Qu'est-ce qui est le plus efficace ? Utiliser pow au carré ou simplement le multiplier par lui-même ?

Question

Laquelle de ces deux méthodes est la plus efficace en C ? Et que dire de :

pow(x,3)

vs.

x*x*x // etc?

Answer 1

MISE À JOUR 2021

J'ai modifié le code du benchmark comme suit :

• std::chrono utilisé pour les mesures de timing au lieu de boost
• C++11 <random> utilisé à la place de rand()
• Évitez les opérations répétées qui risquent de vous faire sortir par hélitreuillage. Le paramètre de base est en constante évolution.

J'obtiens les résultats suivants avec GCC 10 -O2 (en secondes) :

exp     c++ pow     c pow       x*x*x...
2       0.204243    1.39962     0.0902527   
3       1.36162     1.38291     0.107679    
4       1.37717     1.38197     0.106103    
5       1.3815      1.39139     0.117097

GCC 10 -O3 est presque identique à GCC 10 -O2.

Avec GCC 10 -O2 -ffast-math :

exp     c++ pow     c pow       x*x*x...
2       0.203625    1.4056      0.0913414   
3       0.11094     1.39938     0.108027    
4       0.201593    1.38618     0.101585    
5       0.102141    1.38212     0.10662

Avec GCC 10 -O3 -ffast-math :

exp     c++ pow     c pow       x*x*x...
2       0.0451995   1.175       0.0450497   
3       0.0470842   1.20226     0.051399    
4       0.0475239   1.18033     0.0473844   
5       0.0522424   1.16817     0.0522291

Avec Clang 12 -O2 :

exp     c++ pow     c pow       x*x*x...
2       0.106242    0.105435    0.105533    
3       1.45909     1.4425      0.102235    
4       1.45629     1.44262     0.108861    
5       1.45837     1.44483     0.1116

Clang 12 -O3 est presque identique à Clang 12 -O2.

Avec Clang 12 -O2 -ffast-math :

exp     c++ pow     c pow       x*x*x...
2       0.0233731   0.0232457   0.0231076   
3       0.0271074   0.0266663   0.0278415   
4       0.026897    0.0270698   0.0268115   
5       0.0312481   0.0296402   0.029811    

Clang 12 -O3 -ffast-math est presque identique à Clang 12 -O2 -ffast-math.

La machine est un Intel Core i7-7700K sur Linux 5.4.0-73-generic x86_64.

Conclusions :

• Avec GCC 10 (sans -ffast-math), x*x*x... es toujours plus rapide
• Avec GCC 10 -O2 -ffast-math, std::pow est aussi rapide que x*x*x... pour étrange exponents
• Avec GCC 10 -O3 -ffast-math, std::pow est aussi rapide que x*x*x... pour tous les cas de test, et est environ deux fois plus rapide que -O2.
• Avec le GCC 10, le C pow(double, double) est toujours beaucoup plus lent
• Avec Clang 12 (sans -ffast-math), x*x*x... est plus rapide pour les exposants supérieurs à 2
• Avec Clang 12 -ffast-math, toutes les méthodes produisent des résultats similaires
• Avec Clang 12, pow(double, double) est aussi rapide que std::pow pour les exposants entiers
• Ecrire des benchmarks sans que le compilateur soit plus malin que vous, c'est dur .

Je finirai par installer une version plus récente de GCC sur ma machine et je mettrai à jour mes résultats lorsque ce sera fait.

Voici le code de référence mis à jour :

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

using Moment = std::chrono::high_resolution_clock::time_point;
using FloatSecs = std::chrono::duration<double>;

inline Moment now()
{
    return std::chrono::high_resolution_clock::now();
}

#define TEST(num, expression) \
double test##num(double b, long loops) \
{ \
    double x = 0.0; \
\
    auto startTime = now(); \
    for (long i=0; i<loops; ++i) \
    { \
        x += expression; \
        b += 1.0; \
    } \
    auto elapsed = now() - startTime; \
    auto seconds = std::chrono::duration_cast<FloatSecs>(elapsed); \
    std::cout << seconds.count() << "\t"; \
    return x; \
}

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 testCppPow(double base, long loops)
{
    double x = 0.0;

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

    auto seconds = std::chrono::duration_cast<FloatSecs>(elapsed); \
    std::cout << seconds.count() << "\t"; \

    return x;
}

double testCPow(double base, double exponent, long loops)
{
    double x = 0.0;

    auto startTime = now();
    for (long i=0; i<loops; ++i)
    {
        x += ::pow(base, exponent);
        base += 1.0;
    }
    auto elapsed = now() - startTime;

    auto seconds = std::chrono::duration_cast<FloatSecs>(elapsed); \
    std::cout << seconds.count() << "\t"; \

    return x;
}

