¿Qué es más eficiente? ¿Usar pow para cuadrar o simplemente multiplicarlo consigo mismo?

¿Cuál de estos dos métodos es en C más eficiente? Y qué tal:

pow(x,3)

vs.

x*x*x // etc?

Probé la diferencia de rendimiento entre x*x*...vs pow(x,i)para pequeños iusando este código:

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

Los resultados son:

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

Tenga en cuenta que acumulo el resultado de cada cálculo de pow para asegurarme de que el compilador no lo optimice.

Si uso la std::pow(double, double)versión y loops = 1000000l, obtengo:

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

Esto es en un Intel Core Duo con Ubuntu 9.10 de 64 bits. Compilado usando gcc 4.4.1 con optimización -o2.

Entonces, en C, sí x*x*xserá más rápido que pow(x, 3), porque no hay pow(double, int)sobrecarga. En C ++, será aproximadamente lo mismo. (Suponiendo que la metodología en mis pruebas sea correcta).

Esto es en respuesta al comentario hecho por An Markm:

Incluso si using namespace stdse emitió una directiva, si el segundo parámetro powes an int, se llamará a la std::pow(double, int)sobrecarga de en <cmath>lugar de ::pow(double, double)desde <math.h>.

Este código de prueba confirma ese comportamiento:

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

Ese es el tipo de pregunta equivocado. La pregunta correcta sería: "¿Cuál es más fácil de entender para los lectores humanos de mi código?"

Si la velocidad importa (más tarde), no pregunte, mida. (Y antes de eso, mida si optimizar esto realmente hará alguna diferencia notable). Hasta entonces, escriba el código para que sea más fácil de leer.

Editar
Solo para dejar esto en claro (aunque ya debería haber sido): las aceleraciones revolucionarias generalmente provienen de cosas como el uso de mejores algoritmos , la mejora de la ubicación de los datos , la reducción del uso de memoria dinámica , los resultados previos al cálculo , etc. Rara vez provienen de micro-optimizando llamadas de función única , y donde lo hacen, lo hacen en muy pocos lugares , lo que solo se encontrarían mediantedeclaraciones cuidadosas (y que consumen mucho tiempo)), y lo que es una optimización para una plataforma es a veces una pesimización para otra ( es por eso que necesita medir, en lugar de preguntar, porque no conocemos / tenemos completamente su entorno). perfil, la mayoría de las veces pueden acelerarse haciendo muy poco intuitivos cosas (como insertarnoop

Permítanme subrayar esto nuevamente: incluso en las pocas aplicaciones en las que estas cosas importan, no importan en la mayoría de los lugares donde se usan, y es muy poco probable que encuentre los lugares donde importan mirando el código. Realmente necesita identificar los puntos calientes primero , porque de lo contrario optimizar el código es solo una pérdida de tiempo .

Incluso si una sola operación (como calcular el cuadrado de algún valor) ocupa el 10% del tiempo de ejecución de la aplicación (que IME es bastante raro), e incluso si la optimización ahorra el 50% del tiempo necesario para esa operación (que IME es incluso mucho, mucho más raro), aún así hizo que la aplicación tomara solo un 5% menos de tiempo .
Sus usuarios necesitarán un cronómetro para notarlo. (Supongo que en la mayoría de los casos algo menos del 20% de aceleración pasa desapercibido para la mayoría de usuarios. Y que es de cuatro puntos tales que necesita para encontrar.)

x*xo x*x*xserá más rápido que pow, ya que powdebe ocuparse del caso general, mientras quex*x es específico. Además, puede eludir la llamada a la función y cosas por el estilo.

Sin embargo, si se encuentra microoptimizando de esta manera, necesita obtener un generador de perfiles y crear perfiles serios. La abrumadora probabilidad es que nunca notarías ninguna diferencia entre los dos.

También me preguntaba sobre el problema de rendimiento, y esperaba que el compilador lo optimizara, según la respuesta de @EmileCormier. Sin embargo, me preocupaba que el código de prueba que mostraba aún permitiera al compilador optimizar la llamada std :: pow (), ya que se usaban los mismos valores en la llamada cada vez, lo que permitiría al compilador almacenar los resultados y reutilícelo en el bucle: esto explicaría los tiempos de ejecución casi idénticos para todos los casos. Así que también le eché un vistazo.

Aquí está el código que usé (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;
}

Esto fue compilado usando:

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

Básicamente, la diferencia es el argumento de std :: pow () es el contador de bucle. Como temía, la diferencia de rendimiento es pronunciada. Sin el indicador -O2, los resultados en mi sistema (Arch Linux de 64 bits, g ++ 4.9.1, Intel i7-4930) fueron:

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)

Con la optimización, los resultados fueron igualmente sorprendentes:

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)

Así que parece que el compilador al menos intenta optimizar el caso std :: pow (x, 2), pero no el caso std :: pow (x, 3) (tarda ~ 40 veces más que el caso std :: pow (x, 2) caso). En todos los casos, la expansión manual funcionó mejor, pero particularmente para la carcasa Power 3 (60 veces más rápida). Esto definitivamente vale la pena tenerlo en cuenta si ejecuta std :: pow () con potencias enteras superiores a 2 en un bucle cerrado ...

La forma más eficiente es considerar el crecimiento exponencial de las multiplicaciones. Verifique este código para 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 el exponente es constante y pequeño, amplíelo, minimizando el número de multiplicaciones. (Por ejemplo, x^4no es óptimamente x*x*x*x, pero y*ydónde y=x*x. Y x^5es y*y*xdóndey=x*x . Y así sucesivamente.) Para exponentes enteros constantes, simplemente escriba la forma optimizada ya; con pequeños exponentes, esta es una optimización estándar que debe realizarse tanto si el código ha sido perfilado como si no. La forma optimizada será más rápida en un porcentaje tan grande de casos que básicamente siempre vale la pena hacerlo.

(Si usa Visual C ++, std::pow(float,int) realiza la optimización a la que aludo, por lo que la secuencia de operaciones está relacionada con el patrón de bits del exponente. Sin embargo, no garantizo que el compilador desenrollará el bucle por usted, por lo que aún vale la pena hacerlo a mano.)

[editar] Por cierto, powtiene una tendencia (no) sorprendente a aparecer en los resultados del generador de perfiles. Si no lo necesita absolutamente (es decir, el exponente es grande o no es una constante) y está preocupado por el rendimiento, lo mejor es escribir el código óptimo y esperar a que el generador de perfiles le diga que es (sorprendentemente ) perdiendo el tiempo antes de pensar más. (La alternativa es llamar powy pedirle al generador de perfiles que le diga que (como era de esperar) está perdiendo el tiempo; está recortando este paso al hacerlo de manera inteligente).

He estado ocupado con un problema similar y estoy bastante desconcertado por los resultados. Estaba calculando x⁻³ / ² para la gravitación newtoniana en una situación de n cuerpos (aceleración sufrida por otro cuerpo de masa M situado en un vector de distancia d): a = M G d*(d²)⁻³/²(donde d² es el punto (escalar) producto de d por sí mismo), y pensé que calcular M*G*pow(d2, -1.5)sería más simple queM*G/d2/sqrt(d2)

El truco es que es cierto para sistemas pequeños, pero a medida que los sistemas crecen en tamaño, se M*G/d2/sqrt(d2)vuelven más eficientes y no entiendo por qué el tamaño del sistema afecta este resultado, porque repetir la operación en diferentes datos no lo hace. Es como si hubiera posibles optimizaciones a medida que el sistema crece, pero que no son posibles conpow