[C++] Mikrooptimierungs-Log

Hier können Artikel, Tutorials, Bücherrezensionen, Dokumente aller Art, Texturen, Sprites, Sounds, Musik und Modelle zur Verfügung gestellt bzw. verlinkt werden.
Forumsregeln
Möglichst sinnvolle Präfixe oder die Themensymbole nutzen.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

[C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Hallo und willkommen zu Krishtys bonbonbunter Wunderwelt der Mikrooptimierungen!

Da ich für gewöhnlich nichts anderes mache, als völlig belanglosen Quelltext rundzulutschen statt mich wirklich fruchtbaren Fortschritten zu widmen, denke ich, dass ihr meine Mikroerrungenschaften vielleicht lesen und recyclen wollt. Darum präsentiere ich hier jedes Mal, wenn ich eine tolle, aber sinnfreie Optimierung entdecke (lies: in regelmäßigen Abständen) eine kleine Analyse. Wegen meiner begrenzten Zeit und Geduld kann ich hier leider nur Erfahrungen aus Visual C++ 2010 x64 auf einem Intel Core i7 anbieten; aber ich möchte euch ermutigen, es auch mit anderen Systemen zu testen!
Ich begrüße sogleich unseren ersten Gast, ein …

Schnelles min() / max() für Gleitkommazahlen durch SSE2

… und, um es kurz zu machen: Es ist eine Lüge. Die klassische Version mit dem bedingten Sprung:

    float max(float a, float b) {
        return a > b ? a : b;
    }


ist synthetisch auf einem Core i7 etwa 70 % schneller als der extra dafür abgestellte SSE-Befehl MAXSS mit Datenabhängigkeit:

    float max(float a, float b) {
        return _mm_cvtss_f32(_mm_max_ss(_mm_set_ss(a), _mm_set_ss(b)));
    }


Je unregelmäßiger der Sprung ist, desto schlechter schneidet MAXSS ab – mit richtig schön randomisierten Werten ist der Klassiker zuweilen doppelt so schnell. (Die Werte sind synthetisch; mir fällt aber kein Grund ein, warum es sich in realen Anwendungsfällen umkehren sollte.)

Warum? Laut Intel-Handbuch schlägt MAXSS mit glatt drei Takten zu Buche; also etwas mehr, als die beiden Befehle für bedingten Sprung mit angeschlossener Kopie zusammen. Auf AMD-Hardware ist mit nur zwei Takten zu rechnen, dort erwarte ich also ähnliche Leistung wie der Klassiker – aber eben auch keine Optimierung.

Man könnte jetzt argumentieren: Hey! Das ist doch eine SSE-Funktion, die ist für paralleles Maximum von vier floats ausgelegt! Nö, is’e nicht. Das wäre MAXPS, nicht MAXSS. Aber falls man zufällig ein Register voll gepackter Zahlen parat hat, ist erstere natürlich der roxx0r schlechthin und empfehlenswert, wie immer bei SIMD. Lest dazu unbedingt diesen Nachtrag!

Was haben wir heute gelernt? Manchmal ist es auch eine Optimierung, die Optimierung sein zu lassen. Für Skeptiker ist der Benchmark-Quelltext im Spoiler (vielleicht möchte ja jemand auf AMD-Hardware testen); für alle anderen: Kommentare sind willkommen, und falls euch keine einfallen, bis zur nächsten Episode!
Testfall; kompiliert mit VC 2010 (wie man an der fehlenden Autovektorisierung sieht); getestet auf Core i7:

    size_t const len = 768 * 1024 * 1024;
    auto arr = new float[len];
    auto rand = 0xBB234C27;
    for(size_t i = 0; i < len; ++i) {
        arr = rand;
        rand += 0xCBDA77FC;
    }

    auto start = __rdtsc();

    float acc = 0.0f;
    for(size_t i = 0; i < len; i += 4) {
        acc += max(acc, arr[i+0]);
        acc += max(acc, arr[i+1]);
        acc += max(acc, arr[i+2]);
        acc += max(acc, arr[i+3]);
    }

    auto ticks = __rdtsc() - start;

    out << acc << "@" << ticks;
    __debugbreak();    float acc = 0.0f;
 xorps       xmm0,xmm0
    }


Klassiker:
    auto start = __rdtsc();
 lea         rcx,[rdi+8]
 mov         edx,0C000000h
        acc += max(acc, arr[i+0]);
 movss       xmm1,dword ptr [rcx-8]
 comiss      xmm0,xmm1
 jbe         main+0ADh (14000824Dh)
 movaps      xmm1,xmm0
 addss       xmm0,xmm1
        acc += max(acc, arr[i+1]);
 movss       xmm2,dword ptr [rcx-4]
 comiss      xmm0,xmm2
 jbe         main+0BEh (14000825Eh)
 movaps      xmm2,xmm0
 addss       xmm0,xmm2
        acc += max(acc, arr[i+2]);
 movss       xmm1,dword ptr [rcx]
 comiss      xmm0,xmm1
 jbe         main+0CEh (14000826Eh)
 movaps      xmm1,xmm0
 addss       xmm0,xmm1
        acc += max(acc, arr[i+3]);
 movss       xmm1,dword ptr [rcx+4]
 comiss      xmm0,xmm1
 jbe         main+0DFh (14000827Fh)
 movaps      xmm1,xmm0
 addss       xmm0,xmm1
    for(size_t i = 0; i < len; i += 4) {
 add         rcx,10h
 dec         rdx
 jne         main+0A0h (140008240h)
    }


Zeiten:

3248441883
3251520016
3285571953


MAXSS:

    float acc = 0.0f;
 xorps       xmm2,xmm2
    }

    auto start = __rdtsc();
 add         rdi,8
 mov         ecx,0C000000h
        acc += max(acc, arr[i+0]);
 movss       xmm0,dword ptr [rdi-8]
 movss       xmm1,xmm2
 maxss       xmm1,xmm0
 addss       xmm2,xmm1
        acc += max(acc, arr[i+1]);
 movss       xmm0,dword ptr [rdi-4]
 movss       xmm1,xmm2
 maxss       xmm1,xmm0
 addss       xmm2,xmm1
        acc += max(acc, arr[i+2]);
 movss       xmm0,dword ptr [rdi]
 movss       xmm1,xmm2
 maxss       xmm1,xmm0
 addss       xmm2,xmm1
        acc += max(acc, arr[i+3]);
 movss       xmm0,dword ptr [rdi+4]
 movss       xmm1,xmm2
 maxss       xmm1,xmm0
 addss       xmm2,xmm1
    for(size_t i = 0; i < len; i += 4) {
 add         rdi,10h
 dec         rcx
 jne         main+0A0h (13FF08240h)
    }


Zeiten:

5578030548
5539127893
5559210794
Zuletzt geändert von Krishty am 02.03.2015, 13:41, insgesamt 6-mal geändert.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Willkommen zurück. Heute mal was Einfaches, unter der alten Prämisse: Gilt für Visual C++ 2010 x64; getestet mit einem Intel Core i7.

Verdoppeln einer Gleitkommazahl

Ich spüre schon, wie ihr in Ehrfurcht erstarrt. Doch so einfach das auch klingt – gerade im Umgang mit Gleitkommazahlen ist der Compiler oft übervorsichtig (meist mit Recht!), und wir können hier schön sehen, wie man der Maschine noch was vormachen kann.

Wir beginnen wieder mit dem Klassiker:

    float doubled(float x) {
        return 2.0f * x;
    }


In den Testfall aus Folge 1 eingebaut ergibt sich folgender Maschinentext:

 …
 movss       xmm3,dword ptr [__real@40000000 (13F303480h)]
 …
        acc += doubled(arr[i+0]);
 movss       xmm1,dword ptr [rcx-8]
 mulss       xmm1,xmm3
 …


und hier rollen sich dem geneigten Pedanten die Fußnägel auf. Was da im Speziellen passiert:
  • Der Compiler legt im Read-Only-Datenabschnitt der ausführbaren Datei eine Konstante 0x40000000 (die Integerrepräsentation des float-Werts 2.0f) an.
  • Diese Konstante wird in ein Register geladen.
  • Dieses Register wird mit einem Register, das x enthält, multipliziert.
Ein Bisschen viel Arbeit für eine Multiplikation, oder? Die Konstante ist zwar, nun ja, konstant, und wird deshalb sicher keine direkten Cache Misses oder Latenzen verursachen, aber sie wird beim Laden irgendeine andere Cache-Zeile des Programms verdrängen und damit einen indirekten Miss auslösen. Außerdem macht sie den Text länger und lächelt nie und ihre Mutter zieht sie komisch an. Versuchen wir es mal anders:

    float doubled(float x) {
        return x + x;
    }

 movss       xmm0,dword ptr [rcx-8]
 addss       xmm0,xmm0


Voilà – das Laden einer Konstanten und die Belegung eines Registers gespart. Die Multiplikation wurde durch eine Addition ersetzt, die laut Intel-Handbuch auch weniger Ausführungszeit benötigt. Eine hübsche Mikrooptimierung in Zeit und Raum.

Wie viel das Ganze schneller ist, kann ich nicht sagen. Der Testfall, den ich gebastelt habe, sagt 2 % voraus. Real wird es aber deutlich mehr sein, weil
  • das Laden der Konstante im Testfall von dem Compiler aus der Schleife herausbewegt wurde, also nicht mitgemessen, wurde;
  • mir nicht einfällt, wie ich mögliche Cache-Misses zuverlässig benchen soll; und
  • die Benchmark bei so fixen Operationen wahrscheinlich durch die Speicherbandbreite begrenzt wird (von der reinen Ausführungszeit der Berechnung her sollte es nun etwa doppelt so schnell sein, ist es aber nicht).
Kurz: Die 2 % sagen bloß aus, dass in einem stark speicherdurchsatzbegrenzten Fall eine Addition schneller ist als eine Multiplikation. Ob die Verbesserung real bloß zwei oder doch 100 % erreicht, steht in den Sternen.

