Was ist effizienter? Verwenden Sie pow, um es zu quadrieren oder einfach mit sich selbst zu multiplizieren?

Welche dieser beiden Methoden ist in C effizienter? Und wie wäre es mit:

pow(x,3)

vs.

x*x*x // etc?

Ich habe den Leistungsunterschied zwischen x*x*...vs pow(x,i)für small imit diesem Code getestet :

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

Ergebnisse sind:

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

Beachten Sie, dass ich das Ergebnis jeder Pow-Berechnung akkumuliere, um sicherzustellen, dass der Compiler es nicht entfernt.

Wenn ich die std::pow(double, double)Version benutze und loops = 1000000l, bekomme ich:

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

Dies ist auf einem Intel Core Duo mit Ubuntu 9.10 64bit. Kompiliert mit gcc 4.4.1 mit -o2 Optimierung.

In C ist ja x*x*xalso schneller als pow(x, 3), weil es keine pow(double, int)Überlastung gibt. In C ++ wird es ungefähr gleich sein. (Vorausgesetzt, die Methodik in meinen Tests ist korrekt.)

Dies ist eine Antwort auf den Kommentar von An Markm:

Selbst wenn eine using namespace stdDirektive ausgegeben wurde und der zweite Parameter powein ist int, wird die std::pow(double, int)Überladung von <cmath>anstelle von ::pow(double, double)von aufgerufen<math.h> .

Dieser Testcode bestätigt dieses Verhalten:

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

Das ist die falsche Frage. Die richtige Frage wäre: "Welches ist für menschliche Leser meines Codes leichter zu verstehen?"

Wenn Geschwindigkeit wichtig ist (später), fragen Sie nicht, sondern messen Sie. (Messen Sie vorher, ob die Optimierung tatsächlich einen spürbaren Unterschied macht.) Schreiben Sie den Code bis dahin so, dass er am einfachsten zu lesen ist.

Bearbeiten
Nur um dies zu verdeutlichen (obwohl dies bereits hätte sein sollen): Durchbruchbeschleunigungen entstehen normalerweise durch die Verwendung besserer Algorithmen , die Verbesserung der Datenlokalität, die Reduzierung des dynamischen Speichers , die Vorberechnung von Ergebnissen usw. Sie kommen selten vor Mikrooptimierende Einzelfunktionsaufrufe , und wo sie dies tun, tun sie dies an sehr wenigen Stellen , die nur durch sorgfältige (und zeitaufwändige) Profilerstellung gefunden werden können. Meistens können sie durch sehr nicht intuitive Funktionen beschleunigt werden Dinge (wie das Einfügennoop Aussagen), und was eine Optimierung für eine Plattform ist, ist manchmal eine Pessimierung für eine andere (weshalb Sie messen müssen, anstatt zu fragen, weil wir Ihre Umgebung nicht vollständig kennen / haben).

Lassen Sie mich dies noch einmal unterstreichen: Selbst in den wenigen Anwendungen, in denen solche Dinge wichtig sind, spielen sie an den meisten Stellen, an denen sie verwendet werden, keine Rolle, und es ist sehr unwahrscheinlich, dass Sie die Stellen finden, an denen sie wichtig sind, indem Sie sich den Code ansehen. Sie müssen die Hot Spots wirklich zuerst identifizieren , da sonst die Optimierung des Codes nur Zeitverschwendung ist .

Selbst wenn eine einzelne Operation (wie das Berechnen des Quadrats eines Werts) 10% der Ausführungszeit der Anwendung beansprucht (was IME ziemlich selten ist), und selbst wenn die Optimierung 50% der für diese Operation erforderlichen Zeit spart (was IME ist) sogar viel, viel seltener), Sie haben dafür gesorgt, dass die Anwendung nur 5% weniger Zeit in Anspruch nimmt .
Ihre Benutzer benötigen eine Stoppuhr, um dies überhaupt zu bemerken. (Ich denke, in den meisten Fällen bleibt etwas unter 20% Beschleunigung für die meisten Benutzer unbemerkt. Und das sind vier solcher Stellen, die Sie finden müssen.)

x*xoder x*x*xwird schneller sein als pow, da powmuss sich mit dem allgemeinen Fall befassen, während x*xspezifisch ist. Sie können auch den Funktionsaufruf und dergleichen weglassen.

Wenn Sie jedoch feststellen, dass Sie auf diese Weise eine Mikrooptimierung durchführen, müssen Sie einen Profiler erstellen und ernsthafte Profilerstellungen durchführen. Die überwältigende Wahrscheinlichkeit ist, dass Sie niemals einen Unterschied zwischen den beiden bemerken würden.

