Qu'est-ce qui est le plus efficace? Utiliser pow pour quadriller ou simplement le multiplier avec lui-même?

Laquelle de ces deux méthodes est en C plus efficace? Et que diriez-vous:

pow(x,3)

contre.

x*x*x // etc?

J'ai testé la différence de performances entre x*x*...vs pow(x,i)pour petit en iutilisant ce code:

#include <cstdlib>
#include <cmath>
#include <boost/date_time/posix_time/posix_time.hpp>

inline boost::posix_time::ptime now()
{
    return boost::posix_time::microsec_clock::local_time();
}

#define TEST(num, expression) \
double test##num(double b, long loops) \
{ \
    double x = 0.0; \
\
    boost::posix_time::ptime startTime = now(); \
    for (long i=0; i<loops; ++i) \
    { \
        x += expression; \
        x += expression; \
        x += expression; \
        x += expression; \
        x += expression; \
        x += expression; \
        x += expression; \
        x += expression; \
        x += expression; \
        x += expression; \
    } \
    boost::posix_time::time_duration elapsed = now() - startTime; \
\
    std::cout << elapsed << " "; \
\
    return x; \
}

TEST(1, b)
TEST(2, b*b)
TEST(3, b*b*b)
TEST(4, b*b*b*b)
TEST(5, b*b*b*b*b)

template <int exponent>
double testpow(double base, long loops)
{
    double x = 0.0;

    boost::posix_time::ptime startTime = now();
    for (long i=0; i<loops; ++i)
    {
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
    }
    boost::posix_time::time_duration elapsed = now() - startTime;

    std::cout << elapsed << " ";

    return x;
}

int main()
{
    using std::cout;
    long loops = 100000000l;
    double x = 0.0;
    cout << "1 ";
    x += testpow<1>(rand(), loops);
    x += test1(rand(), loops);

    cout << "\n2 ";
    x += testpow<2>(rand(), loops);
    x += test2(rand(), loops);

    cout << "\n3 ";
    x += testpow<3>(rand(), loops);
    x += test3(rand(), loops);

    cout << "\n4 ";
    x += testpow<4>(rand(), loops);
    x += test4(rand(), loops);

    cout << "\n5 ";
    x += testpow<5>(rand(), loops);
    x += test5(rand(), loops);
    cout << "\n" << x << "\n";
}

Les résultats sont:

1 00:00:01.126008 00:00:01.128338 
2 00:00:01.125832 00:00:01.127227 
3 00:00:01.125563 00:00:01.126590 
4 00:00:01.126289 00:00:01.126086 
5 00:00:01.126570 00:00:01.125930 
2.45829e+54

Notez que j'accumule le résultat de chaque calcul de puissance pour m'assurer que le compilateur ne l'optimise pas.

Si j'utilise la std::pow(double, double)version et loops = 1000000l, j'obtiens:

1 00:00:00.011339 00:00:00.011262 
2 00:00:00.011259 00:00:00.011254 
3 00:00:00.975658 00:00:00.011254 
4 00:00:00.976427 00:00:00.011254 
5 00:00:00.973029 00:00:00.011254 
2.45829e+52

Ceci est sur un Intel Core Duo exécutant Ubuntu 9.10 64 bits. Compilé en utilisant gcc 4.4.1 avec l'optimisation -o2.

Donc en C, oui x*x*xsera plus rapide que pow(x, 3), car il n'y a pas de pow(double, int)surcharge. En C ++, ce sera à peu près la même chose. (En supposant que la méthodologie de mes tests est correcte.)

C'est en réponse au commentaire fait par An Markm:

Même si une using namespace stddirective a été émise, si le second paramètre to powest an int, alors la std::pow(double, int)surcharge de <cmath>sera appelée au lieu de ::pow(double, double)from<math.h> .

Ce code de test confirme ce comportement:

#include <iostream>

namespace foo
{

    double bar(double x, int i)
    {
        std::cout << "foo::bar\n";
        return x*i;
    }


}

double bar(double x, double y)
{
    std::cout << "::bar\n";
    return x*y;
}

using namespace foo;

int main()
{
    double a = bar(1.2, 3); // Prints "foo::bar"
    std::cout << a << "\n";
    return 0;
}