Jedenfalls: Wenn beim nächsten Mal etwas verdoppelt werden muss, doubled() aufrufen statt 2.0 hinzuschreiben!

P.S.: Bringt aber nur bei Gleitkommazahlen was; Ganzzahltypen werden eh von jedem Nischen-Cmpiler besser optimiert.

Bis zum nächsten Mal!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Bleib dran! Ich lese mir das gerne durch und komme darauf zurück, wenn es mal kritisch sein sollte.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Schön zu hören :) Ich denke, ich werde dieses Wochenende noch zwei Beiträge rauskramen – ich habe nämlich was mit richtig Wirkung gefunden. Das wird’s dann morgen zur Krönung geben.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Diesmal wird es wieder um einen SSE2-Befehl gehen. Bedenkt: Der Tipp wurde nur mit Visual C++ 2010 x64 auf einem Intel Core i7 getestet.

Schnellere Quadratwurzeln mit SSE2

Viele wissen nicht, dass SSE2 einen eigenen Befehl zum Berechnen von Quadratwurzeln mitbringt. Wessen CPU x64-kompatibel ist, oder in der zweiten Hälfte des ersten Jahrzehnts des ersten Jahrhunderts des dritten Jahrtausends produziert wurde, sollte ihn sich unbedingt mal angucken. Der Referenz-Benchmark wird erstmal umgebaut, um die Standardfunktion von Visual C++’ CRT zu nutzen:

    acc += sqrt(arr[i+0]);
    acc += sqrt(arr[i+1]);
    acc += sqrt(arr[i+2]);
    acc += sqrt(arr[i+3]);


Die Ausführungszeit nehmen wir als Referenz.

Schauen wir uns mal ein Stück des entstehenden Maschinentextes an:

        acc += sqrt(arr[i+3]);
 movd        xmm0,dword ptr [rdi-8]
 cvtps2pd    xmm0,xmm0
 call        sqrt (13F398E3Eh)
 unpcklps    xmm6,xmm6
 addsd       xmm0,xmm1


… und hier offenbart sich auch schon das große Problem: CVTPS2PD ist eine Konvertierung von float zu double. Die VC-CRT bietet nur eine double-Version der Funktion an; beim Ziehen jeder Wurzel wird der Wert also zu doppelter Präzision konvertiert; in doppelter Genauigkeit ausgerechnet; zu einfacher Genauigkeit zurückgerundet und dann weiterverarbeitet. Das geschieht außerdem in einer externen Funktion (wen der genaue Ablauf interessiert, der kann ja im Debugger durchgehen – u.a. werden die CPU-Features bestimmt und dementsprechend aus einer passenden Implementierung gewählt, allerdings keine, die wieder auf SQRTSD zurückgreift!) Fassen wir kurz zusammen:
  • unnötige Konvertierungen zwischen float und double sind böse
  • Sachen doppelt so genau wie nötig ausrechnen ist böse
  • Funktionsaufrufe sind böse
Der entsprechend große Vorteil des SSE2-Befehls ist, dass er auf float-Eingaben auch nur mit float-Genauigkeit arbeitet und dadurch viel Zeit spart. Ich persönlich wundere mich, warum der Befehl nicht stärker eingesetzt wird – anfangs habe ich einen Haken vermutet, konnte aber keinen finden (die Genauigkeit ist in Ordnung; die Verarbeitung von NaN, Unendlichkeiten und negativen Zahlen sieht IEEE-konform aus). Wer es weiß, teile es mir bitte mit!

Übrigens erzeugt Visual C++ bei mir minimal besseren Maschinentext, wenn ich den Wert als Referenz übergebe:

    float squareRootOf(
        float const & value // pass by reference: saves one useless 'xorps'
    ) {
        // • Copy the value to an XMM register using '_mm_set_ss()' (http://msdn.microsoft.com/en-us/library/0thxfyft).
        // • Compute the square root using '_mm_sqrt_ss()' (http://msdn.microsoft.com/en-us/library/ahfsc22d). This will
        //    generate a 'SQRTSS' instruction, which seems IEEE754-compliant (though I could not find any proof on that).
        // • Extract the result using '_mm_cvtss_f32()' (http://msdn.microsoft.com/en-us/library/bb514059).
        return _mm_cvtss_f32(_mm_sqrt_ss(_mm_set_ss(value)));
    }


 movss       xmm3,dword ptr [rdi-8]
 sqrtss      xmm3,xmm3
 addss       xmm0,xmm3


Sieht doch gleich viel besser aus – und verbraucht nur 56 % der Ausführungszeit, ist also fast doppelt so schnell!

Okay; das war minimal ungerecht: wenn sqrt() nur für double geschrieben ist, sollten wir es auch damit mal testen! In dem Fall benötigt die SSE2-Version ein zusätzliches Register und sieht folgendermaßen aus:

    double squareRootOf(
        double const & value // pass by reference: saves one useless 'xorpd'
    ) {
        // • Copy the value to an XMM register using '_mm_set_sd()' (http://msdn.microsoft.com/en-us/library/dksztbt9).
        // • A second register is required to pass a dummy value. Use 'mm_setzero_pd()' to zero it so any dependencies are
        //     broken (http://msdn.microsoft.com/en-us/library/3x8wktyc).
        // • Compute the square root using '_mm_sqrt_sd()' (http://msdn.microsoft.com/en-us/library/1994h1ay). This will
        //     generate a 'SQRTSD' instruction, which seems to be IEEE754-compliant (though I could not find any proof on that).
        // • Extract the result using '_mm_cvtsd_f64()' (http://msdn.microsoft.com/en-us/library/bb531421).
        return _mm_cvtsd_f64(_mm_sqrt_sd(_mm_setzero_pd(), _mm_set_sd(value)));
    }


Hier schneidet das handgeschriebene VC-CRT-sqrt() auf einem Core i7 exakt ein Prozent besser ab. Trotzdem würde ich mich für SQRTSD entscheiden: Obgleich ein Prozent langsamer, kommt es ohne Sprünge in Fremdbibliotheken und mit weniger Maschinentext aus. Ich gehe stark davon aus, dass es die handgeschriebene Version nur in synthetischen Benchmarks schneller ist, und dass SQRTSD durch die deutlich bessere Lokalität (ein einziger Befehl auf zwei Registern gegenüber einem KiB entfernten Maschinentexts, der zehn Register verschlingt) in allen tatsächlichen Anwendungen die schnellere Wahl sein wird.

Falls man zufällig vier Skalare in einem Register herumliegen hat, ist die SSE-Version übrigens sowieso vier- bis achtmal so schnell. Spätestens dann sollte man also zugreifen!

Das war also eine Mikrooptimierung, bei der wir deutliche Wirkung nachweisen konnten. Werden wir das beim nächsten Mal wieder schaffen? *cliffhang*
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Mikrooptimierungs-Log

Beitrag von eXile »

Krishty hat geschrieben:        // • Compute the square root using '_mm_sqrt_ss()' (http://msdn.microsoft.com/en-us/library/ahfsc22d). This will
        //    generate a 'SQRTSS' instruction, which seems IEEE754-compliant (though I could not find any proof on that).
Ha, da kann ich aber liefern:
Intel® 64 and IA-32 Architectures Software Developer’s Manual, Seite 494, http://download.intel.com/design/processor/manuals/253665.pdf hat geschrieben:SSE/SSE2/SSE3 extensions are 100% compatible with the IEEE Standard 754 for
Binary Floating-Point Arithmetic, satisfying all of its mandatory requirements (when
the flush-to-zero or denormals-are-zeros modes are not enabled).
Intel® 64 and IA-32 Architectures Software Developer’s Manual, Seite 376, http://download.intel.com/design/processor/manuals/253665.pdf hat geschrieben:IEEE 754 Compliance of SSE4.1 Floating-Point Instructions
The six SSE4.1 instructions that perform floating-point arithmetic are:
  • DPPS
  • DPPD
  • ROUNDPS
  • ROUNDPD
  • ROUNDSS
  • ROUNDSD
Dot Product operations are not specified in IEEE-754.
Und SSE 4.2 enthält keine Floating-Point-Operationen. Damit sind alle SSE-Befehle mit Floating-Point-Zusammenhang IEEE-754-konform.

Ich hätte als nächstes auf der Wunschliste eine Abhandlung zur inversen Quadratwurzel; als Lesestoff siehe hier. ;)
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

MSDN hat geschrieben:Using the true intrinsic forms implies loss of IEEE exception handling, and loss of _matherr and errno functionality; the latter implies loss of ANSI conformance.
Daher generiert MSVC unter /fp:precise Calls in die Libraryfunktionen (unter /fp:precise sind math intrisincs rein prinzipiell disabled). Mit /fp:fast bekommst du den von dir gewünschten SSE Code. Aus irgendeinem Grund scheint MSVC allerdings sqrtps statt sqrtss zu verwenden...
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

@eXile: Super, danke! Damit fällt mir echt ein Stein vom Herzen.

Die inverse Quadratwurzel ist ein schöner Wemmser. Wie im verlinkten Thread schon in der höchstbewerteten Antwort steht: Die Anweisung selber ist furchtbar ungenau; und wie man sie auf annähernd (aber nicht ganz!) so hohe Genauigkeit wie SQRTSS kriegt, beschreiben Intel selber schon im Paper. Außerdem gibt es anscheinend Probleme mit Sonderwerten, beispielsweise bei sqrt(0).

Vor allem sehe ich aber schon, dass es dabei nicht bei eine Stunde Ausprobieren, Testfälle hinhacken, benchen und fertig bleiben wird – ich würde mindestens alle 2^32 float-Werte einmal durchjagen und auf ULPs vergleichen und die Anweisungen stundenlang umsortieren und … ;) Ich reihe ein, aber erstmal ganz hinten, sorry.