Ich habe mich auch über das Leistungsproblem gewundert und gehofft, dass dies vom Compiler basierend auf der Antwort von @EmileCormier optimiert wird. Ich befürchtete jedoch, dass der von ihm angezeigte Testcode es dem Compiler weiterhin ermöglichen würde, den Aufruf von std :: pow () zu optimieren, da im Aufruf jedes Mal dieselben Werte verwendet wurden, wodurch der Compiler die Ergebnisse und speichern konnte Verwenden Sie es erneut in der Schleife - dies würde die nahezu identischen Laufzeiten für alle Fälle erklären. Also habe ich es mir auch angesehen.

Hier ist der Code, den ich verwendet habe (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;
}

Dies wurde kompiliert mit:

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

Grundsätzlich ist der Unterschied das Argument, dass std :: pow () der Schleifenzähler ist. Wie ich befürchtet habe, ist der Leistungsunterschied ausgeprägt. Ohne das Flag -O2 waren die Ergebnisse auf meinem System (Arch Linux 64-Bit, g ++ 4.9.1, Intel i7-4930):

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)

Bei der Optimierung waren die Ergebnisse gleichermaßen beeindruckend:

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)

Es sieht also so aus, als würde der Compiler zumindest versuchen, den Fall std :: pow (x, 2) zu optimieren, nicht jedoch den Fall std :: pow (x, 3) (es dauert ~ 40-mal länger als der Fall std :: pow (x, 2) Fall). In allen Fällen schnitt die manuelle Erweiterung besser ab - insbesondere beim Power 3-Gehäuse (60-mal schneller). Dies ist auf jeden Fall zu beachten, wenn Sie std :: pow () mit ganzzahligen Potenzen größer als 2 in einer engen Schleife ausführen ...

Am effizientesten ist es, das exponentielle Wachstum der Multiplikationen zu berücksichtigen. Überprüfen Sie diesen Code auf 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;
}

Wenn der Exponent konstant und klein ist, erweitern Sie ihn und minimieren Sie die Anzahl der Multiplikationen. (Zum Beispiel x^4ist nicht optimal x*x*x*x, aber y*ywo y=x*x. Und x^5ist y*y*xwoy=x*x . Und so weiter.) Für konstante ganzzahlige Exponenten schreiben Sie einfach das optimierte Formular bereits aus; Bei kleinen Exponenten ist dies eine Standardoptimierung, die durchgeführt werden sollte, unabhängig davon, ob der Code profiliert wurde oder nicht. Das optimierte Formular ist in so vielen Fällen schneller, dass es sich grundsätzlich immer lohnt, es zu tun.

(Wenn Sie Visual C ++ verwenden, std::pow(float,int)führt es die Optimierung durch , auf die ich anspreche, wobei die Reihenfolge der Operationen mit dem Bitmuster des Exponenten zusammenhängt. Ich kann jedoch nicht garantieren, dass der Compiler die Schleife für Sie abrollt, sodass es sich dennoch lohnt, dies zu tun es von Hand.)

Übrigens powhat eine (nicht) überraschende Tendenz, auf den Profiler-Ergebnissen aufzutauchen. Wenn Sie es nicht unbedingt benötigen (dh der Exponent ist groß oder keine Konstante) und sich überhaupt Gedanken über die Leistung machen, schreiben Sie am besten den optimalen Code und warten Sie, bis der Profiler Ihnen dies mitteilt (überraschenderweise) ) Zeit verschwenden, bevor man weiter nachdenkt. (Die Alternative besteht darin, anzurufen powund sich vom Profiler mitteilen zu lassen, dass es (nicht überraschend) Zeitverschwendung ist. Sie können diesen Schritt durch intelligentes Ausführen unterbinden.)

Ich war mit einem ähnlichen Problem beschäftigt und bin ziemlich verwirrt über die Ergebnisse. Ich berechnete x⁻³ / ² für die Newtonsche Gravitation in einer Situation mit n Körpern (Beschleunigung durch einen anderen Massenkörper M, der sich in einem Abstandsvektor d befindet): a = M G d*(d²)⁻³/²(wobei d² das Punktprodukt (Skalarprodukt) von d für sich ist), und ich dachte, das Berechnen M*G*pow(d2, -1.5)wäre einfacher alsM*G/d2/sqrt(d2)

Der Trick ist, dass dies für kleine Systeme zutrifft, aber mit zunehmender Größe der Systeme M*G/d2/sqrt(d2)effizienter wird und ich nicht verstehe, warum sich die Größe des Systems auf dieses Ergebnis auswirkt, da das Wiederholen des Vorgangs mit verschiedenen Daten dies nicht tut. Es ist, als ob es mögliche Optimierungen gäbe, wenn das System wächst, die aber mit nicht möglich sindpow