[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: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

  1. Danke, das ist hervorragend! Branchless Binary Search kannte ich noch nicht.
  2. Ich habe IACA seit einigen Wochen auf der Platte liegen, hatte aber glücklicherweise noch keine Zeit, es zu testen – jetzt weiß ich, dass die Timings ähnlich absurd geraten sind wie damals im AMD GPU Shader Analyzer; danke!
  3. Ich habe schon oft gemerkt, dass Code, der in jeder Hinsicht schneller sein sollte, plötzlich total abstinkt. OR -1 habe ich in dem Zusammenhang oft gesehen, aber nie wirklich wahrgenommen – für so bescheuert, da keinen Dependency Breaker zu nutzen, habe ich bei MS keinen gehalten. Fuck.
  4. Branch Prediction ist mit VC ein *riesen* Problem, für das ich auch neben POGO keine Lösung kenne; es frustriert mich auch von Mal zu Mal mehr. Ich hatte vorletzte Woche wieder so einen Fall, urks, einfach zum Kotzen.
  5. Ich hatte 2011 einen wenig professionellen Vergleich von Binary vs Linear gemacht und kam auf einen Break-Even bei rund 400 Elementen. Passt ungefähr zu den Daten im Artikel.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Krishty hat geschrieben:Benutzt in Visual C++ keine Initializer Lists.

  struct SRGBC_8888 { unsigned char r, g, b, c; };

  result.ambient = { 0xFF, 0xFF, 0xFF, 0xFF };
  result.diffuse = { 0xFF, 0xFF, 0xFF, 0xFF };
  result.specular = { 0xFF, 0xFF, 0xFF, 8 }; // exponent 1: 255 * sqrt(1 / 1024)
  result.emissive = { 0xFF, 0xFF, 0xFF, 0xFF };


Erzeugt:

Code: Alles auswählen

40 55                push        rbp  
48 8B EC             mov         rbp,rsp  
83 4D 10 FF          or          dword ptr [rbp+10h],0FFFFFFFFh  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
83 4D 10 FF          or          dword ptr [rbp+10h],0FFFFFFFFh  
89 41 18             mov         dword ptr [rcx+18h],eax  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
89 41 1C             mov         dword ptr [rcx+1Ch],eax  
C7 45 10 FF FF FF 08 mov         dword ptr [rbp+10h],8FFFFFFh  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
83 4D 10 FF          or          dword ptr [rbp+10h],0FFFFFFFFh  
89 41 20             mov         dword ptr [rcx+20h],eax  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
89 41 24             mov         dword ptr [rcx+24h],eax  
48 8B C1             mov         rax,rcx  
5D                   pop         rbp  
C3                   ret  
wat

  result.ambient.r = 0xFF;
  result.ambient.g = 0xFF;
  result.ambient.b = 0xFF;
  result.ambient.c = 0xFF;

  result.diffuse.r = 0xFF;
  result.diffuse.g = 0xFF;
  result.diffuse.b = 0xFF;
  result.diffuse.c = 0xFF;

  result.specular.r = 0xFF;
  result.specular.g = 0xFF;
  result.specular.b = 0xFF;
  result.specular.c = 8; // exponent 1: 255 * sqrt(1 / 1024)

  result.emissive.r = 0xFF;
  result.emissive.g = 0xFF;
  result.emissive.b = 0xFF;
  result.emissive.c = 0xFF;


Erzeugt:

Code: Alles auswählen

48 83 49 18 FF       or          qword ptr [rcx+18h],0FFFFFFFFFFFFFFFFh  
48 8B C1             mov         rax,rcx  
83 49 24 FF          or          dword ptr [rcx+24h],0FFFFFFFFh  
C7 41 20 FF FF FF 08 mov         dword ptr [rcx+20h],8FFFFFFh  
C3                   ret
70 % kürzer. Er hat sogar zwei benachbarte 32-Bit-FFFFFFFFs zu einem 64-Bit-mov mit der 8-Bit-Konstante -1 zusammengefasst :o

fml

Und wo wir gerade dabei sind: fuck alle anderen. Wenn ich sowas einchecke, kommt immer irgendein Schlaumeier, der meint, er könne es besser machen weil eeeew Wiederholungen und eeew unleserlich und mimimimi. Irgendwann fällt mir dann auf, dass ein Modul doppelt so groß ist wie vorher, und dann darf ich die ganzen „Verbesserungen“ rückgängig machen.
Wow. Also … mandrills Bug Report ist letzten Monat anerkannt worden:
Hi, thanks for the feedback and the small repro case. I confirm the codegen you are seeing. In the "good" case, the optimizer sees a sequence of 1-byte stores to adjacent memory locations and is able to easily merge the stores into the instruction sequence you see.

In the "bad" case, we end up seeing four 1-byte assignments to a local variable, then a 4-byte store of that local. Then another 4 1-byte assignments to a local varibale, then a 4-byte store of that local. etc.

The optimization that would normally address this is copy propagation, and while we have plenty of copy propagation in the optimizer, it is clearly not firing properly in the case you provided. We'll look into addressing this optimizer shortcoming in an upcoming release.

I'll let this MSConnect item open until we fix the issue.

Thanks,
Eric Brumer
Microsoft Visual C++ Team
Im aktuellen Optimizer wird die ausgeschriebene Variante aber schon wieder zerstört. Damals war das „perfekte“ Disassembly durch Ausschreiben:

Code: Alles auswählen

48 83 49 18 FF       or          qword ptr [rcx+18h],0FFFFFFFFFFFFFFFFh  
48 8B C1             mov         rax,rcx  
83 49 24 FF          or          dword ptr [rcx+24h],0FFFFFFFFh  
C7 41 20 FF FF FF 08 mov         dword ptr [rcx+20h],8FFFFFFh  
C3                   ret
70 % kürzer. Er hat sogar zwei benachbarte 32-Bit-FFFFFFFFs zu einem 64-Bit-mov mit der 8-Bit-Konstante -1 zusammengefasst :o
Jetzt (VS 2017.3) erzeugt ähnlicher Code:

Code: Alles auswählen

C6 44 01 24 FF       mov         byte ptr [rcx+rax+24h],0FFh  
49 03 C9             add         rcx,r9  
49 3B CC             cmp         rcx,r12  
7C EF                jl          triangulateExtrusion+638h (024E70h)  
33 C9                xor         ecx,ecx  
48 8B 43 08          mov         rax,qword ptr [rbx+8]  
C6 44 01 18 FF       mov         byte ptr [rcx+rax+18h],0FFh  
49 03 C9             add         rcx,r9  
49 3B CC             cmp         rcx,r12  
7C EF                jl          triangulateExtrusion+64Bh (024E83h)  
33 C9                xor         ecx,ecx  
48 8B 43 08          mov         rax,qword ptr [rbx+8]  
C6 44 01 1C FF       mov         byte ptr [rcx+rax+1Ch],0FFh  
49 03 C9             add         rcx,r9  
49 3B CC             cmp         rcx,r12  
7C EF                jl          triangulateExtrusion+65Eh (024E96h)
48 8B 43 08          mov         rax,qword ptr [rbx+8]  
33 C9                xor         ecx,ecx  
C6 40 20 FF          mov         byte ptr [rax+20h],0FFh  
48 8B 43 08          mov         rax,qword ptr [rbx+8]  
C6 40 21 FF          mov         byte ptr [rax+21h],0FFh  
48 8B 43 08          mov         rax,qword ptr [rbx+8]  
C6 40 22 FF          mov         byte ptr [rax+22h],0FFh  
48 8B 43 08          mov         rax,qword ptr [rbx+8]  
C6 40 23 08          mov         byte ptr [rax+23h],8  
Kleiner Tipp: Das sind Schleifen.

VC hat echt pro Schreibvorgang eine kleine for-Schleife erzeugt und schreibt pro Iteration ein Byte. Mein WTF-Vokabular reicht nicht mehr aus. Ich dachte lange, ich hätte versehentlich einen Debug Build kompiliert oder sowas.

Nachtrag: Ich hab’s. Ich habe durch eine Referenz auf einen Zeiger geschrieben statt direkt durch eine Referenz oder direkt durch einen Zeiger. VS hat dadurch irrtümlicherweise angenommen, die Adresse könne sich ändern oder so.

Ich sage nochmal gaaanz ganz deutlich: Legt für alles eine lokale Variable an. Niemals geschachtelte Referenzen mehrmals hinschreiben.

Code: Alles auswählen

// SCHLECHT:
a->b->c = 1;
a->b->d = 2;

// GUT:
auto & b = *a->b;
b.c = 1;
b.d = 2;
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Artificial Mind hat geschrieben:Keine Ahnung ob wir sowas hier schon hatte, aber ich finde es passt hervorragend:

Hochoptimierte Linear-Search vs. Binary-Search

Beinhaltet ASM-level analyse und Späße wie branchless binary search.
Nachtrag dazu: Es ist inkompatibel zu /LARGEADDRESSAWARE in 32-Bit-Builds (ptrdiff_t läuft zu negativer Zahl über, sobald das Array >= 2^31 Elemente lang ist; danach ist der Right Shift undefined. Lässt sich aber einfach beheben.)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

mandrill hat geschrieben:Hat ein bisschen gedauert (hab im Moment zu Hause kein Internet) ... mein Geduldvorrat für heute ist aufgebraucht, aber nach dem üblichem Kampf gegen Connect gibt's da jetzt nen Bug-Report.
Der Bug Report, den mandrill vor über einem Jahr gepostet hat, wurde vor geraumer Zeit gelöscht, aber heute habe ich ihn zufällig im neuen System wiedergefunden: https://developercommunity.visualstudio ... ssign.html

Status leider zurückgestellt weil keine Priorität. Ihr solltet also weiterhin keine Initializer Lists zuweisen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
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 »

Kurzer Nachtrag, weil ich das irgendwo hier von Krishty aufgeschnappt habe:

Wenn man assert im Release als __assume() umdefiniert, kann der Compiler manchmal hübsche Sachen machen. Zum Beispiel sowas hier:

Code: Alles auswählen

tassert(0 == count % 4);
for( size_t a = 0; a < count; ++a )
  irgendwelche_mathe_sachen();
Wird im Release-Build zu __assume(0 == count % 4);. Und der Compiler teil-entrollt daraufhin die Schleife und vektorisiert die Berechnung für vier Elemente auf einmal. Hübsch.

Birgt allerdings auch Gefahren. Ein assert(ptr != nullptr) wird in Verbindung mit __assume() gefährlich. Manche Leute schreiben ja "resilienten" Code vor im Sinne von:

Code: Alles auswählen

void DoSomething(Thing* thing) {
  assert(thing);
  if( !thing )
    return;
}
Also eine Assertion, weil man eigentlich immer nen Pointer erwartet. Dann aber trotzdem noch explizit gegen Nullptr vergleichen, um bei Fehlbenutzung nicht in Ärger zu laufen. In Verbindung mit __assume() aber wird das if( !ptr ) rausoptimiert, weil der Pointer ja nicht Null sein kann. Und dann bekommt man Monate später von ner anderen Arbeitsgruppe ein Crashlog, in dem später im Code ein Nullzeiger dereferenziert wurde, obwohl ich doch oben extra darauf verglichen habe!!!1eins.

Trotzdem ein netter Gag mit manchmal messbaren Verbesserungen.

[edit] In der Beispielschleife war ein Tippfehler.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Bild

Dieser Tweet machte gerade die Runde.

Die Funktion bestimmt, ob ein Buchstabe Whitespace ist (Leerzeichen, Tab, Zeilenumbruch, Seitenumbruch etc).

Der Standardweg steckt hinter #if BORING. Der andere Weg ist deutlich aufregender: Da die Zahlenwerte von Whitespace im ASCII-Code keine 32 Stellen auseinanderliegen, funktioniert man kurzerhand eine 32-Bit-Zahl zu einem 32-Bit-Lookup um. Ist ein Bit gesetzt, ist das ASCII-Zeichen an dieser Position (plus 1) Whitespace, sonst nicht.

Aufregender ist das, aber ist es auch schneller?

Eine wörtliche Übersetzung vorausgesetzt: Absolut!
  • In vielen textbasierten Formaten können Token durch Whitespace getrennt werden. Also wird so eine Prüfung hinter jedem Token benötigt!
  • Gerade weil sich in textbasierten Formaten Leerzeichen und Tabs mit Zeilenumbrüchen abwechseln, ist das naive if Gift für die Sprungvorhersage.
  • Anstelle einer langen Befehlskette haben wir eine kurze Kette aus Basisarithmetik und Shifts, die jeweils in einem Takt oder weniger abschließen.
Aber wir haben die Rechnung ohne den Compiler gemacht.

Schauen wir uns das Disassembly der naiven Funktion an – vereinfacht auf Leerzeichen, Tab, Carriage Return und Line Feed (damit ich nicht so viel tippen muss) und für x86-64.

Code: Alles auswählen

bool isSpace(char c) {
    return c == ' ' || c == '\t' || c == '\n' || c == '\r';
}
Hier GCC -O2:

Code: Alles auswählen

isSpace(char):
        cmp     dil, 32
        sete    al
        cmp     dil, 9
        sete    dl
        or      al, dl
        jne     .L1
        cmp     dil, 10
        sete    al
        cmp     dil, 13
        sete    dl
        or      eax, edx
.L1:
        ret
… da kommt überhaupt nur ein einziger Sprung vor! GCC führt zwar Vergleiche aus, kombiniert die Ergebnisse dann aber mit OR. Das ist verdammt schnell. Messt selber.

Dann kommt Clang -O2:

Code: Alles auswählen

isSpace(char):
        add     dil, -9
        cmp     dil, 23
        ja      .LBB0_2
        mov     eax, 8388627
        mov     ecx, edi
        shr     eax, cl
        and     al, 1
        ret
.LBB0_2:
        xor     eax, eax
        ret
Wenn man das nach C++ rückübersetzt, sieht es so aus:

Code: Alles auswählen

	auto c2 = static_cast<unsigned int>(c) - 23;
	if(c2 > 23)
		return fasle;
	return static_cast<bool>((0x800013 >> c2) & 1);
Überflüssig zu sagen: Clang hat die langweilige Variante automatisch in die aufregende Verwandelt! Nur mit leicht anderen Zahlen, weil es 9 abzieht statt 1 (so sind die Konstanten kleiner, was andere Vorteile mit sich bringt).

Nun Visual C++ /O2:

Code: Alles auswählen

bool isSpace(char) PROC
        cmp     cl, 32
        ja      SHORT $LN5@isSpace
        mov     rax, 0x100002600
        bt      rax, rcx
        jae     SHORT $LN5@isSpace
        mov     al, 1
        ret     0
$LN5@isSpace:
        xor     al, al
        ret     0
Das sieht aus wie die aufregende Variante (zumal die Konstante wieder darin vorkommt), aber dahinter steckt mehr. Diese Version zieht allen anderen – auch dem „aufregenden“ Code – die Socken aus. Sie verwendet nämlich den BT Befehl (Bit Test), der Shift + AND + Vergleich in einen einzigen Befehl kombiniert. Der heiße Pfad ist hier – insbesondere in einer Schleife – zwei Takte kürzer. Gegen das hier hat auch der handgeschriebene Code keine Chance.

Zusammenfassung:
  • GCC: ★☆☆
    Bringt naiven Code fast auf das Niveau von handoptimiertem Code.
  • Clang: ★★☆
    Bringt naiven Code auf das Niveau von handoptimiertem Code.
  • Visual C++: ★★★
    Übertrifft sogar handoptimierten Code.
An dieser Stelle könnten wir aufhören.

Aber jetzt beginnt das Lernen erst so richtig!

Ich hatte die Funktion ja vereinfacht, so dass sie nicht auf Vertical Tab und Form Feed testet. Damit ich nicht so viel tippen muss. Wenn ich diese Prüfungen hinzufüge, dann müssten Clang und Visual C++ ja bloß zwei weitere Bits zu ihren Konstanten hinzufügen. Sonst bleibt alles gleich.

Oder?

Code: Alles auswählen

bool isSpace(char c) {
    return c == ' ' || c == '\t' || c == '\v' || c == '\f' || c == '\n' || c == '\r';
}
Der olle GCC -O2:

Code: Alles auswählen

        cmp     dil, 32
        ja      .L2
        movabs  rdx, 4294973952
        mov     eax, 1
        bt      rdx, rdi
        jnc     .L2
        ret
.L2:
        cmp     dil, 10
        sete    al
        cmp     dil, 13
        sete    dl
        or      eax, edx
        ret
Was ist denn da passiert?! GCC nutzt nun ebenfalls den heißen BT-Befehl – aber verkorkst alles drumherum so dermaßen, dass ich gar nicht weiß, wo ich anfangen soll.

Clang -O2:

Code: Alles auswählen

sSpace(char):
        add     dil, -9
        cmp     dil, 23
        ja      .LBB0_2
        mov     eax, 8388639
        mov     ecx, edi
        shr     eax, cl
        and     al, 1
        ret
.LBB0_2:
        xor     eax, eax
        ret
Clang hat tatsächlich nur zwei neue Bits hinzugefügt. Aber sein Code bleibt weiterhin um ein Vielfaches langsamer als Visual C++’s vorheriger.

Apropos Visual C++:

Code: Alles auswählen

bool isSpace(char) PROC
        cmp     cl, 32
        je      SHORT $LN3@isSpace
        sub     cl, 9
        cmp     cl, 4
        jbe     SHORT $LN3@isSpace
        xor     al, al
        ret     0
$LN3@isSpace:
        mov     al, 1
        ret     0
Visual C++ ist plötzlich dumm geworden und optimiert zu

Code: Alles auswählen

	if(c == 32)
		return true;
	return c2 - 9 <= 4;
… keine Spur mehr von BT.

Quintessenz

Compiler sind nicht „schlau“. Sie führen keine „schlauen“ Optimierungen durch. Was sie tun ist lediglich Mustererkennung: Ein Programmierer sieht, dass der Compiler schlechten Code für isSpace erzeugt. Also programmiert er in den Compiler ein: Wenn das Muster auftritt, dass eine Variable gegen vier Werte verglichen wird, und diese vier Werte sind Leerzeichen/Tab/Zeilenumbruch/Zeilenvorschub, dann lösche den Ausdruck und ersetze ihn durch <cleverste Befehlsfolge, die dem Entwickler gerade einfällt>.“

Die Tabellen für Mustererkennung nehmen absurde Ausmaße an. Durchsucht den Quelltext eures Compilers mal nach cos – da müsstet ihr auf Hunderte Muster à „ersetze cos(0) durch 1.0“ treffen.

Darum würde ich die Bewertung nun eher so vergeben:
  • GCC: ☆☆☆
    Hat ein paar Optimierungen einprogrammiert, aber sobald man eine Kleinigkeit ändert, geht der Code richtig in die Brüche.
  • Visual C++: ★☆☆
    Wie GCC, nur dass hier der Entwickler schlau genug war, direkt BT hardzucoden.
  • Clang: ★★☆
    Produziert zwar nie optimalen Code, aber zumindest scheint hier ein halbwegs variables Regelwerk einprogrammiert worden sein anstelle starrer Muster. … oder doch nicht?
Nun wäre noch zwei Fragen zu klären:

Ist die handoptimierte Version besser als die automatisch optimierte?

Sie liefert auf allen Compilern vergleichbare Leistung. Sie ist nie optimal, aber auch nie katastrophal langsam.

Kann man auf allen Compilern händisch die optimale Leistung erreichen?

Auf GCC nicht. Das erzeugt kein BT.

Auf allen anderen führt das hier zu quasi-optimalem Code:

Code: Alles auswählen

bool isSpace(char c) {
    auto const u = static_cast<unsigned>(c);
    return (u <= 63) & (0 != (0x100003E00 & (uint64_t(1) << u)));
}

Code: Alles auswählen

        cmp     dil, 64
        setb    cl
        movabs  rax, 4294983168
        bt      rax, rdi
        setb    al
        and     al, cl
        ret
(https://godbolt.org/z/TfssZ8)

… aber stattdessen solltet ihr den Compiler-Entwickler eures Vertrauens fragen, ob er das nicht direkt in den Compiler hardcoden möchte.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
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 »

Das ist ne spannende Erkenntnis. Und irgendwie enttäuschend.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Kennt ihr das, wenn ihr unbedingt schlafen solltet, aber da fällt euch gerade die perfekte Lösung für das Problem ein, an dem ihr so lange sitzt? Und eine halbe Stunde später merkt ihr, dass euer müder Kopp den totalen Brainfart hatte und das gar nicht funktionieren kann?!

Ich hatte bei meinem abschließenden Code vergessen, dass ich nicht über die Datentypbreite hinaus shiften darf. Ist korrigiert.

Nächstes Mal erst Unit Tests, dann posten :)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Noch ein kurzes Real-World-Benchmark: Mein 64-Bit-STL-Viewer schafft mit meiner handgeschriebenen bt-Version rund 30 % mehr Daten pro Sekunde als mit der Compiler-generierten. Das sind wohlgemerkt 30 % mehr Nutzdaten, nicht bloß Whitespace.

Bei 32-Bit kehrt es sich dann um. Das „dumme“

Code: Alles auswählen

	if(c == 32)
		return true;
	return c2 - 9 <= 4;
von Visual C++ ist dann 4,5 % schneller. Aber auch nur halb so schnell wie die 64-Bit-Version (der Bottleneck ist ganz wo anders; es mangelt beim Integerparsing an Registern).
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Fehlgeschlagenes Experiment: Sequence Points reduzieren um Compiler mehr Spielraum beim Instruction Reordering zu geben.

In C++ ist die Reihenfolge, in der Ausdrücke ausgeführt werden, ja nicht genau festgelegt. Bei c = a[b++]; steht nicht fest, ob b seinen neuen Wert vor der Zuweisung oder danach erhält. Festgelegt ist, nur dass vor dem Semikolon alles realisiert sein muss – denn das Semikolon ist ein Sequence Point.

Andere Sequence Points sind &&, Komma, und Funktionsaufrufe.

Warum die Reihenfolge nicht festgelegt ist? Leistung. Wenn eine Architektur erfordert, dass Funktionsparameter von rechts nach links auf den Stack geschrieben werden (x86), kann ein Compiler sie in dieser Reihenfolge berechnen und pushen, statt von links nach rechts vorzugehen und die linken Ergebnisse auf Halde zu legen bis rechts fertig berechnet wurde.

Nun betrachten wir folgenden Code:

  void foo(float * a, float * b) {
    a[1] = a[0] + 2 * a[1];
    b[1] = b[0] + 2 * b[1];
  }


Für einen Menschen sehen die beiden Zeilen unabhängig von einander aus. Aber wenn der Compiler das in Assemblerbefehle umwandelt, darf er die Befehle der beiden Zeilen nicht mischen. Grund ist des Compilers ärgster Feind: Aliasing. Wenn jemand die Funktion aufruft mit

  float abc[3] = { 1, 2, 3 };
  foo(abc, abc + 1);


… dann liefert eine Version, die beide Berechnungen zwecks besserem Scheduling vermischt, mitunter andere Ergebnisse als eine, die beide Berechnungen strikt hintereinander ausführt, weil a[1] und b[0] der selbe Wert sind.

Wenn man sich ganz ganz sicher ist, dass man die Funktion niemals mit überlappenden Parametern aufruft, möchte man das dem Compiler mitteilen. Dafür gibt es keine standardisierte Methode. Üblich sind aber Schlüsselwörter à __restrict oder noalias für die Zeiger. Deklariert man die Zeiger im Beispiel __restrict, vermischt Visual C++ tatsächlich die Berechnungen zwecks besserem Scheduling.

Jedoch hat __restrict enge Grenzen: Es funktioniert nur auf Zeigern, nicht auf Referenzen. Es funktioniert nicht auf this. Usw.

Wäre es nicht toll, dem Compiler generell den Hinweis geben zu können, dass sich benachbarte Code-Blöcke nicht beeinflussen?

… und hier habe ich zu Sequence Points geschielt. Die Idee ist folgende Funktion:

  inline void unordered(...) { }

Eine Funktion, die nichts tut, aber beliebig viele Parameter erwartet. Wir können den obigen Code nun auf folgende Weise umschreiben:

  void foo(float * a, float * b) {
    unordered(
      a[1] = a[0] + 2 * a[1],
      b[1] = b[0] + 2 * b[1]
    );
  }


… und da die Auswertungsreihenfolge von Funktionsparametern undefiniert ist, darf der Compiler die Befehle nun umsortieren und vermengen wie er will (bzw. wie es für die CPU am effizientesten ist).

Und das Ergebnis? Beschissen. Visual C++, Clang, und GCC werten die Ausdrücke schlicht von links nach rechts (getrennt) aus. Bei GCC habe ich in einigen Fällen Durchmischung gesehen, aber ohne messbaren Vorteil. Visual C++ bricht total zusammen, sobald man mehr als vier Ausdrücke angibt, und beginnt, auf den Stack zwischenzuspeichern (weil es denkt, dort würde wirklich eine Funktion aufgerufen werden).

Also ist das komplett nutzlos. Aber man muss es eben mal probiert haben.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
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 »

Aber interessante Erklärung, Danke.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
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: 08.02.2020, 16:01 … und da die Auswertungsreihenfolge von Funktionsparametern undefiniert ist, darf der Compiler die Befehle nun umsortieren und vermengen wie er will (bzw. wie es für die CPU am effizientesten ist).
Seit C++17 ist die Initialisierung von Parametern in einem Functioncall nicht mehr unsequenced sondern indeterminately-sequenced [expr.call]/5. Es ist also zwar nicht spezifiziert, in welcher Reihenfolge die Initialisierung von Parametern genau passiert, aber es ist spezifiziert, dass es eine Reihenfolge gibt [intro.execution]/15, d.h. die Initialisierung mehrerer Parameter kann nicht überlappen…

Die Wahl einer Funktion mit Ellipsisparameter ist für sowas am Ende vermutlich auch nicht so ideal, weil die Übergabe der Argumente an eine solche Funktion ja so erfolgen muss, dass in der Funktion per va_arg auf diese zugegriffen werden kann, weshalb nicht jede beliebige Expression ein Argument eines Calls einer solchen Funktion sein kann [expr.call]/9
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Dein Kommentar ist mal wieder Gold wert. Dann war’s ja tatsächlich umsonst :D

Und nun? Ins prä-C++17-Land zurück? Hätte sehr beschränkten Nutzen. Verdammt …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Falls irgendwann mal wieder jemand labert, inline-Funktionen wären genau so schnell wie Makros: https://godbolt.org/z/Zm5Qzy

Code: Alles auswählen

inline bool isSigned(unsigned short x) {
    return 0 != (x & 0x8000);
}

#define IS_SIGNED(X) (0 != ((X) & 0x8000))

int test(unsigned short const * number) {
    auto const end = number + 9999999;
    do {
#if 0
        // INLINE FUNCTION IS SLOW
        if(isSigned(*number)) {
#else
        // MACRO IS FAST
        if(IS_SIGNED(*number)) {
#endif
            return 1234;
        }
    } while(++number < end);
    return 0;
}
Makro reinterpretiert die Zieladresse als signed und prüft auf <0:

Code: Alles auswählen

cmp     WORD PTR [rcx], 0
jl      SHORT $LN8@test
Funktion shiftet, bis nur das Sign Bit übrig ist, und prüft das dann:

Code: Alles auswählen

movzx   eax, WORD PTR [rcx]
shr     ax, 15
test    al, al
jne     SHORT $LN10@test
Reproduziert mit dem aktuellen Visual C++-Preview und allen anderen Versionen, die ich in die Finger kriegen konnte.

Hat jemand eine Vermutung, warum?! Ich habe pass-by-reference probiert und __restrict. Weiß nicht weiter.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von xq »

Wenn ich mir das so angucke, gewinnt den Wettbewerb der smartesten Optimierung wohl GCC mit einem "sar 31":

Code: Alles auswählen

// https://godbolt.org/z/WVQXQj
test_fncall(unsigned short const*):
        movsx   eax, WORD PTR [rdi]
        sar     eax, 31
        and     eax, 1234
        ret
Sowohl GCC als auch Clang produzieren den selben Code für inline- und Makro-Aufruf, scheint als hättest du da nen Compiler-Bug bzw. zwei separate Pfade im Compiler gefunden
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Wenn du drüber nachdenkst: Der Shift ist wohl der absolut schnellste Weg, um von deinem Check zu einem bool zu kommen. Der Shift ist lediglich nicht der schnellste Weg, um basierend auf dem Resultat des Checks zu branchen. Der Unterschied zwischen dem Makro und der Function ist, dass die Function aus dem Resultat des Checks einen bool erzeugt. Sieht so aus, als ob der Compiler da dann auf einmal nicht mehr durchsieht. Wenn wir dein Makro so abändern:

Code: Alles auswählen

#define IS_SIGNED(X) static_cast<bool>(0 != ((X) & 0x8000))
erzeugen beide Varianten den selben Code. Ich würde das wohl als missed optimization einstufen…
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

xq hat geschrieben: 27.02.2020, 00:00Wenn ich mir das so angucke, gewinnt den Wettbewerb der smartesten Optimierung wohl GCC mit einem "sar 31"
Ja, aber sein branchless Bit Twiddling ist sinnlos, wenn das return optional angesprungen werden muss. Ursprünglich wollte ich prüfen, ob BT emittiert wird, aber die Prüfung auf < 0 ist nochmal besser.
dot hat geschrieben:Der Unterschied zwischen dem Makro und der Function ist, dass die Function aus dem Resultat des Checks einen bool erzeugt. Sieht so aus, als ob der Compiler da dann auf einmal nicht mehr durchsieht.
DAS scheint es zu sein, in der Tat :) Ich habe die ganze Zeit an den Eingabeparametern herumexperimentiert, aber tatsächlich ist der Ausgabeparameter das Problem. Vielen Dank; ich werde ein Ticket erstellen!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Wenn man den Rückgabewert der Funktion zu int ändert, wird vernünftig optimert. Boah wie übel.

Das Ticket: https://developercommunity.visualstudio ... n-int.html

Upvote falls ihr nicht wollt, dass ich alle bool in meinem Code durch int ersetze!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Kleinere Programme durch kleinere Datenstrukturen

Es ist mittlerweile bekannt, dass Speicherzugriffe für moderne CPUs sehr teuer sind und dass es sich deshalb lohnt, häufig genutzte Datenstrukturen möglichst kompakt auszulegen, so dass die CPU-Caches gut ausgenutzt werden können.

Weniger bekannt ist, dass sich das auch bei selten genutzten, “kalten” Datenstrukturen lohnen kann. Allerdings nicht für die Verarbeitungsgeschwindigkeit, sondern für die Größe des Kompilats.


Heißer Code, kalter Code

In den meisten Programmen wird der Großteil der Rechenleistung von relativ wenig Code verbraucht – von den innersten Schleifen und den Flaschenhälsen. Dieser Code ist “heiß”, da er ständig benutzt wird.

Der restliche Code liegt weitgehend brach und wird nur wenige Male pro Sekunde angesprungen (aus CPU-Sicht so gut wie nie).


Die passende Optimierung

Alle Compiler-Hersteller empfehlen Profile-Guided Optimization. Dabei wird das Programm in zwei Schritten optimiert:

Zuerst erzeugt der Compiler ein Programm für Profiling. Dieses wird gestartet und führt eine Reihe Use Cases aus, die der Entwickler bereitstellt – im Falle eines Web Browsers etwa das Laden von Seiten, das Betrachten von Videos, das Öffnen und Schließen von Tabs. Dabei werden die Profiling-Daten aufgezeichnet.

Durch diese Daten erhält der Compiler Informationen darüber, welcher Code heiß ist, und welcher kalt. Damit kompiliert er das zweite, finale Programm.

Die wichtigste Optimierung ist dann: Der heiße Code wird auf Geschwindigkeit optimiert; der kalte Code auf Größe. Das maximiert die Ausnutzung des Befehls-Caches in der CPU. Selten durchlaufene Schleifen “verpesten” den Cache nicht mehr, indem sie zu unrecht abgerollt werden und Berge an Befehlen produzieren, die die CPU am Ende doch nicht ausführt. Häufig durchlaufenen Schleifen steht mehr Cache zur Verfügung, so dass sie stärker abgerollt und schneller ausgeführt werden können.

Wie stark das Verhältnis von heißem zu kaltem Code ist, zeigt dieser Artikel des Visual C++ Team Blogs:
As a general rule of thumb for a medium or large component, there should be <5 % methods compiled for speed.
Große Anwendungen (die Klasse Microsoft Exchange, Firefox, Microsoft Word) werden also zu über 95 % auf Größe optimiert.

(Ich persönlich nutze keine Profile-Guided Optimization, sondern optimiere alles auf Größe. Meine Bottlenecks lassen sich nur selten durch Optimierung auf Geschwindigkeit lösen.)


Wie die CPU auf Datenstrukturen zugreift

Wird auf ein Member einer Klasse oder Datenstruktur zugegriffen, muss zuerst dessen Adresse berechnet werden. In den allermeisten Fällen ergibt sie sich aus der Adresse der umgebenden Datenstruktur (bei Klassen bekannt als this):

  struct Foo {
    int a;
    int b;
  };

  void overwrite_b(Foo & foo) {
    foo.b = 123;
  }


Die Funktion kompiliert zu

  MOV DWORD PTR [eax+4], 123

Dabei ist MOV der MOVE-Befehl, der aber eher Copy hätte heißen sollen. Er kopiert einen Wert aus einem Register in ein Register, oder aus dem Speicher in ein Register, oder umgekehrt. MOV ist auf x86 der mit Abstand häufigste Befehl. Während RISC-Prozessoren mit hunderten adressierbaren Registern kommen, hat x86 nur acht (32-Bit) oder 16 (64-Bit). Bei so wenig Registern muss man viel hin- und herschieben.

DWORD PTR bedeutet, dass wir hier auf Speicher zugreifen, und zwar auf ein 4-Byte großes Stück (denn so groß ist das int, das wir setzen wollen).

[eax+4] bedeutet, dass an eine Speicherposition geschrieben werden soll, die vier Bytes über dem Wert im eax-Register liegt. Das eax-Register ist jenes, in dem unser Parameter foo gelandet ist.

123 ist der Wert, der geschrieben werden soll.

Insgesamt bedeutet die Zeile also: Schreibe den Wert 123 an die Speicheradresse, die im eax-Register steckt, plus vier Bytes.


Ein Klassensystem

Diese Adressierung kennt drei subtile Unterschiede. Ändern wir das Beispiel zu:

  struct Foo {
    int first;
    int second;
    char longString[256];
    int last;
  };

  void init(Foo & foo) {
    foo.first = 1;
    foo.second = 2;
    foo.longString[0] = 0;
    foo.last = 123;
  }


Nun bekommen wir:

  MOV DWORD PTR [eax], 1
  MOV DWORD PTR [eax+4], 2
  MOV BYTE PTR [eax+8], 0
  MOV DWORD PTR [eax+264], 123


Dem Anschein nach hat sich hier nichts geändert. Die Datenstruktur wird noch immer durch eax adressiert, und die einzelnen Attribute beginnen bei Offsets von 0, 4, 8, und 264 Bytes.

Die Situation änder sich schlagartig, wenn wir nicht die Bedeutung der Befehle anzeigen, sondern die tatsächlichen Bytes der Assembler-Befehle:

  C7 00 01 00 00 00               MOV DWORD PTR [eax],1
  C7 40 04 02 00 00 00            MOV DWORD PTR [eax+4], 2
  C6 40 08 00                     MOV BYTE PTR [eax+8], 0
  C7 80 08 01 00 00 7B 00 00 00   MOV DWORD PTR [eax+264], 123


Die Einfärbung bedeutet:
  • Rot ist der eigentliche Befehl;
  • Grün ist der Versatz in der Adresse;
  • Blau ist der Wert, der geschrieben werden soll.
Wie ihr seht, verbraucht alles Platz: Möchte man ein int schreiben, muss man diesen vier-Byte-Wert auch tatsächlich in den Befehl schreiben. Ein einzelnes Byte zu schreiben ist schon drei Bytes kürzer.

Interessanter ist hier aber der Versatz! Man erkennt, dass dem Compiler drei Arten der Adressierung zur Verfügung stehen:
  • Ohne Versatz. Diese Variante funktioniert nur mit dem ersten Member, denn dessen Adresse gleicht jener der Datenstruktur. Diese Variante ist die kürzeste.
     
  • Mit kleinem Versatz (bis 127 Bytes*). Diese Variante ist ein Byte länger.
     
  • Mit großem Versatz (bis 2³¹-1 Bytes). Diese Variante ist volle drei Bytes länger als die Variante mit kleinem Versatz!

Versteckte Kosten großer Datenstrukturen

Drei Bytes sind nicht viel, aber MOV-Befehle machen nunmal einen Großteil aller Executables aus. Wir haben gesehen, dass Executables zu über 95 % auf Größe optimiert werden. Ist eine Datenstruktur größer als 128 Bytes, sind dem Compiler aber die Hände gebunden, und er muss zur Adressierung die langen Varianten des MOV-Befehls einsetzen.

Für heiße Datenstrukturen empfehle ich weiterhin:
  • Haltet sie klein (achtet auf Alignment)!
     
  • Gruppiert Attribute nach Zugriffsmustern!
     
Für kalte Datenstrukturen kommen nun aber diese Empfehlungen hinzu:
  • Haltet Datenstrukturen kleiner als 128 Bytes. Teilt sie gegebenenfalls auf. (Weckt Erinnerungen an Style Guides, oder?)
     
  • Sortiert die Attribute, so dass das am häufigsten genutzte Attribut vorn liegt (also ohne Versatz adressiert werden kann).
     
Ich habe das auf eine meiner kalten Gottklassen (*hust* GUI *hust*) angewendet und 0,5 % kleineres Kompilat bekommen. Tausende Bytes weg, durch Umsortierung der Attribute einer einzigen Klasse!


* Die 127 Bytes rühren daher, dass die CPU den Versatz signed interpretiert. Man kann also zwischen -128 und +127 Bytes angeben. Ein cleverer Compiler könnte den this-Zeiger um 127 Bytes versetzt speichern, und so alle 256 Bytes über ein kurzes MOV adressierbar machen. So einem Compiler bin ich aber bisher nie begegnet – wer auch immer den Debugger pflegen muss, würde sich darüber die Haare raufen!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Jonathan »

Interessant. Das in der Regel einige wenige Teile des Codes überproportional wichtig sind hat man natürlich schon gehört aber das man das automatisiert evaluiert und daraufhin das Programm anders optimiert war mir neu.
Ich weiß, dass folgendes Krishty provozieren wird, muss es aber trotzdem fragen: Wie relevant ist die Größe der Executable in der Praxis wirklich? Klar, bei 'nackten' Anwendungen ist das irgendwie wichtig, aber sagen wir mal ich habe ein Spiel dessen exe 20 MB hat, aber die Assets sind 1 GB groß - was wäre dann meine Motivation aus diesen 20 MB 15 MB zu machen?
Es wäre natürlich nett, wenn man nur 5% des Codes wirklich Geschwindigkeitsoptimiert kompilieren muss und sich damit Optimierungszeit spart - aber die Pipeline um herauszufinden welcher Code das genau ist erscheint mir so komplex, dass ich für Hobbyprojekte doch vielleicht einfach alles grundsätzlich auf Geschwindigkeit optimieren würde und es damit gut sein lassen würde.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Wie relevant ist die Größe der Executable in der Praxis wirklich?
Ich wünschte, ich wüsste es. Benchmarks sind sehr schwer zu finden.

Phoronix hat GCC-Benchmarks, in denen -Os ziemlich schlecht abschneidet. Aber es geht ja eigentlich gar nicht darum, das ganze Programm möglichst klein zu kriegen, deshalb sind die nicht aussagekräftig.

Idealerweise hätte eine CPU unendlich großen Instruction Cache, so dass jede Anweisung sofort in der Pipeline landet. Praktisch sind wir aber bei rund 32 KiB pro Kern. Auch wenn dein Code auf Geschwindigkeit optimiert ist, muss ihn die CPU vor der Ausführung zuerst in diese 32 KiB kriegen. Falls deine heißen Schleifen ständig von kalten Abschnitten unterbrochen werden, die 32 heiße KiB des Instruction Caches durch 32 kalte ersetzen, bremst der kalte Code die heißen Schleifen. Den kalten Code in der Größe zu halbieren würde dann die Leistung des heißen Codes verbessern, da er länger im Instruction Cache bleibt.

Wie viele Cache Misses / wie viele Prozent Leistung das bringt? Werde ich irgendwann mal testen, wenn mein Spiel reproduzierbare Benchmarks unterstützt. Oder wenn ich mit meinem S.T.A.L.K.E.R.-Build eine Benchmark-Demo aufnehme.

Chrome (und andere große Projekte) haben ein anderes Problem mit Executable Size: Code Signing setzt voraus, dass die komplette Executable in den Speicher geladen wird, bevor sie startet oder blockiert wird (denn man braucht den Hash aller enthaltenen Daten, um die Signatur zu prüfen). Dort bedeuten 30 oder 100 MiB Executable Size einen spürbaren Unterschied beim Starten. (Kann sein, dass sie die Windows-Version von Chromium deshalb in eine DLL gestopft haben statt in eine EXE – damit das Öffnen neuer Tabs keine halbe Sekunde laggt.)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Jonathan hat geschrieben: 17.09.2020, 12:25Wie relevant ist die Größe der Executable in der Praxis wirklich?
Ein Datenpunkt:

Keith Adams: PHP on the Metal

Facebook hatte sein PHP durch eine selber entwickelte VM ersetzt … die bei Einführung aber nur mit einem Siebtel der Leistung des vorherigen Systems lief.

Auf Folie 18 sieht man den ersten Hinweis, dass es sich vor allem um ein Cache-Problem handelte: Optimierungen am JIT-Compiler (aber nicht am Code, den er ausspuckt!), ließen beides schneller werden.

Sie führen speziell das Beispiel an, dass sie ein 11 KiB großes memcpy() hatten, das zwar in Mikro-Benchmarks super abschnitt, in realen Situationen aber ständig den Instruction Cache verstopfte. Ein langsameres, aber dafür kleineres memcpy() war einer der Schritte in Richtung besserer Gesamtleistung (ein Prozent Verbesserung allein dadurch, sagt Folie 34).

Leider sagen sie nur, dass der Rest durch ähnliche kleine Schritte erkämpft wurde; aber nicht, ob dabei ebenfalls Code-Größe der kritische Faktor war.

Ach, sie sagen nicht einmal, ob sie „ein Prozent“ auf die Leistung des neuen Systems beziehen (davon braucht es 600 mehr, um wieder so schnell wie das alte zu sein) oder auf die des alten Systems (davon fehlten „nur“ 86).

Eher letzteres, denn sonst würden sie wohl kaum einen Vortrag drüber machen? Also sagen wir, 6,25 % Verbesserung nur durch’s kleinere memcpy(): Vorher 16 % der Original-Leistung, danach 17. 17/16 = 1.0625 Mal so schnell.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Jonathan »

Hm ja, interessant fand ich den Teil mit "When code makes unrelated code faster or slower, suspect caching."
Ich weiß gar nicht wann ich zum letzten Mal Code wirklich profiled habe aber ist sicherlich nützlich das im Hinterkopf zu behalten, falls ich es mal irgendwann brauche.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Jonathan hat geschrieben: 22.09.2020, 10:08 Hm ja, interessant fand ich den Teil mit "When code makes unrelated code faster or slower, suspect caching."
Ich weiß gar nicht wann ich zum letzten Mal Code wirklich profiled habe aber ist sicherlich nützlich das im Hinterkopf zu behalten, falls ich es mal irgendwann brauche.
Kein Nitpicking, nur gut zu wissen weil wir ja hier bequem über das Thema plaudern: Der andere Grund, aus dem das passieren kann, ist Alignment. Auf einigen CPUs kann es einen galaktischen Unterschied machen, ob innere Schleifen auf 16-B-Grenzen beginnen oder nicht. Und das hängt davon ab, wie groß der umgebende Code ist (das ist also pseudo-zufällig).

Wir hatten hier doch mal einen Vortrag über ein Tool, das ein paar hundert Performance-Messungen durchführt und die Streuung in den Durchläufen vergleicht, um das Rauschen rauszurechnen. AFAIK werden da auch ein paar Dutzend Durchläufe mit selbem Code, aber unterschiedlichem Alignment durchgeführt (Clang/GCC können das), um Glückstreffer im Alignment auszuschließen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ich schreibe meine COM-Fehlerbehandlung seit Jahren in diesem Stil:

  HRESULT result;
  if(OpenFile(…)) {
    if(MapFile(…)) {
      if(TransferData(…)) {
        result = SUCCESS;
        ReleaseData(…);
      } else {
        result = E_CANNOT_TRANSFER;
      }
      UnmapFile(…);
    } else {
      result = E_CANNOT_MAP;
    }
    CloseFile(…);
  } else {
    result = E_CANNOT_OPEN;
  }
  return result;


Nun fällt mir ein, wie dämlich es ist, die ganzen Sprünge da drin zu haben! Viel besser:

  HRESULT result;
  result = E_CANNOT_OPEN;
  if(OpenFile(…)) {
    result = E_CANNOT_MAP;
    if(MapFile(…)) {
      result = E_CANNOT_TRANSFER;
      if(TransferData(…)) {
        result = SUCCESS;
        ReleaseData(…);
      }
      UnmapFile(…);
    }
    CloseFile(…);
  }
  return result;


… und tatsächlich brechen die Funktionen mit Visual C++ regelrecht zusammen: 50 B hier, 20 B da, 80 B drüben …

Na dann habe ich ja richtig was zu tun.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Krishty hat geschrieben: 17.09.2020, 13:56
Wie relevant ist die Größe der Executable in der Praxis wirklich?
Ich wünschte, ich wüsste es. Benchmarks sind sehr schwer zu finden.

Phoronix hat GCC-Benchmarks, in denen -Os ziemlich schlecht abschneidet.
Okay, eine Messung von Optimierung auf Größe vs. Geschwindigkeit aus der echten Welt:
  • 3D-Druck-Vorbereitung im Industriemaßstab
  • einige zehntausend Dreiecke als Eingabe; einige Millionen Voxel als Ausgabe
  • 64-Bit-Windows
  • kompiliert mit dem aktuellen Visual Studio 2019-Preview
Kompiliert weitgehend mit meinen Compiler-Einstellungen. Da andere ihre Finger drin hatten, konnte ich Exceptions und Typinformation nicht komplett abschalten, aber das wäre wohl auch realitätsfern.

Hardware ist ein aktueller Ryzen mit sechs physischen und zwölf logischen Kernen; das Programm läuft in elf Threads (einer für GUI).

Voxelisierung (SSE2 mit viel float & double):
Speed: 21.3 s
Size: 20.7 s (2.8 % schneller)

Erkennung einzelner Voxel-Volumen (skalar, viel Integer und Bitmasken):
Speed: 3.04 s (10 % schneller)
Size: 3.34 s

Auffüllen von Hohlkörpern (SSE2, viel Baumtraversierung):
Speed: 0.095 s
Size: 0.088 s (8 % schneller)

Rekonstruktion und Validierung eines Signed Distance Field nach diversen Veränderungen (SSE2 mit viel float):
Speed: 4.47 s
Size: 4.26 s (5 % schneller)

Triangulierung (skalar mit einem Bisschen float und viel Baumtraversierung):
Speed: 9.31 s
Size: 9.17 s (1.5 % schneller)

Erkennung Materialdicke (skalar mit einem Bisschen float und viel Baumtraversierung):
Speed: 5.39 s (3 % schneller)
Size: 5.55 s

Während der Entwicklung wurde ausschließlich auf Geschwindigkeit optimiert; das Kompilieren auf Größe habe ich heute zum ersten Mal ausprobiert. Ich habe keine Zeit, mit das detaillierter anzuschauen, aber Geschwindigkeitsverbesserung durch kompakten Code scheint zumindest keine Einbildung zu sein (insbesondere mit SSE?)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
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 »

Ui, interessant. Mal wieder keinen eindeutigen Sieger, so dass ich jetzt nicht losziehe und all meine Projekte umkonfiguriere. Aber doch gut zu wissen.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
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 »

Eine Mikrooptimierung, die mir auf Arbeit gerade 10% über alle Reftest-Benchmarks gebracht hat:

Wir haben sinngemäß einen std::variant<bool, uint32_t, StructMit32Byte, HUGETYPE>, die ziemlich weit drinnen in boolschen Operationen verarbeitet wird und demzufolge auch diverse Temporaries erzeugt. HUGETYPE ist auch POD, aber ein großer, fast 1kb groß.

Jetzt habe ich gelernt, dass der Variant zumindest in der Clang-Standardlib eine schicke Optimierung hat: wenn alle Typen trivially_copyable sind, erspart der Variant sich die Typunterscheidung und damit die recht teure Sprungtabelle, die dabei entsteht, weil der Standard O(1) vorschreibt. Stattdessen wird einfach der komplette Variant ohne Typunterscheidung memmoved. Ziemlich clever! Bei uns leider nicht. Dadurch wird bei uns jetzt immer ein Riesenblock kopiert, selbst wenn nur ein bool drin steht.

Meine primäre Idee: ich habe von HUGETYPE die Konstruktoren und Kopier-Operatoren manuell ausprogrammiert. Damit gilt der Typ nicht mehr als trivially_copyable und der Variant muss überall die korrekte Typunterscheidung vornehmen, und das muss in vielen Fällen kein riesiges memmove mehr machen. 10% schneller.

Weiterführende Idee: ich mache die Typunterscheidung selbst, aber mit nem simplen if. Wir haben das Ding eh in ner Struktur gewrappt, deren Kopiermechanismen ich überschreiben könnte mit

Code: Alles auswählen

if( std::holds_alternative<HUGETYPE>(other.variant) ) 
  this->variant = other.variant; // memcpys all of it anyways
else
  memcpy(&this->variant, &other.variant, MAX_SIZE_OF_THE_OTHER_TYPES + sizeof(variant_index_type));
Ich weiß noch nicht, wo genau der type_index des Variants liegt - vorne dran können wir ihn einfach mit-memcpyen, aber das Alignment des enthaltenen Typen ist evtl. ungünstig. Hintendran wäre das Alignment immer ok, aber der type_index liegt x Cachezeilen weit weg. Hm. Mal gucken, was es ist. Aber diese Methode dampft die Sprungtabelle auf ein einzelnes if() ein, das müsste den modernen Prozessoren nochmal hübsch in die Karten spielen. Und ein memcpy() mit 32Bytes ist ein AVX256-Register, das fällt nicht weiter auf.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von xq »

Schrompf hat geschrieben: 24.06.2022, 13:28 Ich weiß noch nicht, wo genau der type_index des Variants liegt - vorne dran können wir ihn einfach mit-memcpyen, aber das Alignment des enthaltenen Typen ist evtl. ungünstig. Hintendran wäre das Alignment immer ok, aber der type_index liegt x Cachezeilen weit weg. Hm. Mal gucken, was es ist. Aber diese Methode dampft die Sprungtabelle auf ein einzelnes if() ein, das müsste den modernen Prozessoren nochmal hübsch in die Karten spielen. Und ein memcpy() mit 32Bytes ist ein AVX256-Register, das fällt nicht weiter auf.
Der type_index liegt hinter dem union im Variant, damit du dir nicht das Alignment zerschießt
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Antworten