@dot: Perfekt – klingt absolut einleuchtend. Ich arbeite eigentlich nie mit /fp:fast, weil ich jede Menge Unendlichkeiten und NaN rumschiebe. Das hätte ich wohl wirklich testen sollen …
Warum SQRTPS genutzt wird, weiß ich auch nicht. Vielleicht wird damit nochmal zusätzlich eine Abhängigkeit aufgebrochen … ich kann es leider dieses Wochenende nicht testen, weil ich vor einer anderen CPU sitze.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Hallo und willkommen zurück! Nachdem wir bisher nur *Mikro*optimierungen durchgeackert haben, werde ich heute mal einen schönen fetten Brocken präsentieren – nämlich eine Mikrooptimierung, die einen Compiler-Fehler in Visual C++ 2010 umschifft:

Überflüssige Destruktoren weglassen

Und direkt ab dafür – wir beginnen mit meiner plumpen 3D-Vektor-Datenstruktur:

    template <
        typename Scalar
    > struct Vector<Scalar, 3> {
        Scalar x;
        Scalar y;
        Scalar z;
    };


Schlicht und schnell, wie ich es liebe. Um es vorweg zu nehmen: Das ist die optimierte Version.

Den Fehler, um den es geht, habe ich zufällig entdeckt, weil einige Leute – früher auch ich – gern der Explizität halber einen Destruktor definieren, selbst, wenn die Klasse an sich keinen braucht. Dabei ist es egal, wie viel sinnloses Zeug der Destruktor erledigt (einige Leute nullen z.B. gern alle Attribute vor der Zerstörung – halloooohooo! Nach dem Destruktor ist das Objekt weg und nie mehr zugreifbar; es ist egal, was drinsteht!) oder ob er einfach nur leer ist. Aber schauen wir einfach mal, was passiert, wenn wir der Datenstruktur dies hinzufügen:

    ~Vector() { }

Die folgende unscheinbare Zeile (sie lässt sich effizenter berechnen, aber das ist Stoff für eine spätere Folge)

    auto const relativeVelocity = dotProductOf(normalized(direction), normalized(velocity));

ohne Destruktor:

    movss       xmm0,xmm15
    movaps      xmm1,xmm13
    movaps      xmm5,xmm12
    movaps      xmm4,xmm8
    movaps      xmm6,xmm11
    movaps      xmm7,xmm10
    sqrtss      xmm0,xmm0
    mulss       xmm1,xmm13
    movaps      xmm3,xmm10
    divss       xmm5,xmm0
    divss       xmm6,xmm0
    divss       xmm4,xmm0
    movaps      xmm0,xmm9
    mulss       xmm0,xmm9
    mulss       xmm7,xmm10
    addss       xmm7,xmm0
    movaps      xmm0,xmm9
    addss       xmm7,xmm1
    movaps      xmm1,xmm13
    movss       xmm2,xmm7
    sqrtss      xmm2,xmm7
    divss       xmm1,xmm2
    divss       xmm0,xmm2
    divss       xmm3,xmm2
    mulss       xmm1,xmm6
    mulss       xmm0,xmm4
    mulss       xmm3,xmm5
    addss       xmm3,xmm0
    addss       xmm3,xmm1


und mit:

    mov         rdx,rsi
    [color=FF2010]call        Math::normalized<3> (13F188580h)[/color]
    lea         rdx,[direction]
    [color=FF2010]call        Math::normalized<3> (13F188580h)[/color]
    movss       xmm2,dword ptr [rax+4]
    mulss       xmm2,dword ptr [rbx+4]
    movss       xmm0,dword ptr [rax]
    mulss       xmm0,dword ptr [rbx]
    addss       xmm2,xmm0
    movss       xmm0,dword ptr [rax+8]
    mulss       xmm0,dword ptr [rbx+8]
    addss       xmm0,xmm2


Hier sind deutliche Unterschiede zu erkennen. Was ist passiert?

Offenbar genießen Klassen, die einen Destruktor besitzen, in VC++ einen Sonderstatus (unwindable) – sogar, wenn der D’tor garnichts tut; es geht nur darum, dass einer definiert wurde. (Der Fehler ist Microsoft bekannt und soll in einer zukünftigen Version behoben werden. Offenbar hat Microsoft meinen Bug Report mittlerweile gelöscht. Yay! Wer VC++ 2010 und VC++ 2012 nebeneinander installiert hat, ist eingeladen, die Kompilate zu vergleichen!)

Insbesondere wird für alle Funktionen, die einen unwindable Rückgabewert besitzen, Inlining deaktiviert. Wird also einer häufig genutzten Klasse – wie in diesem Fall dem 3D-Vektor – ein D’tor hinzugefügt, kommt das damit gleich, für die meistgenutzten Funktionen Inlining zu deaktivieren. Auch die kleinste Popelfunktion wird nun nicht mehr geinlinet:

    Vector<float, 3> const operator / (
        Vector<float, 3> const &    dividend,
        Scalar const &              divisor
    ) {
        Vector<float, 3> const result = {
            dividend.x / divisor,
 movss       xmm2,dword ptr [r8]
 movss       xmm0,dword ptr [rdx]
            dividend.y / divisor,
 movss       xmm1,dword ptr [rdx+4]
            dividend.z / divisor
        };
        return result;
 mov         rax,rcx
 divss       xmm0,xmm2
 divss       xmm1,xmm2
 movss       dword ptr [rcx],xmm0
 movss       xmm0,dword ptr [rdx+8]
 movss       dword ptr [rcx+4],xmm1
 divss       xmm0,xmm2
 movss       dword ptr [rcx+8],xmm0
    }
 ret


Mit Inlining würden hier bloß drei DIVSS-Befehle stehen.

Wie viel das tatsächlich bewirkt, hängt von der Anwendung ab. Ich habe hier eine Direct3D-Anwendung mit hoher CPU-Rechenlast; im oben beschriebenen Fall – der 3D-Vektor-Klasse einen überflüssigen D’tor verpassen – fällt die Aktualisierungsrate von 57 auf 50 Bilder pro Sekunde, oder um 14 %. Das ist, wohlgemerkt, keine Messung einer einzelnen Funktion, sondern des gesamten Programms. Die heutige Mikrooptimierung hat also eine Wirkung, für die sich einige Leute ein Bein abreißen würden!

Was wir daraus lernen: Auch Compiler sind fehleranfällige, komplexe Programme; und wie sich Quelltext auf sie auswirkt, ist schwer vorherzusagen. Generell sollte alles immer so einfach wie gerade möglich gehalten werden – VC++ gerät durch einen überflüssigen D’tor aus dem Tritt; bei anderen Compilern könnte es sonstwas sein. Raus mit allem, was nicht unbedingt nötig ist!

Und damit bis zum nächsten Wochenende!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Mikrooptimierungs-Log

Beitrag von eXile »

Krishty hat geschrieben:Der Fehler ist Microsoft bekannt und soll in einer zukünftigen Version behoben werden. Offenbar hat Microsoft meinen Bug Report mittlerweile gelöscht. Yay! Wer VC++ 2010 und VC++ 2012 nebeneinander installiert hat, ist eingeladen, die Kompilate zu vergleichen!
Am Arsch. (Zu Dokumentationszwecken: Die Seite war hier, und da stand irgendwas von kein schwerwiegender Fehler, wird frühestens in Visual C++ 2042 gefixt, usw. :evil:)

Damit wir wissen, worüber wir hier reden: Ich habe folgenden Code unter Visual C++ 2010 und Visual C++ 2012 RC (mit allen Updates jeweils) auf x64 im Release kompiliert, und als einzige Änderung /fp:fast in den Projekteinstellungen vorgenommen.

Code: Alles auswählen

#include <iostream>
#include <cmath>

template <
	typename Scalar, 
	size_t Dimension
> struct Vector;

template <
	typename Scalar
> struct Vector<Scalar, 3> {
	Scalar x;
	Scalar y;
	Scalar z;

//	~Vector() {};
};

template <
	typename Scalar
> Scalar dotProductOf(
	Vector<Scalar, 3> a, 
	Vector<Scalar, 3> b
) {
	return a.x * b.x + a.y * b.y + a.z * b.z;
}

template <
	typename Scalar
> Vector<Scalar, 3> normalized(
	Vector<Scalar, 3> v
) {
	Scalar norm = sqrt(dotProductOf(v, v));

	Vector<Scalar, 3> const result = {
		v.x / norm, 
		v.y / norm, 
		v.z / norm
	};

	return result;
}

float test(
	float d1, 
	float d2, 
	float d3,
	float v1, 
	float v2, 
	float v3
) {
	Vector<float, 3> direction = { d1, d2, d3 };
	Vector<float, 3> velocity = { v1, v2, v3 };
	auto const relativeVelocity = dotProductOf(normalized(direction), normalized(velocity));

	return relativeVelocity;
}

int main(int argc, char * argv[])
{
	float d1, d2, d3, v1, v2, v3;

	std::cin >> d1 >> d2 >> d3 >> v1 >> v2 >> v3;
	std::cout << test(d1, d2, d3, v1, v2, v3) << std::endl;

	return 0;
}
Visual C++ 2010 ohne ~Vector():

Code: Alles auswählen