C'est le mauvais genre de question. La bonne question serait: "Laquelle est la plus facile à comprendre pour les lecteurs humains de mon code?"

Si la vitesse compte (plus tard), ne demandez pas, mais mesurez. (Et avant cela, mesurez si l'optimisation de cela fera réellement une différence notable.) Jusque-là, écrivez le code pour qu'il soit le plus facile à lire.

Modifier
Juste pour ce faire clairement (bien qu'il devrait déjà avoir été): speedups percée viennent généralement des choses comme l' utilisation de meilleurs algorithmes , l' amélioration de la localité des données , en réduisant l'utilisation de la mémoire dynamique , les résultats pré-calcul , etc. Ils viennent rarement de micro-optimisation des appels de fonction unique , et là où ils le font, ils le font dans très peu d'endroits , ce qui ne serait trouvé que par des prudentes (et chronophages) profilage , le plus souvent, ils peuvent être accélérés en faisant très peu intuitif choses (comme insérernoop déclarations), et ce qui est une optimisation pour une plate-forme est parfois une pessimisation pour une autre (c'est pourquoi vous devez mesurer, au lieu de demander, car nous ne connaissons pas / n'avons pas entièrement votre environnement).

Permettez-moi de le souligner à nouveau: même dans les quelques applications où de telles choses comptent, elles n'ont pas d'importance dans la plupart des endroits où elles sont utilisées, et il est très peu probable que vous trouviez les endroits où elles comptent en regardant le code. Vous devez d'abord identifier les points chauds , car sinon, l'optimisation du code n'est qu'une perte de temps .

Même si une seule opération (comme le calcul du carré d'une certaine valeur) occupe 10% du temps d'exécution de l'application (ce qui est assez rare dans l'IME), et même si l'optimisation, cela permet d'économiser 50% du temps nécessaire à cette opération (ce que IME est même beaucoup, beaucoup plus rare), vous avez quand même fait prendre seulement 5% de temps en moins à l'application .
Vos utilisateurs auront besoin d'un chronomètre pour même le remarquer. (Je suppose que dans la plupart des cas, une accélération inférieure à 20% passe inaperçue pour la plupart des utilisateurs. Et c'est quatre de ces endroits que vous devez trouver.)

x*xou x*x*xsera plus rapide que pow, puisque powdoit traiter le cas général, alors quex*x c'est spécifique. En outre, vous pouvez supprimer l'appel de fonction et autres.

Cependant, si vous vous trouvez en micro-optimisation comme celle-ci, vous devez obtenir un profileur et effectuer un profilage sérieux. La probabilité écrasante est que vous ne remarquerez jamais aucune différence entre les deux.

Je m'interrogeais également sur le problème de performances et j'espérais que cela serait optimisé par le compilateur, sur la base de la réponse de @EmileCormier. Cependant, je craignais que le code de test qu'il montrait ne permette toujours au compilateur d'optimiser l'appel std :: pow (), car les mêmes valeurs étaient utilisées dans l'appel à chaque fois, ce qui permettrait au compilateur de stocker les résultats et le réutiliser dans la boucle - cela expliquerait les temps d'exécution presque identiques pour tous les cas. J'ai donc jeté un coup d'œil là-dessus.

Voici le code que j'ai utilisé (test_pow.cpp):

#include <iostream>                                                                                                                                                                                                                       
#include <cmath>
#include <chrono>

class Timer {
  public:
    explicit Timer () : from (std::chrono::high_resolution_clock::now()) { }

    void start () {
      from = std::chrono::high_resolution_clock::now();
    }

    double elapsed() const {
      return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - from).count() * 1.0e-6;
    }

  private:
    std::chrono::high_resolution_clock::time_point from;
};

int main (int argc, char* argv[])
{
  double total;
  Timer timer;



  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += std::pow (i,2);
  std::cout << "std::pow(i,2): " << timer.elapsed() << "s (result = " << total << ")\n";

  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += i*i;
  std::cout << "i*i: " << timer.elapsed() << "s (result = " << total << ")\n";

  std::cout << "\n";

  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += std::pow (i,3);
  std::cout << "std::pow(i,3): " << timer.elapsed() << "s (result = " << total << ")\n";

  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += i*i*i;
  std::cout << "i*i*i: " << timer.elapsed() << "s (result = " << total << ")\n";


  return 0;
}

