std::complex vs. Eigenbau



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


  • |  Mod

    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



  • Frag am besten die GCC Entwickler nach einer Begründung: http://news.gmane.org/gmane.comp.gcc.help



  • unskilled schrieb:

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

    Zufall nicht wirklich. Ich wusste dass es ne alte Schreibweise von "magic" im Englischen ist. Allerdings nicht, dass irgendein komischer Okkultist sich diese "angeeignet" hat, und es für nötig hielt daraus ein neues Wort mit leicht anderer Bedeutung zu machen.



  • conj erzeugt ein temporaeres Objekt, auch wenn es nur auf dem Stack ist, der Konstruktor wird immer aufgerufen. Der macht sich gegenueber von wenigen arithmetischen Operationen schon bemerkbar. Bei Variante 2 eben nicht. Deswegen ist das kein Vergleich zwischen zwei Implementationen fuer std::complex sondern ein Vergleich zwischen zwei Implementationen eines Skalarproduktes.

    Wenn das der Flaschenhals ist, dann weiche doch auf MMX bzw. SSE aus. Besser ist wohl aber eine Strategie, die die Anzahl der Skalarprodukte/Complex irgendwas verringert.



  • knivil schrieb:

    conj erzeugt ein temporaeres Objekt, auch wenn es nur auf dem Stack ist, der Konstruktor wird immer aufgerufen. Der macht sich gegenueber von wenigen arithmetischen Operationen schon bemerkbar.

    Die 4% wären es mir sogar wert für die hübschere Syntax. Der Übeltäter sitzt aber ganz woanders und heißt __muldc3 . Dieser Implementierung der Berechnung eines Produktes zweier komplexen Zahlen habe ich es zu verdanken, dass die Performance dermaßen in den Keller geht, dass das, worauf Du Dich beziehst, nicht ins Gewicht fällt.

    kk



  • Interessant finde ich, dass bei mir die 64-Bit Version mit std::complex deutlich schneller ist als die 32-Bit:

    32 Bit  64 Bit
    -------------+-------+---------
    std::complex | 1,67  | 0,44
    eigenbau     | 0,21  | 0,19
    

    OpenSuese 11.3 mit gcc4.5

    Lars