test:
000000013FAC1000  mov         rax,rsp  
000000013FAC1003  sub         rsp,68h  
000000013FAC1007  movaps      xmmword ptr [rax-18h],xmm6  
000000013FAC100B  movaps      xmmword ptr [rax-28h],xmm7  
000000013FAC100F  movaps      xmmword ptr [rax-38h],xmm8  
000000013FAC1014  movaps      xmm8,xmm0  
000000013FAC1018  movaps      xmmword ptr [rax-48h],xmm9  
000000013FAC101D  movaps      xmmword ptr [rax-58h],xmm10  
000000013FAC1022  movss       xmm9,dword ptr [__real@3f800000 (13FAC21E0h)]  
000000013FAC102B  movaps      xmm10,xmm1  
000000013FAC102F  movaps      xmmword ptr [rsp],xmm11  
000000013FAC1034  movaps      xmm11,xmm2  
000000013FAC1038  movss       xmm2,dword ptr [v2]  
000000013FAC1041  movaps      xmm7,xmm9  
000000013FAC1045  movaps      xmm4,xmm2  
000000013FAC1048  movaps      xmm0,xmm3  
000000013FAC104B  mulss       xmm0,xmm3  
000000013FAC104F  mulss       xmm4,xmm2  
000000013FAC1053  addss       xmm0,xmm4  
000000013FAC1057  movss       xmm4,dword ptr [v3]  
000000013FAC1060  movaps      xmm5,xmm4  
000000013FAC1063  mulss       xmm5,xmm4  
000000013FAC1067  addss       xmm0,xmm5  
000000013FAC106B  sqrtss      xmm1,xmm0  
000000013FAC106F  movaps      xmm0,xmm10  
000000013FAC1073  divss       xmm7,xmm1  
000000013FAC1077  mulss       xmm0,xmm10  
000000013FAC107C  movaps      xmm1,xmm11  
000000013FAC1080  movaps      xmm5,xmm7  
000000013FAC1083  movaps      xmm6,xmm7  
000000013FAC1086  mulss       xmm5,xmm2  
000000013FAC108A  mulss       xmm1,xmm11  
000000013FAC108F  mulss       xmm6,xmm3  
000000013FAC1093  movaps      xmm2,xmm8  
000000013FAC1097  mulss       xmm2,xmm8  
000000013FAC109C  mulss       xmm7,xmm4  
000000013FAC10A0  addss       xmm2,xmm0  
000000013FAC10A4  addss       xmm2,xmm1  
000000013FAC10A8  sqrtss      xmm0,xmm2  
000000013FAC10AC  divss       xmm9,xmm0  
000000013FAC10B1  movaps      xmm1,xmm9  
000000013FAC10B5  movaps      xmm0,xmm9  
000000013FAC10B9  mulss       xmm9,xmm11  
000000013FAC10BE  mulss       xmm0,xmm10  
000000013FAC10C3  mulss       xmm9,xmm7  
000000013FAC10C8  mulss       xmm1,xmm8  
000000013FAC10CD  movaps      xmm7,xmmword ptr [rax-28h]  
000000013FAC10D1  movaps      xmm8,xmmword ptr [rax-38h]  
000000013FAC10D6  movaps      xmm10,xmmword ptr [rax-58h]  
000000013FAC10DB  mulss       xmm0,xmm5  
000000013FAC10DF  mulss       xmm1,xmm6  
000000013FAC10E3  movaps      xmm6,xmmword ptr [rax-18h]  
000000013FAC10E7  movaps      xmm11,xmmword ptr [rsp]  
000000013FAC10EC  addss       xmm0,xmm1  
000000013FAC10F0  addss       xmm0,xmm9  
000000013FAC10F5  movaps      xmm9,xmmword ptr [rax-48h]  
000000013FAC10FA  add         rsp,68h  
000000013FAC10FE  ret  
Visual C++ 2010 mit ~Vector():

Code: Alles auswählen

test:
000000013F311000  push        rbp  
000000013F311002  mov         rbp,rsp  
000000013F311005  sub         rsp,60h  
000000013F311009  movss       dword ptr [rbp-20h],xmm0  
000000013F31100E  movss       xmm0,dword ptr [rbp+30h]  
000000013F311013  movss       dword ptr [rbp-30h],xmm3  
000000013F311018  lea         rdx,[rbp-40h]  
000000013F31101C  lea         rcx,[rbp-10h]  
000000013F311020  movss       dword ptr [rbp-2Ch],xmm0  
000000013F311025  movss       dword ptr [rbp-1Ch],xmm1  
000000013F31102A  movss       xmm1,dword ptr [rbp+38h]  
000000013F31102F  mov         rax,qword ptr [rbp-30h]  
000000013F311033  mov         qword ptr [rbp-40h],rax  
000000013F311037  movss       dword ptr [rbp-28h],xmm1  
000000013F31103C  movss       dword ptr [rbp-18h],xmm2  
000000013F311041  mov         eax,dword ptr [rbp-28h]  
000000013F311044  mov         dword ptr [rbp-38h],eax  
000000013F311047  call        normalized<float> (13F311180h)  
000000013F31104C  lea         rdx,[rbp-30h]  
000000013F311050  mov         ecx,dword ptr [rax]  
000000013F311052  mov         dword ptr [rbp-40h],ecx  
000000013F311055  mov         ecx,dword ptr [rax+4]  
000000013F311058  mov         eax,dword ptr [rax+8]  
000000013F31105B  mov         dword ptr [rbp-38h],eax  
000000013F31105E  mov         rax,qword ptr [rbp-20h]  
000000013F311062  mov         dword ptr [rbp-3Ch],ecx  
000000013F311065  mov         qword ptr [rbp-30h],rax  
000000013F311069  mov         eax,dword ptr [rbp-18h]  
000000013F31106C  lea         rcx,[rbp-20h]  
000000013F311070  mov         dword ptr [rbp-28h],eax  
000000013F311073  call        normalized<float> (13F311180h)  
000000013F311078  mov         ecx,dword ptr [rax]  
000000013F31107A  movss       xmm0,dword ptr [rbp-40h]  
000000013F31107F  movss       xmm1,dword ptr [rbp-3Ch]  
000000013F311084  movss       xmm2,dword ptr [rbp-38h]  
000000013F311089  mov         dword ptr [rbp-30h],ecx  
000000013F31108C  mov         ecx,dword ptr [rax+4]  
000000013F31108F  mov         eax,dword ptr [rax+8]  
000000013F311092  mulss       xmm0,dword ptr [rbp-30h]  
000000013F311097  mov         dword ptr [rbp-2Ch],ecx  
000000013F31109A  mov         dword ptr [rbp-28h],eax  
000000013F31109D  mulss       xmm1,dword ptr [rbp-2Ch]  
000000013F3110A2  mulss       xmm2,dword ptr [rbp-28h]  
000000013F3110A7  addss       xmm0,xmm1  
000000013F3110AB  addss       xmm0,xmm2  
000000013F3110AF  add         rsp,60h  
000000013F3110B3  pop         rbp  
000000013F3110B4  ret  
Visual C++ 2012 RC ohne ~Vector():

Code: Alles auswählen

test:
000007F68F2F1240  mov         rax,rsp  
000007F68F2F1243  sub         rsp,68h  
000007F68F2F1247  movss       xmm4,dword ptr [v2]  
000007F68F2F1250  movaps      xmmword ptr [rax-18h],xmm6  
000007F68F2F1254  movaps      xmmword ptr [rax-28h],xmm8  
000007F68F2F1259  movaps      xmmword ptr [rax-38h],xmm9  
000007F68F2F125E  movaps      xmmword ptr [rax-48h],xmm10  
000007F68F2F1263  movaps      xmm9,xmm0  
000007F68F2F1267  mulss       xmm4,xmm4  
000007F68F2F126B  movss       xmm10,dword ptr [__real@3f800000 (07F68F2F3400h)]  
000007F68F2F1274  movaps      xmmword ptr [rax-58h],xmm11  
000007F68F2F1279  movaps      xmm11,xmm1  
000007F68F2F127D  movaps      xmm8,xmm10  
000007F68F2F1281  xorps       xmm1,xmm1  
000007F68F2F1284  movaps      xmmword ptr [rsp],xmm12  
000007F68F2F1289  movaps      xmm12,xmm2  
000007F68F2F128D  movaps      xmm2,xmm0  
000007F68F2F1290  mulss       xmm2,xmm9  
000007F68F2F1295  movaps      xmm6,xmm3  
000007F68F2F1298  movaps      xmm0,xmm11  
000007F68F2F129C  mulss       xmm0,xmm11  
000007F68F2F12A1  mulss       xmm6,xmm3  
000007F68F2F12A5  addss       xmm2,xmm0  
000007F68F2F12A9  addss       xmm6,xmm4  
000007F68F2F12AD  movss       xmm4,dword ptr [v3]  
000007F68F2F12B6  xorps       xmm0,xmm0  
000007F68F2F12B9  movaps      xmm5,xmm4  
000007F68F2F12BC  mulss       xmm5,xmm4  
000007F68F2F12C0  addss       xmm6,xmm5  
000007F68F2F12C4  sqrtss      xmm1,xmm6  
000007F68F2F12C8  divss       xmm8,xmm1  
000007F68F2F12CD  movaps      xmm1,xmm12  
000007F68F2F12D1  mulss       xmm1,xmm12  
000007F68F2F12D6  movaps      xmm6,xmm8  
000007F68F2F12DA  movaps      xmm5,xmm8  
000007F68F2F12DE  mulss       xmm5,dword ptr [v2]  
000007F68F2F12E7  mulss       xmm6,xmm3  
000007F68F2F12EB  mulss       xmm8,xmm4  
000007F68F2F12F0  addss       xmm2,xmm1  
000007F68F2F12F4  sqrtss      xmm0,xmm2  
000007F68F2F12F8  divss       xmm10,xmm0  
000007F68F2F12FD  movaps      xmm1,xmm10  
000007F68F2F1301  movaps      xmm0,xmm10  
000007F68F2F1305  mulss       xmm10,xmm12  
000007F68F2F130A  mulss       xmm0,xmm11  
000007F68F2F130F  mulss       xmm10,xmm8  
000007F68F2F1314  mulss       xmm1,xmm9  
000007F68F2F1319  movaps      xmm8,xmmword ptr [rax-28h]  
000007F68F2F131E  movaps      xmm9,xmmword ptr [rax-38h]  
000007F68F2F1323  movaps      xmm11,xmmword ptr [rax-58h]  
000007F68F2F1328  mulss       xmm0,xmm5  
000007F68F2F132C  mulss       xmm1,xmm6  
000007F68F2F1330  movaps      xmm6,xmmword ptr [rax-18h]  
000007F68F2F1334  movaps      xmm12,xmmword ptr [rsp]  
000007F68F2F1339  addss       xmm0,xmm1  
000007F68F2F133D  addss       xmm0,xmm10  
000007F68F2F1342  movaps      xmm10,xmmword ptr [rax-48h]  
000007F68F2F1347  add         rsp,68h  
000007F68F2F134B  ret  
Visual C++ 2012 RC mit ~Vector():

