- Danke, das ist hervorragend! Branchless Binary Search kannte ich noch nicht.
- 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!
- 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.
- 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.
- 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.
[C++] Mikrooptimierungs-Log
Möglichst sinnvolle Präfixe oder die Themensymbole nutzen.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Wow. Also … mandrills Bug Report ist letzten Monat anerkannt worden: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:
watCode: 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
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:
70 % kürzer. Er hat sogar zwei benachbarte 32-Bit-FFFFFFFFs zu einem 64-Bit-mov mit der 8-Bit-Konstante -1 zusammengefasst :oCode: 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
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.
Im aktuellen Optimizer wird die ausgeschriebene Variante aber schon wieder zerstört. Damals war das „perfekte“ Disassembly durch Ausschreiben: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
Jetzt (VS 2017.3) erzeugt ähnlicher Code:70 % kürzer. Er hat sogar zwei benachbarte 32-Bit-FFFFFFFFs zu einem 64-Bit-mov mit der 8-Bit-Konstante -1 zusammengefasst :oCode: 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
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
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;
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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.)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.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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.htmlmandrill 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.
Status leider zurückgestellt weil keine Priorität. Ihr solltet also weiterhin keine Initializer Lists zuweisen.
- Schrompf
- Moderator
- Beiträge: 4855
- Registriert: 25.02.2009, 23:44
- Benutzertext: Lernt nur selten dazu
- Echter Name: Thomas Ziegenhagen
- Wohnort: Dresden
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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();
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;
}
Trotzdem ein netter Gag mit manchmal messbaren Verbesserungen.
[edit] In der Beispielschleife war ein Tippfehler.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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.
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';
}
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
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
Code: Alles auswählen
auto c2 = static_cast<unsigned int>(c) - 23;
if(c2 > 23)
return fasle;
return static_cast<bool>((0x800013 >> c2) & 1);
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
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.
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';
}
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
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
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
Code: Alles auswählen
if(c == 32)
return true;
return c2 - 9 <= 4;
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?
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
… aber stattdessen solltet ihr den Compiler-Entwickler eures Vertrauens fragen, ob er das nicht direkt in den Compiler hardcoden möchte.
- Schrompf
- Moderator
- Beiträge: 4855
- Registriert: 25.02.2009, 23:44
- Benutzertext: Lernt nur selten dazu
- Echter Name: Thomas Ziegenhagen
- Wohnort: Dresden
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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 :)
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Bei 32-Bit kehrt es sich dann um. Das „dumme“
Code: Alles auswählen
if(c == 32)
return true;
return c2 - 9 <= 4;
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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.
- Schrompf
- Moderator
- Beiträge: 4855
- Registriert: 25.02.2009, 23:44
- Benutzertext: Lernt nur selten dazu
- Echter Name: Thomas Ziegenhagen
- Wohnort: Dresden
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
- dot
- Establishment
- Beiträge: 1734
- Registriert: 06.03.2004, 18:10
- Echter Name: Michael Kenzel
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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…
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Und nun? Ins prä-C++17-Land zurück? Hätte sehr beschränkten Nutzen. Verdammt …
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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;
}
Code: Alles auswählen
cmp WORD PTR [rcx], 0
jl SHORT $LN8@test
Code: Alles auswählen
movzx eax, WORD PTR [rcx]
shr ax, 15
test al, al
jne SHORT $LN10@test
Hat jemand eine Vermutung, warum?! Ich habe pass-by-reference probiert und __restrict. Weiß nicht weiter.
- 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
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
Programmiert viel in Zig und nervt Leute damit.
- dot
- Establishment
- Beiträge: 1734
- Registriert: 06.03.2004, 18:10
- Echter Name: Michael Kenzel
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Code: Alles auswählen
#define IS_SIGNED(X) static_cast<bool>(0 != ((X) & 0x8000))
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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.
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!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.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Das Ticket: https://developercommunity.visualstudio ... n-int.html
Upvote falls ihr nicht wollt, dass ich alle bool in meinem Code durch int ersetze!
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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:
Große Anwendungen (die Klasse Microsoft Exchange, Firefox, Microsoft Word) werden also zu über 95 % auf Größe optimiert.As a general rule of thumb for a medium or large component, there should be <5 % methods compiled for speed.
(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.
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!
- 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).
* 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!
Re: [C++] Mikrooptimierungs-Log
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.
https://jonathank.de/games/
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Ich wünschte, ich wüsste es. Benchmarks sind sehr schwer zu finden.Wie relevant ist die Größe der Executable in der Praxis wirklich?
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.)
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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.
Re: [C++] Mikrooptimierungs-Log
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.
https://jonathank.de/games/
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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).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.
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.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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
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?)
- Schrompf
- Moderator
- Beiträge: 4855
- Registriert: 25.02.2009, 23:44
- Benutzertext: Lernt nur selten dazu
- Echter Name: Thomas Ziegenhagen
- Wohnort: Dresden
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
- Schrompf
- Moderator
- Beiträge: 4855
- Registriert: 25.02.2009, 23:44
- Benutzertext: Lernt nur selten dazu
- Echter Name: Thomas Ziegenhagen
- Wohnort: Dresden
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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));
- 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
Der type_index liegt hinter dem union im Variant, damit du dir nicht das Alignment zerschießtSchrompf 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.
Programmiert viel in Zig und nervt Leute damit.