std::complex vs. Eigenbau


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



  • 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



  • ogni42 schrieb:

    Hab den Code bei mir mal mit VS2010 durchlaufen lassen:
    ...
    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

    Selbst mit diesen Einstellungen scheint Version2 fast 2mal so schnell zu laufen, wie Version1 bei mir. Fp, Fa, Fo, Fd habe ich einfach mal weggelassen.

    kk



  • Selbst mit diesen Einstellungen scheint Version2 fast 2mal so schnell zu laufen, wie Version1 bei mir. Fp, Fa, Fo, Fd habe ich einfach mal weggelassen.

    Bei mir ist es ein Faktor 1,29. Benutzt Du denn VS 2010? Ich nehme mal an, dass dort in der StdLib durch Move-Semantik dort noch einiges an Zeit raus geholt werden kann, weil temporäre Kopien weg fallen.

    Edit: Habe jetzt noch beim inlining "Any suitable" eingestellt und - um den Einfluss der Schleifen und Funktionsaufrufe zu reduzieren Size erhöht und passes verkleinert:

    VecSize = 100000
    passes = 5000
    Version 1 = 3.703
    Version 2 = 3.672
    Rate = 1.00844
    Result1 = 499683+i496250
    Result2 = 499683+i496250

    Also beide Versionen praktisch gleich schnell!



  • Nach ein bisschen experimentieren (und genauerer Messmethodik) ist g++ bei mir ca. 95% langsamer bei std::complex ohne -ffast-math als die andere Variante, mit -ffast-math sind es nur ca. 4%.

    Der Verantwortliche Schalter scheint dabei -fcx-limited-range zu sein

    gcc Manual 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.

    Die beiden Varianten sind also tatsächlich nicht äquivalent, wobei ich vermute, dass in den meisten Anwendungsfällen (wegen der Eigenart der EIngabedaten) -fcx-limited-range eine sichere Option ist.

    Offenbar bildet die Standardbibliothek von g++ std::complex auf den C99-Typ _Complex ab, bei anderen Compilern ist das möglicherweise nicht so.

    Mit -fcx-limited-range (ohne -ffast-math) differieren die Zeiten bei mir nur um ca. 1-2 %.



  • ogni42 schrieb:

    Selbst mit diesen Einstellungen scheint Version2 fast 2mal so schnell zu laufen, wie Version1 bei mir. Fp, Fa, Fo, Fd habe ich einfach mal weggelassen.

    Bei mir ist es ein Faktor 1,29. Benutzt Du denn VS 2010?

    Ja. Vielleicht sind unsere Rechner auch einfach zu verschieden. Ich hab hier schon ne recht alte Krücke im Moment (Intel Petium 4). Mit all den Optimierungen ist std::complex nur halb so schnell.

    ogni42 schrieb:

    Ich nehme mal an, dass dort in der StdLib durch Move-Semantik dort noch einiges an Zeit raus geholt werden kann, weil temporäre Kopien weg fallen.

    Nein. Das braucht man nicht annehmen. Es gibt keinen guten Grund, std::complex<double> mit benutzerdefinierten Copy/Move Funktionen auszustatten. Die vom Compiler generierten Funktionen sind schon optimal.

    ogni42 schrieb:

    Edit: Habe jetzt noch beim inlining "Any suitable" eingestellt

    Habe ich auch gerade. Keine Änderung.

    ogni42 schrieb:

    Also beide Versionen praktisch gleich schnell!

    Kann ich nicht reproduzieren auf meiner Kiste. Habe hier immer ein Verhältnis von etwa 1:2 in der Laufzeit.

    camper schrieb:

    Nach ein bisschen experimentieren (und genauerer Messmethodik) ist g++ bei mir ca. 95% langsamer bei std::complex ohne -ffast-math als die andere Variante, mit -ffast-math sind es nur ca. 4%.

    Das scheint auch stark Rechnerabhängig zu sein. Bei mir sieht es wie gesagt noch viel schlimmer aus. Mit -O3 -march=native -mtune=native immerhin noch 1:4.

    camper schrieb:

    Der Verantwortliche Schalter scheint dabei -fcx-limited-range zu sein

    Das steht auch in etwa so in der Diskussion, die ich von der ersten Seite aus verlinkt hatte.

    Wen's interessiert, ich habe im Projekt jetzt in einer cpp-Datei (in etwa) folgendes stehen:

    #ifdef USE_NATIVE_COMPLEX_OPERATORS
    
    /// computes t += conj(a)*b
    static inline void cmac(complx_d & t, complx_d const& a, complx_d const& b)
    {
       t += conj(a) * b;
    }
    
    #if defined(__GNUG__) && !defined(__FAST_MATH__)
    #warning "use of native complex operators without -ffast_math might degrade performance"
    #endif
    
    #else // manual handling of real and imaginary parts
    
    /// computes t += conj(a)*b
    static inline void cmac(complx_d & t, complx_d const& a, complx_d const& b)
    {
       double const ar = real(a);
       double const ai = imag(a);
       double const br = real(b);
       double const bi = imag(b);
       t = complx_d(
          real(t) + (ar*br+ai*bi),
          imag(t) + (ar*bi-ai*br)
       );
    }
    
    #endif
    

    Ich sehe keine Notwendigkeit noch weiter zu experimentieren. Vielleicht auf einem anderen Rechner dann wieder... Per Default nehme ich die zweite Variante.

    kk