Code: Alles auswählen

test:
000007F6B5CC1240  push        rbp  
000007F6B5CC1242  mov         rbp,rsp  
000007F6B5CC1245  sub         rsp,80h  
000007F6B5CC124C  movss       dword ptr [rbp-50h],xmm0  
000007F6B5CC1251  movss       xmm0,dword ptr [rbp+30h]  
000007F6B5CC1256  movss       dword ptr [rbp-60h],xmm3  
000007F6B5CC125B  movaps      xmmword ptr [rsp+70h],xmm6  
000007F6B5CC1260  lea         rdx,[rbp-40h]  
000007F6B5CC1264  lea         rcx,[rbp-60h]  
000007F6B5CC1268  movaps      xmmword ptr [rsp+60h],xmm7  
000007F6B5CC126D  movaps      xmmword ptr [rsp+50h],xmm8  
000007F6B5CC1273  movss       dword ptr [rbp-5Ch],xmm0  
000007F6B5CC1278  movss       dword ptr [rbp-4Ch],xmm1  
000007F6B5CC127D  movss       xmm1,dword ptr [rbp+38h]  
000007F6B5CC1282  mov         rax,qword ptr [rbp-60h]  
000007F6B5CC1286  mov         qword ptr [rbp-40h],rax  
000007F6B5CC128A  movss       dword ptr [rbp-58h],xmm1  
000007F6B5CC128F  movss       dword ptr [rbp-48h],xmm2  
000007F6B5CC1294  mov         eax,dword ptr [rbp-58h]  
000007F6B5CC1297  mov         dword ptr [rbp-38h],eax  
000007F6B5CC129A  call        normalized<float> (07F6B5CC1800h)  
000007F6B5CC129F  lea         rdx,[rbp-40h]  
000007F6B5CC12A3  lea         rcx,[rbp-50h]  
000007F6B5CC12A7  movss       xmm6,dword ptr [rax]  
000007F6B5CC12AB  movss       xmm8,dword ptr [rax+4]  
000007F6B5CC12B1  movss       xmm7,dword ptr [rax+8]  
000007F6B5CC12B6  mov         rax,qword ptr [rbp-50h]  
000007F6B5CC12BA  mov         qword ptr [rbp-40h],rax  
000007F6B5CC12BE  mov         eax,dword ptr [rbp-48h]  
000007F6B5CC12C1  mov         dword ptr [rbp-38h],eax  
000007F6B5CC12C4  call        normalized<float> (07F6B5CC1800h)  
000007F6B5CC12C9  mulss       xmm8,dword ptr [rax+4]  
000007F6B5CC12CF  mulss       xmm6,dword ptr [rax]  
000007F6B5CC12D3  mulss       xmm7,dword ptr [rax+8]  
000007F6B5CC12D8  addss       xmm8,xmm6  
000007F6B5CC12DD  movaps      xmm6,xmmword ptr [rsp+70h]  
000007F6B5CC12E2  addss       xmm8,xmm7  
000007F6B5CC12E7  movaps      xmm7,xmmword ptr [rsp+60h]  
000007F6B5CC12EC  movaps      xmm0,xmm8  
000007F6B5CC12F0  movaps      xmm8,xmmword ptr [rsp+50h]  
000007F6B5CC12F6  add         rsp,80h  
000007F6B5CC12FD  pop         rbp  
000007F6B5CC12FE  ret  
Ohne ein Assembler-Magier zu sein, hier die Kurzversion:
  • Visual C++ 2012 RC sortiert ein paar Befehle um
  • Visual C++ 2012 RC generiert um eine Instruktion längeren Code bei nicht vorhandenem Destruktor, ansonsten fünf Instruktionen kürzeren Code. Ziemlich egal.
  • Visual C++ 2012 RC generiert noch immer Funktionsaufrufe bei leerem Destruktor :evil:
Bild
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Mikrooptimierungs-Log

Beitrag von eXile »

Nachtrag: Gilt auch für die Visual Studio Ultimate 2012 90-day trial. Wird damit in der distributierten Version nicht gefixt sein.

So haben wir das ja mal wieder gerne, einfach den Bugreport löschen aber nichts fixen. Werden sich vermutlich mit „Connect-Datenbank migrieren“ oder so herausreden. :evil:
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Diskussion zur Nutzung des Visual Studio-C++-Compilers hier herausgetrennt und dorthin verschoben: http://zfx.info/viewtopic.php?f=4&t=2503
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Heute geht es mal einem wirklich hinterlistigen kleinen Detail an den Kragen:

Gleitkommatypen konsistent halten

Was ist suboptimal am folgenden (semantisch richtigen) Stück Quelltext?

    float value = foo();
    if(0.1 <= value) {
        bar(value);
    }


Unter x86 garnichts, unter x64 schon: Das if vergleicht eine double-Konstante mit einem float-Wert.

Unter x86 ist das egal, weil die FPU intern sowieso mit 80-Bit-Gleitkommazahlen arbeitet, value wird also sowieso in 80 Bits vorliegen und 0.1 wird beim Laden implizit zu 80 Bits konvertiert. Der Speicherdurchsatz der Ladeoperation wird zwar 32 Bits größer sein, das hat aber bei einer einzelnen Konstante keine Auswirkung auf die Geschwindigkeit.

x64 wird value hingegen tatsächlich nur als 32-Bit-Gleitkommazahl in den SSE-Registern halten und 0.1 in 64 Bits laden. Weil es keine native Anweisung gibt, die eine 32- mit einer 64-Bit-Gleitkommazahl vergleicht, wird value zu 64 hochkonvertiert werden. (Der umgekehrte Weg, 0.1 auf 32 Bits zu reduzieren, wird vom Compiler nicht genommen werden, weil dabei signifikande Genauigkeit verloren ginge. Selbst, falls foo() intern mit 64 Bits gerechnet und nur das Ergebnis auf 32 Bits reduziert hat, wird diese Reduktion nicht wegoptimiert werden, weil sie beobachtbare und möglicherweise beabsichtigte Wirkung aufs Programm hat.)

Für die Konvertierung und den Vergleich emittiert Visual C++ die folgenden Anweisungen:

    unpcklps    xmm3,xmm3
    cvtps2pd    xmm0,xmm3
    comisd      xmm0,xmm2


Dabei verteilt UNPCKLPS die Zahl (grob gesagt) aufs ganze Register und wird wahrscheinlich eingesetzt, um das Register von Überbleibseln vorheriger Anweisungen zu reinigen, die sonst bei der Konvertierung eine Floating-Point Exception auslösen könnten, weil die Konvertierung nur auf die zwei unteren Werte eines Registers zugleich durchführbar ist (die skalare Version wäre langsamer). Es schlägt mit einem Takt zu Buche. CVTPS2PD führt die eigentliche Konvertierung durch. Die Latenz beträgt 2–3 Takte. Danach wird verglichen (zwei Takte, für 32-Bit-Gleitkommazahlen wäre die Latenz aber gleich).

Damit hat ein fehlendes f hinter der Konstanten das if um drei Takte verzögert. Ähnliches passiert eigentlich bei jeder Rechnung, die 32- und 64-Bit-Genauigkeit durcheinanderwirft. Wer ausschließlich mit 32-Bit-Genauigkeit arbeitet, könnte also mal einen Blick über alle Konstanten und die Typen der Zwischenergebnisse riskieren.

Leider habe ich genau dafür keine kohärente Lösung gefunden. Es ist dank Regulärer Ausdrücke [eeew!] möglich, in Visual C++ alle double-Literale im Quelltext aufzulisten:
  • STRG+Shift+F
  • [0-9]+[.][0-9]+[^f]
  • Find Options -> Use -> Regular Expressions
Dann eben alle durchgehen und prüfen, ob sie legitim sind. Der Compiler sollte eigentlich eine vollständige Liste aller Konvertierungen zusammenstellen können; da ranzukommen habe ich aber noch keinen Weg gefunden. Bis dahin bleibt nur: Weiterhin immer fleißig den Maschinentext prüfen!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Vielleicht sollte man noch erwähnen: Das Problem hat man natürlich auch unter x86, sobald man SSE aktiviert. Unter x64 ist SSE nur implizit schon an.

Einer der Gründe, wieso ich das hab:

Code: Alles auswählen

namespace math
{
  namespace constants
  {
    template <typename T>
    T one();
    template <>
    inline float one<float>() { return 1.0f; }
    template <>
    inline double one<double>() { return 1.0; }
    template <>
    inline long double one<long double>() { return 1.0; }

    template <typename T>
    T zero();
    template <>
    inline float zero<float>() { return 0.0f; }
    template <>
    inline double zero<double>() { return 0.0; }
    template <>
    inline long double zero<long double>() { return 0.0; }

    template <typename T>
    T pi();
    template <>
    inline float pi<float>() { return 3.1415926535897932384626434f; }
    template <>
    inline double pi<double>() { return 3.1415926535897932384626434; }
    template <>
    inline long double pi<long double>() { return 3.1415926535897932384626434; }
  }
}
Vom beliebten #define PI 3.14 ist auf jeden Fall abzuraten, nicht nur weil es ein böses Makro ist. Auch ein const double pi = 3.14 führt potentiell zu ineffizientem Code...
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Im Augenblick habe ich es ebenfalls so. Funktionen werden aber manchmal auch nicht richtig optimiert – zugegebenermaßen hatte ich noch nie den Fall, in dem Visual C++ eine Funktion return 3.14…; nicht optimiert hätte, aber überrascht wäre ich von sowas nicht. Ich plane schon seit langem dies, und hatte nur nie die Zeit, es durchzuziehen:

    template <> struct Constants<float> {
        static float const pi;
    };

    …

    float const Constants<float>::pi = 3.14…f;


