std::complex vs. Eigenbau



  • Hi!

    Das hier ist keine Frage, sondern nur eine Feststellung. Und zwar sitze ich gerade an einer WinXP-Kiste und habe den GCC (g++) 4.5 etwas getriezt. Dabei ist mir folgendes aufgefallen:

    • std::complex<double> mit Operatoren (*,+) ist im Verglech zum "manuellen" Hantieren von Real- und Imaginärteil im Default-Modus etwa 7mal langsamer
    • schaltet man -ffast-math ein, wird std::complex<double> fast genauso flott wie die "manuelle Alternative".

    Was ich berechne: Ich accumuliere einen Haufen von komplexwertigen Matrix-Produkten der Art T1H*T1 + T2H*T2 + ... + TNH*TN wobei die Ts komplexwertige Matrizen sind und das H im Superskript für eine konjugierte Transposition steht.

    Ich werde morgen vielleicht nochmal den MSVC Compiler anschmeißen und gucken, wie es da mit der Performanz aussieht. Jedenfalls haben mich diese Ergebnisse überrascht und ich wollte sie Euch nicht vorenthalten. 🙂

    Scheinbar wird ohne -ffast-math noch ganz viel an Sonderbehandlungen bzgl NaN und Inf in den std::complex-Operatoren gemacht, die ich eigentlich auch gar nicht brauche.

    kk



  • Ist std::complex denn beim GCC nicht eine reine Library-Implementierung?

    Falls ja, dürfte (sollte) der -ffast-math switch keine Auswirkung auf das haben was in std::complex gemacht wird, sondern nur darauf, was der Compiler daraus im Endeffekt für Code macht.
    Anders gesagt: ich glaube dass man den selbe Unterschied sehem müsste, wenn man sich eine eigene "complex" Klasse bastelt, und dann einmal mit und einmal ohne -ffast-math compiliert.



  • Nee, das stimmt so nicht. Ich habe es ja ausprobiert. Beide Implementierung (also std::complex vs meinen Kram) mit und ohne -ffast-math. Übrigens setzt -ffast-mat das Makro __FAST_MATH__ (wenn ich mich richtig erinnere, ich habe die Doku grad nicht mehr vor mir liegen).

    kk



  • krümelkacker schrieb:

    Nee, das stimmt so nicht. Ich habe es ja ausprobiert. Beide Implementierung (also std::complex vs meinen Kram) mit und ohne -ffast-math.

    Ergebnis: ffast-math macht bei der eigenen Implementierungen so gut wie keinen Unterschied. std::complex<double> wird etwa 7mal schneller dadurch (und damit etwa genauso schnell wie die eigene Impl).



  • Habe ähnliche Infos hier gefunden:
    http://old.nabble.com/performance-question-with-std::complex<float>-in-new-g%2B%2B-versions-td27187415.html
    Anscheinend war std::complex<double> bem GCC 4.2 und früher noch nicht so lahm und ab 4.3 hamse std::complex "konform" implementiert, was nicht mehr so schnell ist, wie vorher -- zumindest nicht, wenn man sich ffast-math spart.



  • Rein aus Interesse: Teste mal gegen _Complex. Das ist C99 aber die gcc könnte das auch im C++-Mode unterstützen.

    Achja, der Code wäre auch ganz interessant.



  • @krümelkacker: dann guck doch bitte einfach in der Implementierung von std::complex nach ob __FAST_MATH__ dort vorkommt. Ich würde mal tippen es kommt nicht vor. Wieso sollte es auch.

    Deine Implementierung wird einfach anders aussehen, und dadurch seltener dazu führen dass ohne -ffast-math irgendwelche langsamen Checks/... generiert werden müssen.



  • Was ist eigentlich der "Default-Modus"? -O3, will ich hoffen?


  • Global Moderator

    Niemanden interessiert es, wie schnell Code ohne Compileroptimierungen läuft.



  • Das dürfte hiermit zusammenhängen:

    g++ manpage schrieb:

    -fcx-limited-range

    When enabled, this option states that a range reduction step is not needed when performing complex division. Also, there is no checking whether the result of a complex multiplication or division is "NaN + I*NaN", with an attempt to rescue the situation in that case. The default is -fno-cx-limited-range, but is enabled by -ffast-math.

    This option controls the default setting of the ISO C99 "CX_LIMITED_RANGE" pragma. Nevertheless, the option applies to all languages.



  • hustbaer schrieb:

    Ist std::complex denn beim GCC nicht eine reine Library-Implementierung?

    Kommt drauf an, was du unter "reine Library-Implementierung" verstehst. libstdc++s std::complex nutzt intern je nach Situation auch C99s _Complex.



  • Etwas was keine Compiler-Magick verwendet.
    _Complex zu verwenden rechne ich in C++ zu Compiler-Magick, da es _Complex in Standard-C++ nicht gibt.



  • hustbaer schrieb:

    Compiler-Magick

    Wieder was dazugelernt:
    http://de.wikipedia.org/wiki/Magick

    war das mit Absicht oder ists nur Zufall, dass es das Wort gibt? 😛

    bb



  • krümelkacker schrieb:

    im Default-Modus etwa 7mal langsamer

    Was ist bitte der Default-Modus. Und zudem hoffe ich das du die Geschwindigkeit grundsätzlich im Release-Modus testest (Debug ist nur zum debuggen).



  • Hmm... dass man hier eher davon ausgeht, dass ich Mist gebaut habe, als dass std::complex ohne -ffast-math wirklich sehr langsam ist, bestätigt mich, was den Sinn des Threads angeht. 🙂 Wie gesagt, ich war auch überrascht.

    Den originalen Quellcode kann ich aus rechtlichen Gründen nicht zeigen. Ich habe aber ein anderes Testprogramm geschrieben:

    #include <complex>
    #include <vector>
    #include <algorithm>
    
    using std::complex;
    using std::vector;
    
    typedef std::complex<double> complx;
    
    complx scalarproduct_version1(vector<complx> const& a, vector<complx> const& b)
    {
      typedef vector<complx>::size_type sizt;
      complx accumulator = 0;
      sizt len = std::min(a.size(),b.size());
      for (sizt i=0; i<len; ++i) {
        accumulator += conj(a[i]) * b[i];
      }
      return accumulator;
    }
    
    complx scalarproduct_version2(vector<complx> const& a, vector<complx> const& b)
    {
      typedef vector<complx>::size_type sizt;
      double accumR = 0;
      double accumI = 0;
      sizt len = std::min(a.size(),b.size());
      for (sizt i=0; i<len; ++i) {
        double ar = real(a[i]);
        double ai = imag(a[i]);
        double br = real(b[i]);
        double bi = imag(b[i]);
        accumR += ar*br+ai*bi;
        accumI += ar*bi-ai*br;
      }
      return complx(accumR,accumI);
    }
    
    #include <iostream>
    #include <ostream>
    #include <ctime>
    
    using std::cout;
    using std::endl;
    
    const int vecsize = 4096;
    const int passes  = 15000;
    
    int main()
    {
      vector<complx> a (vecsize, complx(2,1));
      vector<complx> b (vecsize, complx(1,3));
      std::clock_t time1 = std::clock();
      for (int pass=0; pass<passes; ++pass) {
        scalarproduct_version1(a,b);
      }
      std::clock_t time2 = std::clock();
      for (int pass=0; pass<passes; ++pass) {
        scalarproduct_version2(a,b);
      }
      std::clock_t time3 = std::clock();
      cout << double(time2-time1)/CLOCKS_PER_SEC << endl;
      cout << double(time3-time2)/CLOCKS_PER_SEC << endl;
    }
    

    Hier kann man sehen, dass scalarproduct_version1 Multiplikation und Addition über die überladenen Operatorn für std::complex<double> verwendet. scalarproduct_version2 rechnet manuell auf Real-/Imaginärteil.

    Es ergibt sich auf meinem Bürorechner (WinXP, MinGW-TDM, GCC4.5) folgende Tabelle:

    --Zeit, in Sekunden--
    Compiler-Optionen        Version 1   Version 2
    ----------------------------------------------
    -O3 -DNDEBUG               4.515       0.375
    -O3 -DNDEBUG -ffast-math   0.375       0.375
    

    I rest my case.

    kk



  • Selber Rechner, selber Compiler (GCC), andere Optionen:

    --Zeit, in Sekunden--
    Compiler-Optionen                                    Version 1   Version 2
    --------------------------------------------------------------------------
    -O3 -DNDEBUG -march=native -mtune=native               2.406       0.375
    -O3 -DNDEBUG -march=native -mtune=native -ffast-math   0.406       0.312
    

    Selber Rechner mit Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 for 80x86. Der Microsoft Compiler hat scheinbar erkannt, dass der Aufruf scalarproduct_version2(a,b); komplett wegoptimiert werden kann. Ich habe daher das Programm etwas modifiziert, so dass das Ergebnis des Funktionsaufruf wieder an eine andere Funktion "foo" übergeben wird, die ich so definiert habe:

    void foo(complx) {}
    

    Damit erhalte ich folgende Ergebnisse

    --Zeit, in Sekunden--
    Compiler-Optionen        Version 1   Version 2
    ----------------------------------------------
    /O2 /Ob1 /Oi               0.512       0.283
    

    Ich muss gestehen, dass ich mich mit dem Microsoft-Compiler nicht richtig gut auskenne. Vielleicht habt ihr noch Ideen, was man für Optionen verwenden kann.

    So richtig überzeugen tut mich std::complex<double> bzgl Performance nicht. Beim GCC muss ich -ffast-math verwenden und beim Microsoft Compiler bekomme ich bisher nicht an die "manuelle" Version dran. Ich bin bei meiner Anwendung nicht an super-duper Genauigkeit für extrem kleine oder extrem große Werte interessiert. Nan und Inf kommt bei mir auch nicht vor. Daher brauche ich keine (genauigkeiterhaltende) Sonderbehandlungen. Das kostet nur Zeit. Laut Profiler sind komplex-wertige Produkte in meiner Anwendung der Flaschenhals.

    kk



  • Der Benchmark ist fuer den Arsch. bei mir dauert alles 0 Sekunden mit g++ -O3 unter Linux. Ausserdem vergleichst du hier zwei unterschiedliche Ansaetze zur Berechnung des Skalarprodukts und nicht die Performance von std::complex.



  • knivil schrieb:

    Der Benchmark ist fuer den *****. bei mir dauert alles 0 Sekunden mit g++ -O3 unter Linux. Ausserdem vergleichst du hier zwei unterschiedliche Ansaetze zur Berechnung des Skalarprodukts und nicht die Performance von std::complex.

    Keine Ahnung, was Du da treibst. Bei mir verhält es sich sowohl unter Linux (mit gcc 4.4) als auch unter Windows (MSVC2008SP1) so, wie es KK beschreibst. Außerdem gibt es nur einen Ansatz zur Berechnung des Skalarproduktes.

    Offensichtlich verhalten sich die Operatoren und Funktionen, die für std::complex definiert sind, je nach eingestellter Optimierung unterschiedlich. Hätte ich so eigentlich nicht erwartet.



  • knivil schrieb:

    Der Benchmark ist fuer den *****. bei mir dauert alles 0 Sekunden mit g++ -O3 unter Linux.

    Das kann zwei Gründe haben. Entweder wurde erkannt, dass die Berechnungen ins leere laufen und nach der as-if Regel komplett wegoptimiert werden können, oder sie liefen alle so schnell bei dir, dass die Granularität der Uhr bei der Zeitmessung das Problem ist. Letzteres kannst Du mit Erhöhen von 'passes' und 'vecsize' kompensieren. Ersteres kannst Du umgehen, indem Du zB die Skalarprodukte nochmal alle aufsummierst und ganz zum Schluss auf die Konsole schickst. Ich bin mir dessen wohl bewusst, auch ohne Deinen Kommentar. Ich habe nicht behauptet, dass die Ergebnisse des Benchmarks von jedem korrekt interpretiert werden können.

    knivil schrieb:

    Ausserdem vergleichst du hier zwei unterschiedliche Ansaetze zur Berechnung des Skalarprodukts und nicht die Performance von std::complex

    Der "Ansatz" ist der gleiche. Nur in einem Fall verwende ich conj, operator* und operator+ für std::complex<double> und in anderem Fall eben nicht. Wie Du auf diese These kommst, ist mir schleirhaft.

    kk


  • Global Moderator

    Ich muss knivil Zustimmen. Da wird bei mir vom GCC alles wegoptimiert, selbst mit dem foo-Trick. Deshalb frage ich mich, ob da nicht vielleicht etwas mit den Optimierungseinstellungen bei euch nicht passt, wenn ihr doch den gleichen Compiler benutzt.

    Was ich ganz lustig finde: Ich habe das mal durch den Intel-Compiler gejagt. Bei normaler Optimierung erhält man das gleiche Ergebnis wie krümelkacker, d.h. Version 2 ist ungefähr doppelt so schnell wie Version 1. Was jetzt aber interessant ist, was passiert, wenn ich architekturspezifische Optimierung anschalte: Dann braucht Version 1 nämlich auf einmal 5x so lange wie vorher, während dies keine Auswirkungen auf die andere Version hat. Da geht irgendetwas Mysteriöses vor sich.

    Was man noch erwähnen sollte ist, dass der Intel-Compiler in der erfahrungsgemäß (meine Erfahrung) besten Optimierungsstufe (d.h. mit Optimierungsprofil) für beide Versionen fast gleich schnellen Code produziert. Wobei Version 2 bei allen beschriebenen Versuchen immer gleich schnell war. Anscheinend besteht bei Version 1 gehöriges Optimierungspotential, der Compiler benötigt nur genügend Informationen. Version 2 scheint hingegen schon perfekt handoptimiert zu sein, da ist nichts mehr herauszuholen.