std::complex vs. Eigenbau



  • 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?


  • Mod

    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


  • Mod

    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.



  • Hab den Code bei mir mal mit VS2010 durchlaufen lassen:

    Version1 = 1.859
    Version2 = 1.437

    vecsize = 40960;
    passes = 10000;

    Compilereinstellungen sind:

    /Zi /nologo /W3 /WX- /O2 /Oi /Ot /Oy- /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm- /EHsc /GS /Gy /arch:SSE2 /fp:fast /Zc:wchar_t /Zc:forScope /Fp"Release\complexTest.pch" /Fa"Release\" /Fo"Release\" /Fd"Release\vc100.pdb" /Gd /analyze- /errorReport:queue

    Die std:: Implementierung ist also schon etwas langsamer. Ich vermute mal, dass da noch irgendwo (Beim operator+ ?)eine temporäre Kopie erzeugt wird.



  • SeppJ schrieb:

    Ich muss knivil Zustimmen.
    Da wird bei mir vom GCC alles wegoptimiert, selbst mit dem foo-Trick.

    Dann mach's besser.

    Wenn man da ganz auf Nummer sicher gehen will, kommt wohl nicht drum herum, die Vektoren aus einer Datei zur Laufzeit zu lesen und die Produkte zu speichern und zum Schluss auszugeben, so dass da nichts nach as-if wegoptimiert werden kann. Soweit bin ich dann noch nicht gegangen. Es muss einfach nur "kompliziert" genug sein. Im Moment sieht es bei mir so aus:

    complx sum1 = 0;
    for (long pass=0; pass<passes; ++pass) {
      sum1 += scalarproduct_version1(a,b);
    }
    ...
    complx sum2 = 0;
    for (long pass=0; pass<passes; ++pass) {
      sum1 += scalarproduct_version1(a,b);
    }
    ...
    cout << sum1 << sum2 << endl;
    

    Ich denke nicht, dass irgendein Compiler den interessanten Teil (skalarproduct_xxx) hier wegoptimieren kann.

    SeppJ schrieb:

    Deshalb frage ich mich, ob da nicht vielleicht etwas mit den Optimierungseinstellungen bei euch nicht passt,

    Ich weiß nicht, welche GCC Version knivel benutzt hat. Vielleicht spielt es auch noch eine Rolle, ob es die MinGW-TDM Version für Win32 ist oder der "native" GCC für Linux.

    Hier nochmal mit der Modifikation von oben (sum1,sum2), mit vecsize=8192, mit passes=88000, mit "-O3 -DNDEBUG -march=native -mtune=native", mit und ohne ffast-math:

    ffast-math   version 1   version 2
    ----------------------------------
       ohne       18.484       4.563
       mit         4.891       3.703
    

    Verwende ich zusätzlich die Option -pg (für den Profiler GProf) erhalte ich folgende Ausgaben:

    ohne ffast-math

    Flat profile:
    
    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total           
     time   seconds   seconds    calls  us/call  us/call  name    
     54.94     11.79    11.79                             __muldc3
     25.44     17.25     5.46    88000    62.05    62.05  scalarproduct_version1
     19.52     21.44     4.19    88000    47.61    47.61  scalarproduct_version2
      0.05     21.45     0.01                             std::string::_S_construct
      0.05     21.46     0.01                             main
    

    mit ffast-math:

    Flat profile:
    
    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total           
     time   seconds   seconds    calls  us/call  us/call  name    
     56.59      4.64     4.64    88000    52.73    52.73  scalarproduct_version1
     43.17      8.18     3.54    88000    40.23    40.23  scalarproduct_version2
      0.12      8.19     0.01                             std::basic_streambuf<...>::imbue(std::locale const&)
      0.12      8.20     0.01                             main
    

    wobei __muldc3 eine "interne" vom GCC bereitgestellte Funktion ist, die ein Produkt von zwei "complex doubles" berechnet. Sie taucht im ffast-math Modus nicht auf. Im ffast-math-Modus findet man die Multiplikationen direkt in der scalarprodukt-Funktion. Ohne ffast-math sieht man nichts von irgendwelchen Multiplikationen im Assemblercode der Funktion *_version1. Ich sehe zwar keinen __muldc3 Aufruf direkt, aber irgendwo müssen ja die Multiplikationen sein. Den Assembler-Code poste ich jetzt aber nicht mehr. Dass kann jeder selbst mal nachgucken.

    kk



  • krümelkacker schrieb:

    complx sum1 = 0;
    for (long pass=0; pass<passes; ++pass) {
      sum1 += scalarproduct_version1(a,b);
    }
    ...
    complx sum2 = 0;
    for (long pass=0; pass<passes; ++pass) {
      sum1 += scalarproduct_version1(a,b);
    }
    ...
    cout << sum1 << sum2 << endl;
    

    Das muss natürlich "_version2" in der zweiten Schleife heißen.



  • SeppJ schrieb:

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

    Richtig. Mich auch nicht. Haltet ihr mich für blöd oder was?

    kk


Anmelden zum Antworten