Wo wir gerade bei Konstanten sind: Als nächstes sollte ich zeigen, wie man INF und NaN hard-codet. Dabei gibt es nämlich auch Visual C++-Optimizer-Ausfälle, dass einem die Kinnlade runterklappt.
dot hat geschrieben:Vielleicht sollte man noch erwähnen: Das Problem hat man natürlich auch unter x86, sobald man SSE aktiviert. Unter x64 ist SSE nur implizit schon an.
Nicht immer – bloß, weil man SSE aktiviert, wird SSE nicht für alles benutzt. Meiner Erfahrung nach macht der Compiler weiterhin alle Arithmetik mit der FPU und nur Datenschieberei und Intrinsics mit SSE. Das ist ja das große Problem daran, mit Visual C++ auf einem Atom zu programmieren (wo SSE gegenüber der FPU stark zu bevorzugen ist, man es Visual C++ aber niemals entlockt kriegt).
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Was ich heute vorstelle, hat mich echt Nerven gekostet. Begrüßen Sie mit mir …

Overhead-freie Gleitkomma-Konstanten für Unendlichkeiten und NaN

Aber bitte nicht mit Applaus, sondern Buhrufen, denn niemand liebt diese Arschlöcher. Zur Erklärung der naive Weg:

    float infinite = std::numeric_limits<float>::infinity();

Wie wir schon früher gelernt haben, sind Funktionsaufrufe schlecht – erst recht Funktionsaufrufe in Fremdbibliotheken. In diesem Fall ist infinity() in der Visual C++-Laufzeitbibliothek implementiert. Für den Compiler ist das ein Ereignishorizont; er hat keine Kenntnis darüber, ob die Implementierung hinter diesem Aufruf Nebenwirkungen hat oder was der Aufruf zurückgeben wird. Er wird also jegliche Optimierung an diesem Aufruf aufgeben.

Wie können wir also die Konstante selber herstellen?


Ein Blick in die Definition des IEEE754-Gleitkomma-Standards verrät, dass genau ein Wert als (positive) Unendlichkeit gilt: Der, bei dem das Vorzeichen der Zahl 0 ist, der Exponent komplett 1 und die Mantisse 0. Für eine 32-Bit-Gleitkommazahl wäre dies also die Bit-Repräsentation 0x7F800000. Kriegen wir die in eine Konstante?

    static float const infinity = reinterpret_cast<float const &>(0x7F800000);

Fehler: reinterpret_cast<>() verlangt eine Lvalue, Literale sind aber Rvalues! Also mit einer Lvalue:

    static unsigned int const binaryInfinity = 0x7F800000;
    static float const infinity = reinterpret_cast<float const &>(binaryInfinity);


Es kompiliert, aber es ist nicht, was wir wollen. Der kritische Test ist in diesem Zusammenhang das Setzen eines Haltepunkts in der Zeile:
  • Falls in der Zeile ein Haltepunkt gesetzt werden kann, und das Programm beim Start in dieser Zeile hält, bedeutet das: Der Compiler konnte die Variable nicht zur Kompilierzeit ausrechnen und hat stattdessen eine Funktion geschrieben, die sie initialisiert. Diese Funktion wird beim Programmstart vor main(), zur Zeit der Initialisierung globaler Objekte, aufgerufen und berechnet den Wert. (Laufzeitinitialisierung.)
  • Sonst bedeutet das: Der Compiler hat die Variable beim Kompilieren fertig berechnet. (Statische Initialisierung.)
Im obigen Text ist ersteres der Fall: Der Ausdruck ist nun syntaktisch korrekt, aber der Compiler kann ihn nicht statisch auflösen. Wir haben also den Sprung in die Visual C++-Laufzeitbibliothek gespart, und der Wert, den wir wollen, steht nun in einer globalen Variable – aber weil der Compiler den Wert nicht statisch bestimmen konnte, wird immernoch kein Ausdruck, der mit dieser Variable arbeitet, optimiert werden. (Abgesehen von einer Verbesserung: Da unsere Unendlichkeit nun der Zugriff auf eine Variable ist statt der Aufruf einer DLL-Funktion, kann der Compiler den kompletten Aufruf wegoptimieren, falls der umgebende Ausdruck sonst keine Wirkung hat.)

Geht es vielleicht ohne reinterpret_cast<>()?


Wir können stattdessen auch mal den Umweg über eine union probieren:

static union {
    unsigned int asInt;
    float asFloat;
} const binaryInfinity = { 0x7F800000 };
static float const infinity = binaryInfinity.asFloat;


Wieder nichts – auch hier spuckt der Compiler wieder Text aus, um infinity bei der Initialisierung des Programms zu laden. Das bedeutet, dass er den Wert von binaryInfinity.asFloat nicht statisch bestimmen kann. Nichts gewonnen.

Wenn wir mit Bitmustern nicht weiterkommen, machen wir es doch über die Arithmetik! Wie erzeugt man denn normalerweise solche speziellen Werte?


Eine Unendlichkeit erzeugt man in Gleitkommaarithmetik durch eine Division durch 0. Das ist tatsächlich so – im Gegensatz zur Mathematik, wo x÷0 undefiniert ist, ist x÷0 im IEEE754-Gleitkommastandard wohldefiniert. Dieser feine Unterschied ist unsere Chance, wird uns aber erstmal das Genick brechen:

    float const infinity = 1.0f / 0.0f;

Visual C++ wird das nicht kompilieren. Ursache ist eine Spitzfindigkeit im C-Standard: Demnach darf keine Konstante mit Werten initialisiert werden, die mathematisch undefiniert sind. Die Betonung liegt hier auf mathematisch: Im IEEE-Gleitkommastandard ist die Operation sehr wohl definiert, aber weil sie nicht auch mathematisch definiert ist, verbietet C++ diesen Ausdruck.
(GCC wird hier mit einer Warnung kompilieren, habe ich gehört).


Nächster Versuch: Wir wissen, dass Visual C++ mathematische Funktionen nativ verarbeiten kann – sin(), cos(), usw sind Intrinsics und werden bei entsprechender Compiler-Einstellung aufgelöst:

    float const infinity = -log(0.0f);

Haltepunkt setzen, kompilieren, starten, und – es funktioniert! Endlich! Alle Ausdrücke, in denen wir mit infinity arbeiten, werden nun vom Compiler schon bei der Übersetzung des Programms aufgelöst.

Bis das eines Tages aufhört. Ich habe diese Methode schon hier als Lösung präsentiert. Das war, bevor ich rausgefunden habe, dass das Auflösen intrinsischer Funktionen bei Visual C++ offenbar einer Heuristik folgt.

Ich habe etwa zehn Mal verifiziert, dass die Methode oben klappt. Dummerweise konnte ich sie auch zehn Mal falsifizieren. Wann Visual C++ den Ausdruck auflöst und wann nicht, scheint stark von der Benutzung abzuhängen: Wie oft, ob in Schleifen oder nicht, usw usf. Bei einer Code Base von 100.000 Zeilen hat sich das Verhalten manchmal innerhalb von Stunden geändert. Wir haben hier also nur die Möglichkeit, nicht die Garantie.


Intrinsics sind also ein Trugschluss. Zufällig bin ich bei OldNewThing darauf gestoßen, wie sich das Windows-Team intern diese Konstanten holt:

   float const infinity = 3.4028234e38f * 2.0f;

Das ist der Ansatz, den wir mit ÷0 begonnen, aber nicht zuendegeführt haben: Erst wird eine Konstante angelegt, die ganz am oberen Ende des Wertebereichs einer float ist. Indem die dann nochmal skaliert wird, entsteht ein unendlicher Wert. Im Gegensatz zur Division durch Null ist dieser Ausdruck aber mathematisch gültig, und wird deshalb vom Compiler geschluckt. Leider wird eine Warnung wegen des Überlaufs emittiert, die muss stummgeschaltet werden.


Der endgültige Text für float-Sonderwerte sieht also so aus:

    #pragma warning(push)
    #pragma warning(disable: 4056)
    float const positiveInfinity = 3.4028234e38f * 2.0f;
    float const negativeInfinity = 3.4028234e38f * -2.0f;
    float const NaN = 3.4028234e38f * 2.0f * 0.0f;
    #pragma warning(pop)


Damit werden alle Ausdrücke, die positiveInfinity, negativeInfinity oder NaN involvieren, nach bestem Wissen und Gewissen (und Gleitkommasorgfaltseinstellung des Compilers) statisch optimiert.

Tut nicht das:

    float const positiveInfinity = 3.4028234e38f * 2.0f; // noch O.K.
    float const negativeInfinity = -positiveInfinity; // FALSCH!
    float const NaN = positiveInfinity * 0.0f; // auch O.K.


Das wird mit /fp:precise nicht funktionieren. Der Grund ist eine geradezu niedliche Festverdrahtung des Visual C++-Compilers, die meine besser Hälfte entdeckt hat: Gleitkommamultiplikationen, die eine benannte Variable x beinhalten, werden nur optimiert, wenn der Multiplikand 0.0f oder 1.0f ist. -x? Bewirkt Laufzeitinitialisierung. x * 2.0f? Laufzeitinitialisierung. x * -1.0f? Laufzeitinitialisierung. Toll, oder?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Ui, das ist wirklich gut zu wissen, danke für die Info!
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Mal ein etwas anderer Beitrag: Ich möchte kurz drei kleine Helfer vorstellen, die ich ständig benutze – meine liebsten

Tools.