int main()
{
    using std::cout;
    long loops = 100000000l;
    double x = 0;
    std::random_device rd;
    std::default_random_engine re(rd());
    std::uniform_real_distribution<double> dist(1.1, 1.2);
    cout << "exp\tc++ pow\tc pow\tx*x*x...";

    cout << "\n2\t";
    double b = dist(re);
    x += testCppPow<2>(b, loops);
    x += testCPow(b, 2.0, loops);
    x += test2(b, loops);

    cout << "\n3\t";
    b = dist(re);
    x += testCppPow<3>(b, loops);
    x += testCPow(b, 3.0, loops);
    x += test3(b, loops);

    cout << "\n4\t";
    b = dist(re);
    x += testCppPow<4>(b, loops);
    x += testCPow(b, 4.0, loops);
    x += test4(b, loops);

    cout << "\n5\t";
    b = dist(re);
    x += testCppPow<5>(b, loops);
    x += testCPow(b, 5.0, loops);
    x += test5(b, loops);

    std::cout << "\n" << x << "\n";
}

---

Ancienne réponse, 2010

J'ai testé la différence de performance entre x*x*... vs pow(x,i) pour les petits i en utilisant 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 pow pour m'assurer que le compilateur ne l'optimise pas.

Si j'utilise le 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

C'est sur un Intel Core Duo exécutant Ubuntu 9.10 64bit. Compilé avec gcc 4.4.1 avec l'optimisation -o2.

Donc en C, oui x*x*x sera plus rapide que pow(x, 3) parce qu'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 soit correcte).

---

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

Même si un using namespace std a été émise, si le deuxième paramètre de la directive pow est un int alors le std::pow(double, int) surcharge de <cmath> sera appelé à la place de ::pow(double, double) de <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;
}

Answer 2

x*x o x*x*x sera plus rapide que pow puisque pow doit traiter le cas général, alors que x*x est spécifique. Vous pouvez également élider l'appel de fonction et autres.

Cependant, si vous vous surprenez à micro-optimiser de la sorte, vous devez vous procurer un profileur et procéder à un profilage sérieux. Il est fort probable que vous ne remarquerez jamais de différence entre les deux.

Answer 3

Je me posais également la question des performances, et j'espérais que le compilateur les optimiserait, sur la base de la réponse de @EmileCormier. Cependant, je craignais que le code de test qu'il a montré permette encore au compilateur d'optimiser l'appel std::pow(), puisque les mêmes valeurs sont utilisées dans l'appel à chaque fois, ce qui permettrait au compilateur de stocker les résultats et de les réutiliser dans la boucle - cela expliquerait les temps d'exécution presque identiques pour tous les cas. J'y ai donc jeté un coup d'œil également.

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;
}

Ceci a été compilé en utilisant :

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

En gros, la différence est que l'argument de std::pow() est le compteur de boucle. Comme je le craignais, la différence de performance est prononcée. Sans le drapeau -O2, les résultats sur mon système (Arch Linux 64-bit, 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 étaient 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) (il prend ~40 fois plus de temps que le cas std::pow(x,2)). Dans tous les cas, l'expansion manuelle a donné de meilleurs résultats - mais particulièrement pour le cas de la puissance 3 (60 fois plus rapide). Cela vaut vraiment la peine d'en tenir compte si vous utilisez std::pow() avec des puissances entières supérieures à 2 dans une boucle serrée...

Answer 4

La manière la 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;
}

Answer 5

Si l'exposant est constant et petit, développez-le en minimisant le nombre de multiplications. (Par exemple, x^4 n'est pas optimale x*x*x*x mais y*y donde y=x*x . Et x^5 es y*y*x donde y=x*x . Et ainsi de suite). Pour les exposants entiers constants, il suffit d'écrire déjà la forme optimisée ; avec les petits exposants, il s'agit d'une optimisation standard qui devrait ê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 de la faire.

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

[modifier] BTW pow a une tendance (peu) surprenante à apparaître dans les résultats du profileur. Si vous n'en avez pas absolument besoin (c'est-à-dire si l'exposant est grand ou n'est pas une constante), et si vous êtes préoccupé par les performances, il vaut mieux écrire le code optimal et attendre que le profileur vous dise qu'il perd (étonnamment) du temps avant d'aller plus loin. (L'alternative est d'appeler pow et que le profileur vous dise que c'est (sans surprise) une perte de temps - vous supprimez cette étape en la faisant intelligemment).