Cela a été compilé en utilisant:

g++ -std=c++11 [-O2] test_pow.cpp -o test_pow

Fondamentalement, la différence est que l'argument de std :: pow () est le compteur de boucles. Comme je le craignais, la différence de performance est prononcée. Sans l'indicateur -O2, les résultats sur mon système (Arch Linux 64 bits, g ++ 4.9.1, Intel i7-4930) étaient:

std::pow(i,2): 0.001105s (result = 3.33333e+07)
i*i: 0.000352s (result = 3.33333e+07)

std::pow(i,3): 0.006034s (result = 2.5e+07)
i*i*i: 0.000328s (result = 2.5e+07)

Avec l'optimisation, les résultats sont tout aussi frappants:

std::pow(i,2): 0.000155s (result = 3.33333e+07)
i*i: 0.000106s (result = 3.33333e+07)

std::pow(i,3): 0.006066s (result = 2.5e+07)
i*i*i: 9.7e-05s (result = 2.5e+07)

Il semble donc que le compilateur essaie au moins d'optimiser le cas std :: pow (x, 2), mais pas le cas std :: pow (x, 3) (cela prend ~ 40 fois plus longtemps que le cas std :: pow (x, 2) cas). Dans tous les cas, l'expansion manuelle a mieux fonctionné - mais en particulier pour le cas power 3 (60 fois plus rapide). Cela vaut vraiment la peine de garder à l'esprit si vous exécutez std :: pow () avec des puissances entières supérieures à 2 dans une boucle serrée ...

Le moyen le plus efficace est de considérer la croissance exponentielle des multiplications. Vérifiez ce code pour p ^ q:

template <typename T>
T expt(T p, unsigned q){
    T r =1;
    while (q != 0) {
        if (q % 2 == 1) {    // if q is odd
            r *= p;
            q--;
        }
        p *= p;
        q /= 2;
    }
    return r;
}

Si l'exposant est constant et petit, développez-le en minimisant le nombre de multiplications. (Par exemple, x^4n'est pas optimale x*x*x*x, mais y*yoù y=x*x. Et x^5est y*y*xoùy=x*x . Et ainsi de suite.) Pour les exposants entiers constants, écrivez simplement la forme optimisée déjà; avec de petits exposants, il s'agit d'une optimisation standard qui doit être effectuée que le code ait été profilé ou non. La forme optimisée sera plus rapide dans un si grand pourcentage de cas que cela vaut toujours la peine d'être fait.

(Si vous utilisez Visual C ++, std::pow(float,int)effectue l'optimisation à laquelle je fais allusion, dans laquelle la séquence d'opérations est liée au modèle de bits de l'exposant. Je ne garantis pas que le compilateur déroulera la boucle pour vous, cependant, cela vaut toujours la peine de le faire à la main.)

[modifier] BTW powa une tendance (in) surprenante à surgir sur les résultats du profileur. Si vous n'en avez pas absolument besoin (c'est-à-dire que l'exposant est grand ou pas une constante) et que vous êtes du tout préoccupé par les performances, alors mieux vaut écrire le code optimal et attendre que le profileur vous dise que c'est (étonnamment ) perdre du temps avant de réfléchir davantage. (L'alternative est d'appeler powet de demander au profileur de vous dire que vous perdez (sans surprise) du temps - vous supprimez cette étape en le faisant intelligemment.)

J'ai été occupé avec un problème similaire et je suis assez perplexe devant les résultats. Je calculais x⁻³ / ² pour la gravitation newtonienne dans une situation à n corps (accélération subie à partir d'un autre corps de masse M situé à un vecteur de distance d): a = M G d*(d²)⁻³/²(où d² est le produit scalaire de d par lui-même), et je pensais que calculer M*G*pow(d2, -1.5)serait plus simple queM*G/d2/sqrt(d2)

L'astuce est que c'est vrai pour les petits systèmes, mais à mesure que la taille des systèmes augmente, cela M*G/d2/sqrt(d2)devient plus efficace et je ne comprends pas pourquoi la taille du système a un impact sur ce résultat, car répéter l'opération sur différentes données ne le fait pas. C'est comme s'il y avait des optimisations possibles au fur et à mesure de la croissance du système, mais qui ne sont pas possibles avecpow