Visual Studio Disassembly Window
1_vs.png
1_vs.png (9.35 KiB) 30716 mal betrachtet
Idealerweise sollte man von jeder Funktion, die man geschrieben hat, den entstandenen Maschinentext prüfen. Zwar lassen sich viele vom kryptischen Aussehen abschrecken, aber so schwer ist es wirklich nicht – alles mit mov drin ist eine Zuweisung, Funktionsaufrufe sind meist was mit call, und die Registernamen sieht man automatisch. Auch ohne alle Latenzen auswendig zu kennen kann man erkennen, wenn eine Stelle mehr Befehle bewirkt, als man erwartet hätte.

Für alle, die es nicht kennen: In die Disassembly kommt man, indem man das Programm im Debugger startet; anhält; mit der rechten Maustaste auf die Stelle im Quelltext klickt, die man analysieren möchte; und Go To Disassembly auswählt.

Das ist unabhängig vom Haltepunkt – d.h., man kann einen Haltepunkt an den Anfang der main() setzen und von jeder Zeile den Maschinentext abrufen, ohne die Zeile tatsächlich ausführen zu müssen. Die Schritt-für-Schritt-Ausführung (F10 / F11) kann das Verständnis des Maschinentexts aber stark erleichtern.


7-Zip
2_7z.png
2_7z.png (5.85 KiB) 30715 mal betrachtet
Das klingt unorthodox, aber ich benutze es ständig. Der Punkt ist, dass 7-Zip auch ausführbare Dateien öffnen kann und dann die einzelnen Abschnitte der Datei anzeigt. Alle paar Builds klicke ich also rechts auf meine Exe; wähle 7-Zip -> Open Archive; und schaue mir die Größe der Abschnitte an. Falls ich nur 20 Zeilen geschrieben habe, aber plötzlich 50 KiB mehr Maschinentext da sind, weiß ich, dass ich irgendwo was falsch gemacht habe. Für Anfänger eine Erklärung der Abschnitte:
  • .text – Der tatsächliche Maschinentext, der ausgeführt wird. Wächst, wenn ihr Funktionen schreibt.
  • .rdata – Konstanten (Read-Only Data). Wächst, wenn ihr Strings, Konstanten, konstante Arrays usw. hinzufügt. Wenn das übermäßig groß ist, habt ihr vielleicht versehentlich ein Array in einem Header definiert und deshalb 100 identische Kopien davon im Programm.
  • .data – Auch als .bss bekannt. Globale und statische Arrays, die aber nicht konstant sind oder nicht statisch initialisiert wurden. Alles, was hier allokiert wird, muss noch zur Laufzeit initialisiert werden – falls ihr also ein Array von float-Koeffizienten deklariert und das const vergesst, wächst dieser Abschnitt. Der Abschnitt sollte möglichst klein sein, weil ihr so viel Arbeit wie möglich vom Programmstart zur Kompilierung (also zu .rdata) verlagern solltet.
  • .pdata (nur x64) – Tabelle mit den Ausnahmebehandlungsfunktionen. Hat eigentlich keine Signifikanz; wächst mit der Anzahl der Blätter eures Aufrufbaums (also mit der Anzahl der Funktionen, die keine anderen Funktionen aufrufen).
  • .reloc – Relocation Table. Hat ebenfalls keine große Signifikanz. Aus Sicherheitsgründen landen Programme seit Windows Vista immer an einer anderen Adresse im Speicher; damit die Programme trotzdem noch ihre globalen Variablen finden, werden hier alle Stellen verzeichnet, an denen globale Zugriffe stattfinden. Beim Laden des Programms geht Windows die Liste durch und passt alle verzeichneten Adressen an. Wächst mit der Länge eures Texts und dem Anteil globaler / statischer Datenzugriffe darin.
Sizer

Sizer ist ein Programm, das anhand der Debug-Informationen (.pdb) eine vollständige Liste aller Symbole eines Programms mit geschätzter Größe anfertigt. Man kann also nachsehen, welche Funktion wie groß ist; wie viele statische Initialisierungsfunktionen da sind und zu welchen Variablen sie gehören; welche Quelldateien den meisten Text produzieren usw.

Ursprünglich wurde es für die Demo-Szene entwickelt (von ryg, der mit .theprodukkt .kkieger entwickelt hat). Ich benutze es alle paar Tage, um meine Programme daraufhin zu analysieren, ob irgendwo was unbeabsichtigt gewuchert ist, ob unnötige Symbole nicht wegoptimiert wurden, und welche Programmfunktionen welchen Anteil am Maschinentext haben.

Leider ist die verlinkte Version noch auf Visual Studio 2003, 2005 und 2008 zugeschnitten. Visual C++ 2010-tauglich macht ihr es, indem ihr in src\pdbfile.cpp in Zeile 305 die UUID von msdia100.dll nachtragt, und auch Zeile 594 ergänzt. Ich würde die entsprechenden Daten ja gern selber hier posten und auch meine kompilierte Version anbieten, aber die sind leider auf meinem Produktivsystem. Ich kann sie nächstes Wochenende nachreichen. Hier ist meine Visual Studio 2010-/2012-taugliche Version:

[Die Dateierweiterung exe wurde deaktiviert und kann nicht länger angezeigt werden.]

Die Benutzung ist denkbar einfach: Die Kommandozeile

    sizer foo.exe >> foo.txt

speichert eine Analyse von foo.exe in foo.txt.

Gegenüber dem Original habe ich in pdbfile.cpp (306/577) die neuen Laufzeitbibliotheken eingetragen (B86AE24D-BF2F-4ac9-B5A2-34B14E4CE11D für msdia100.dll; 761D3BCD-1304-41D5-94E8-EAC54E4AC172 für msdia110.dll); die Größenbeschränkung geändert (damit man alle Symbole sieht und nicht nur die großen); und die Formatierung geändert (B statt KB).
Zuletzt geändert von Krishty am 21.07.2013, 13:14, insgesamt 4-mal geändert.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von CodingCat »

Sehr schön! Mir war nicht klar, dass 7-Zip exe-Dateien öffnet. Wenn man nicht von Anfang an kontinuierlich den Speicherbedarf verfolgt hat, wartet allerdings wohl erstmal etwas Arbeit mit dem Sizer auf einen. ;)
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Ui, das mit 7-zip wusste ich auch net, das is ja mal endspraktisch. :D

Edit: Wobei mir gerade vorkommt, dass ich wohl aus Versehen schon ein paar mal eine .exe mit 7-zip geöffnet hab, aber wohl net registriert hab, was ich dann gesehen hab...
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Mikrooptimierungs-Log

Beitrag von eXile »

Meiner Meinung nach ist es fast aussichtslos, ohne Verzicht auf die CRT und die STL, und ohne dass man von Anfang an die Code-Größe kontrolliert hat, einen vollständigen Überblick zu bekommen. Was natürlich nicht bedeutet, dass man zumindest die Dateigröße trotzdem (durch Behandlung der dicksten Brocken) stark verringern kann.

Das mit 7-zip war von meiner Seite aus bereits bekannt: Ich benutze es, um Setup-Exe-Dateien zu entpacken (manchmal kann 7-zip das jeweilige Setup-Format einlesen); immer wenn es fehlschlägt, kommt eine solche Section-Auflistung wie oben. ;)
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ja; 7-Zip kann fast alles irgendwie öffnen. Aus EXEs und DLLs kann man die Abschnitte extrahieren und Ressourcen wie Manifest und Symbole; aus Flash- und Video-Dateien die ent-interleave-ten Ton- und Videospuren; aus Setups die zu installierenden Dateien; aus CD-/DVD-/HDD-Images die Dateien, usw usf. Ich meine auch, im Unterstützungsforum irgendwas von BIOS-Containerformaten gelesen zu haben. Ich persönlich fände interessant, ob all die zusätzlichen Informationen, die 7-Zip durch das Unterstützen hunderter Containerformate erhalten kann, auch effektiv in die Kompression einfließen …
eXile hat geschrieben:Meiner Meinung nach ist es fast aussichtslos, ohne Verzicht auf die CRT und die STL, und ohne dass man von Anfang an die Code-Größe kontrolliert hat, einen vollständigen Überblick zu bekommen. Was natürlich nicht bedeutet, dass man zumindest die Dateigröße trotzdem (durch Behandlung der dicksten Brocken) stark verringern kann.
Ja. Bei einem Projekt, an dem ich nun seit etwa einem Jahr arbeite, habe ich zum Glück alles Aufgezählte einhalten können: Ich minimiere die CRT-Benutzung; nutze keine STL; greife durch eine möglichst dünne Schicht direkt auf die WinAPI zu und kontrolliere regelmäßig alle Importe und Abhängigkeiten durch den Dependency Walker.

Schade, dass ich die CRT noch nicht ganz entfernen konnte: Die Kontrolle mit VMMap offenbart, dass die CRT intern Memory-Mapped Files mit Buchstabenkonvertierungstabellen vorhält, obwohl ich nicht eine einzige Textverarbeitungsroutine nutze. Je genauer man analysiert, was passiert, desto gruseliger wird, was da für Unmengen an nutzlosem Müll rumtreiben.

Jedenfalls: Es ist fast aussichtslos, aber nicht unmöglich. Ich kenne fast jedes Symbol meines Programms, jeden Import, fast jeden Ausführungspfad. Ich habe sogar einen groben Überblick über alle meine Konstanten im Kopf. Die Software ist kompakt, sauschnell, robust und fast fehlerfrei. Nicht einmal der Himmel kann uns aufhalten, seit schon Menschen ihre Füße auf den Mond gesetzt haben.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Krishty hat geschrieben:Nicht einmal der Himmel kann uns aufhalten, seit schon Menschen ihre Füße auf den Mond gesetzt haben.
:(

http://www.nasa.gov/topics/people/featu ... _obit.html
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Krishty hat geschrieben:Im Augenblick habe ich es ebenfalls so. Funktionen werden aber manchmal auch nicht richtig optimiert – zugegebenermaßen hatte ich noch nie den Fall, in dem Visual C++ eine Funktion return 3.14…; nicht optimiert hätte, aber überrascht wäre ich von sowas nicht. Ich plane schon seit langem dies, und hatte nur nie die Zeit, es durchzuziehen:

    template <> struct Constants<float> {
        static float const pi;
    };

    …

    float const Constants<float>::pi = 3.14…f;
So ähnlich hatte ich es zuvor, allerdings hatte ich analog zu std::numeric_limits static member functions für die einzelnen Konstanten. Warum ich dann zu dieser Methode umgestiegen bin, weiß ich leider nicht mehr wirklich, vermutlich hat's mir einfach besser gefallen. Wie ich gerade lernen musste, hat die Methode mit dem struct allerdings den Vorteil, dass folgender, nervender Bug umschifft wird: https://connect.microsoft.com/VisualStu ... t-argument
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Mal mit was weitermachen, was viele nicht wissen:

Zeiger-Casts können Zeit kosten (und ich spreche nicht von dynamic_cast)

Das passiert, wenn eine Klasse mehrere Basisklassen hat. Der Compiler wird die endgültige Klasse aus den Basisklassen komponieren – stark vereinfacht gesagt, indem er sie hintereinander im Speicher anlegt. Das bedeutet zugleich, dass die Basisklassenobjekte innerhalb der endgültigen Klasse unterschiedliche Adressen haben – der Grund, warum man Zeiger nicht via reinterpret_cast zur Basisklassenzeigern konvertieren sollte (denn das würde die Adresse erhalten und deswegen aufs falsche Objekt zeigen), sondern via static_cast oder dynamic_cast.

    class Serializable {
    public:
        virtual ~Serializable() { }
    };

    class Object {
    public:
        virtual ~Object() { }
    };

    class StaticObject : public Serializable, public Object { };

    …
    StaticObject * toStaticObject  = new StaticObject(); // 0xC8860
    Serializable * toSerializable  = toStatic;           // 0xC8860
    Object *       toObject        = toStatic;           // 0xC8868 (+8 B)


Damit wäre dann auch erklärt, warum Zeiger-Casts bei polymorphen Typen Zeit kosten können: unter Umständen muss die Adresse des Zielobjekts neu berechnet werden. Ins Spiel kommt das, wenn man Listen nach einem bestimmten Objekt durchsucht:

    bool isInScene(Object * pObject) {

        // falls es ein StaticObject ist, in der entsprechenden Liste suchen
        if(nullptr != dynamic_cast<StaticObject *>(pObject)) {

            // hier lineare Suche; std::map<> und Konsorten hätten aber das gleiche Problem
            for(auto const & staticObject : myStaticObjects) {
                if(pObject == &staticObject) {
                    return true;
                }
            }

        }

        // das gleiche für DynamicObjects , usw.

        return false;
    }


An der unterstrichenen Stelle wird ein Zeiger auf die Basisklasse mit einem Zeiger auf die endgültige Klasse verglichen. Der Compiler wandelt das implizit zu einem Vergleich zweier Basisklassenzeiger um. Wie wir aber wissen, muss dafür gerechnet werden:

    if(pObject == &staticObject) {
        lea rcx,[rax+8] // 8 Bytes aufaddieren
        cmp rbx,rcx
        je  isInScene+63h


Und das direkt vor einem bedingten Sprung! Unter Visual Studio 2012 ist die Situation noch finsterer, dort wird vor jedem Cast ein Nullzeigertest durchgeführt: (Nachtrag: Cat hat mir mittlerweile erklärt, dass der wahrscheinlich da ist, um zu garantieren, dass ein gecasteter Nullzeiger auch Null bleibt, und Visual C++ hier wohl einfach nicht rafft, dass die Adresse niemals Null sein wird. Ein weiterer Grund, warum Zeiger-Casting kosten kann!)

    if(pObject == &staticObject) {
        test rax,rax
        je   isInScene+4Bh
        lea  rcx,[rax+8]
        jmp  isInScene+4Dh
        xor  ecx,ecx
        cmp  rbx,rcx
        je   isInScene+63h

Wir können die Funktion optimieren, indem das zu findende Objekt direkt zum endgültigen Typ gecastet wird, damit die Vergleiche auf demselben Typ operieren:

    if(auto pStaticObject = dynamic_cast<StaticObject *>(pObject)) {

        for(auto const & staticObject : staticObjects) {
            if(pStaticObject == &staticObject) {
                return true;
            }
        }

    }

Hier reduziert sich der komplette Vergleich zu:

        cmp rax,rcx
        je  isInScene+49h


und wenn man Visual Studios Unzulänglichkeit in Betracht zieht, ist die Schleife gerade auf 29 % zusammengeschrumpft. In der Ausführungsgeschwindigkeit zeigt sich das so:

    unoptimiert: 51924000 Ticks (100 %)
    optimiert: 25968329 Ticks (50 %)

Das Array-Beispiel ist natürlich arg konstruiert, aber wir sprechen hier ja auch von Mikrooptimierungen. Wer also oft Adressen polymorpher Typen vergleichen muss, weiß nun, wie er in bestimmten Situationen die Geschwindigkeit verdoppeln kann.

Übrigens zeigt das auch, dass man sich nicht auf Compiler verlassen kann – es gäbe hier zumindest zwei Möglichkeiten, die Optimierung automatisiert durchzuführen, aber Visual Studio macht es im Gegenteil durch den zusätzlichen Test noch langsamer.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ich habe den Tools eine aktuelle Version des Sizers hinzugefügt, damit ihr nicht selber die UIDs recherchieren und reinkompilieren müsst.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Kurze Frage, weil ich davon keinen neuen Thread aufmachen will: kennt sich jemand mit dem Mikrooptimierten Verhalten bei verschieden großen unsigned integer aus?

Ich ringe hier gerade mal wieder mit dem Sparse Voxel Tree vom letzten Jahr. Und um den schnell zu bekommen, nutze ich extrem viel Rumgetrickse mit Bitschiebereien. Und komme dabei immer wieder dazu, mal 8 Bit zu speichern und zu verrechnen, um die dann einige Operationen später auf 64bit aufzuspreizen und mit was anderem zu verrechnen. Und meine Grundfrage dazu lautet:

Lohnt es sich, den jeweils kleinstmöglichen Datentyp einzusetzen? Oder geht dabei zuviel verloren, weil der Compiler intern Extra-Operationen einfügt, um die restlichen Bits konsistent auf 0 zu halten?
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Auf modernem x86 und x86-64 sind kleine Integertypen an sich genau so schnell wie große. Für das Auffüllen mit Nullen gibt es einen eigenen Befehl (MOVZX, move with zero-extend), der genau so schnell ist wie ein normales MOV.

Jede Operation auf kleinen Zahlen benötigt ein Byte mehr Platz im Maschinentext – das Kompilat wird also größer; aber das sollte sich nicht auswirken, so lange du nicht dadurch limitiert bist.

Andererseits sparst du vielleicht Platz im Daten-Cache, wenn du auf kleine Zahlen zurückgreifst. Kleine Zahlen könnten auch zusätzliche Optimierungen durch besseres Wissen über den Werteumfang ermöglichen.

Ich weiß es also nicht; es gibt Gründe dafür und dagegen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Ahso, trotzdem Danke für die Einsichten.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Noch schnelleres min() / max() für Gleitkommazahlen … immernoch mit SSE2

Ihr erinnert euch noch an den ersten Beitrag? Mit diesem max():

    float max(float a, float b) {
        return _mm_cvtss_f32(_mm_max_ss(_mm_set_ss(a), _mm_set_ss(b)));
    }


Mir ist da letztens was aufgefallen:
  • Der Wert liegt, so oder so, in einem 128-Bit-Register. Auch wenn nur 32 Bits davon benutzt werden. _mm_max_ss() operiert nur auf einer float darin.
  • Sein Gangbang-Bruder _mm_max_ps() nagelt aber vier floats auf einmal.
  • Da am Ende nur eine Spur aus dem vierspurigen Register gezogen wird, sind die beiden erstmal völlig austauschbar: Im Zweifel steht in den drei übrigen floats halt Müll, aber die werden eh verworfen.
Nun ist es so, dass die skalare und die Vektor-Version unterschiedlich lang kodiert sind:
  • MAXPS: 0F 5F E9
  • MAXSS: F3 0F 5F 69 F0
Skalar-MAXSS ist fett und hässlich, darum kriegt es nicht mehr floats ab. Das ist bei fast allen SSE-Befehlen so: Die Vektor-Version ist nicht nur kompakter als die Skalar-Version, weil sie weniger Rechenschritte durchführt, sondern weil die einzelnen Schritte im Schnitt auch ein Viertel kürzer kodiert sind. Vielleicht meinte Intel, dass die eh vor allem in optimierten Programmen zum Einsatz kommen, und man sie deshalb besser optimieren solle. Aber ich schweife ab.

Trotz der unterschiedlichen Länge haben beide, gemäß Dokumentation, identische Latenz, identischen Durchsatz, und nutzen den selben Port. Das bedeutet, dass man ohne Geschwindigkeitseinbußen ein kleineres Programm erzeugen kann, indem man die Vektor-Version nutzt.

Das habe ich gerade ausprobiert und bin überrascht worden: Die Vektor-Version ist in Benchmarks auf meinem fünf Jahre alten Core i7 sogar doppelt so schnell wie die Skalar-Version. (Eine Datenabhängigkeit weniger, weil kein alter Register-Inhalt rüberkopiert werden muss?) Also ändern wir max() zu …

    float max(float a, float b) {
        return _mm_cvtss_f32(_mm_max_ps(_mm_set_ss(a), _mm_set_ss(b)));
    }


… und min() natürlich auch. Und genießen ein 0,1 % kleineres und 0,0001 % schnelleres Programm.

Das gilt übrigens nicht für alle Befehle, dass Skalar- und Vektorversion gleich schnell sind – bspw. ist die Quadratwurzel auf vier statt einer Spur langsamer. Immer erst ins Handbuch gucken; im Zweifel testen. Oder umgekehrt.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Antworten