[C++] Mikrooptimierungs-Log
Forumsregeln
Möglichst sinnvolle Präfixe oder die Themensymbole nutzen.
Möglichst sinnvolle Präfixe oder die Themensymbole nutzen.
-
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: [C++] Mikrooptimierungs-Log
Interessant.
Also Clang setzt die Minimum und Maximum Befehle glücklicherweise schon automatisch ein.
Ich finde, Microsofts Compiler sollte das auch können. In vektorisierten Code kann es auch Visual Studio. Also warum nicht auch sonst? Ist mir völlig unverständlich.
Bezüglich Quadratwurzel scheint übrigens das Microsoftteam zufällig eine andere Ansicht zu vertreten:
https://connect.microsoft.com/VisualStu ... ils/880213
Also Clang setzt die Minimum und Maximum Befehle glücklicherweise schon automatisch ein.
Ich finde, Microsofts Compiler sollte das auch können. In vektorisierten Code kann es auch Visual Studio. Also warum nicht auch sonst? Ist mir völlig unverständlich.
Bezüglich Quadratwurzel scheint übrigens das Microsoftteam zufällig eine andere Ansicht zu vertreten:
https://connect.microsoft.com/VisualStu ... ils/880213
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Ja, klingt tatsächlich nach einer Datenabhängigkeit, die bei der vektorisierten Variante entfällt. Ulkigerweise erwartet _mm_sqrt_sd() ein zusätzliches Register zum Rumkritzeln (hat zwei Parameter statt einem) – möglicherweise nullen die das um die Datenabhängigkeit zu vermeiden, und haben dafür ein Register verschwendet. Da kann man mit der vektorisierten Variante echt nur gewinnen.
Ich hätte das benchen sollen, statt nur die Timings nachzusehen :) Das Compiler-Team sagt, dass die double-Varianten skalar und vektorisiert die gleiche Ausführungszeit hätten – ich habe nur für die float-Varianten ins Handbuch gesehen, wo die vektorisierte Variante leicht höhere Latenz hatte.
Ich hätte das benchen sollen, statt nur die Timings nachzusehen :) Das Compiler-Team sagt, dass die double-Varianten skalar und vektorisiert die gleiche Ausführungszeit hätten – ich habe nur für die float-Varianten ins Handbuch gesehen, wo die vektorisierte Variante leicht höhere Latenz hatte.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Mal was für Optimierung auf Größe, das Visual C++ 2015 verpennt:
if(x >= 128)
produziert eine Folge von Vergleich und Jump-if-above-or-equal:
48 3D 80 00 00 00 cmp rax,00000080h
73 13 jae foo+46h
Weil 128 nicht in ein 1-B-signed char passt, den cmp als Operand nutzen kann, wird die Variante mit int als Operand gewählt. Kompakter ist
if(x > 127)
mit den resultierenden Befehlen
48 83 F8 7F cmp rax,7Fh
77 13 ja foo+44h
Zwei Bytes gespart. Bedenkt, dass das auch für x < 128 gilt (besser x <= 127)!
if(x >= 128)
produziert eine Folge von Vergleich und Jump-if-above-or-equal:
48 3D 80 00 00 00 cmp rax,00000080h
73 13 jae foo+46h
Weil 128 nicht in ein 1-B-signed char passt, den cmp als Operand nutzen kann, wird die Variante mit int als Operand gewählt. Kompakter ist
if(x > 127)
mit den resultierenden Befehlen
48 83 F8 7F cmp rax,7Fh
77 13 ja foo+44h
Zwei Bytes gespart. Bedenkt, dass das auch für x < 128 gilt (besser x <= 127)!
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
*seufz* Machen wir mal String-zu-Integer in Visual C++ schneller …
… das betrifft nämlich so ziemlich alle textbasierten Formate.
Hinweis: Nutzt niemals ein textbasiertes Format für irgendwas Performance-kritisches!
Also … meine String-zu-Integer-Routine hat im Kern so eine Schleife:
while(toChar < toEnd && isDecimalDigit(*toChar)) {
result = 10 * result + numberFromDecimalDigit(*toChar);
++toChar;
}
[Es gibt andere Schleifenarten – aber hier geht es erstmal nur um die Mikrooptimierung!]
Wir prüfen also erstmal, ob wir das Ende des Strings erreicht haben. Dann, ob eine Ziffer zwischen 0 und 9 folgt. Falls ja, verzehnfachen wir die bisherige Zahl und addieren die neue Ziffer auf.
bool isDecimalDigit(char c) {
// c >= '0' && c <= '9' würde auch gehen, aber SUB+Sprung ist schneller als zwei Sprünge
// durch den Cast zu unsigned werden alle Buchstaben, die in ASCII vor der Ziffer '0' kommen, zu sehr großen Zahlen
return unsigned(c - '0') < 9;
}
int numberFromDecimalDigit(char c) {
return c - '0';
}
Für die Folge „123“ sind das also drei Durchläufe:
movsx eax,byte ptr [rax]
sub eax,30h
cmp al,9
…
movsx eax,byte ptr [rax]
sub eax,30h
Wir laden zwei Mal aus *toChar, und Visual C++ hat daraus tatsächlich zwei Loads und zwei Subtraktionen gemacht!
Hinweis: Clang und GCC könnten hier bessere Befehle produzieren. Ich nehme Tests dankend entgegen!
Also von Hand auflösen:
while(toChar < toEnd) {
auto digit = numberFromDecimalDigit(*toChar);
if(9 < digit) {
break; // keine Ziffer
}
result = 10 * result + digit;
++toChar;
}
Ergebnis: String-zu-float ist 25 % schneller; String-zu-int 20 %. (Integer haben meist weniger Ziffern als Gleitkommazahlen, da fällt die Verbesserung weniger stark ins Gewicht.) Textbasiertes 3D-Dateiformat ist insgesamt 15 % schneller. Scheiß Compiler.
… das betrifft nämlich so ziemlich alle textbasierten Formate.
Hinweis: Nutzt niemals ein textbasiertes Format für irgendwas Performance-kritisches!
Also … meine String-zu-Integer-Routine hat im Kern so eine Schleife:
while(toChar < toEnd && isDecimalDigit(*toChar)) {
result = 10 * result + numberFromDecimalDigit(*toChar);
++toChar;
}
[Es gibt andere Schleifenarten – aber hier geht es erstmal nur um die Mikrooptimierung!]
Wir prüfen also erstmal, ob wir das Ende des Strings erreicht haben. Dann, ob eine Ziffer zwischen 0 und 9 folgt. Falls ja, verzehnfachen wir die bisherige Zahl und addieren die neue Ziffer auf.
bool isDecimalDigit(char c) {
// c >= '0' && c <= '9' würde auch gehen, aber SUB+Sprung ist schneller als zwei Sprünge
// durch den Cast zu unsigned werden alle Buchstaben, die in ASCII vor der Ziffer '0' kommen, zu sehr großen Zahlen
return unsigned(c - '0') < 9;
}
int numberFromDecimalDigit(char c) {
return c - '0';
}
Für die Folge „123“ sind das also drei Durchläufe:
- result == 0; 10 * 0 + 1 == 1;
- result == 1; 10 * 1 + 2 == 12;
- result == 2; 10 * 12 + 3 == 123;
movsx eax,byte ptr [rax]
sub eax,30h
cmp al,9
…
movsx eax,byte ptr [rax]
sub eax,30h
Wir laden zwei Mal aus *toChar, und Visual C++ hat daraus tatsächlich zwei Loads und zwei Subtraktionen gemacht!
Hinweis: Clang und GCC könnten hier bessere Befehle produzieren. Ich nehme Tests dankend entgegen!
Also von Hand auflösen:
while(toChar < toEnd) {
auto digit = numberFromDecimalDigit(*toChar);
if(9 < digit) {
break; // keine Ziffer
}
result = 10 * result + digit;
++toChar;
}
Ergebnis: String-zu-float ist 25 % schneller; String-zu-int 20 %. (Integer haben meist weniger Ziffern als Gleitkommazahlen, da fällt die Verbesserung weniger stark ins Gewicht.) Textbasiertes 3D-Dateiformat ist insgesamt 15 % schneller. Scheiß Compiler.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
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:
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:
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.
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
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
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.
Re: [C++] Mikrooptimierungs-Log
... das hat mich genauer interessiert. Genug, dass ich mich extra für die Antwort registriert habe (statt nur sporadisch stumm mitzulesen, wenn ich auf was hingewiesen werde; Hallo!).Benutzt in Visual C++ keine Initializer Lists.
Ich hab dann ein bisschen rumprobiert und, ähm, bin erschüttert: Das Problem liegt anscheinend nicht bei der init list, sondern beim autogenerierten op=.
Code: Alles auswählen
struct SRGBC_8888 {
unsigned char r, g, b, c;
SRGBC_8888& operator=(const SRGBC_8888&) = default;
};
Code: Alles auswählen
struct SRGBC_8888 {
unsigned char r, g, b, c;
SRGBC_8888& operator=(const SRGBC_8888& other) {
r = other.r;
g = other.g;
b = other.b;
c = other.c;
return *this;
};
wat.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Danke für’s Nachhaken! Vor allem der Hinweis mit dem eigenen Zuweisungsoperator ist Gold wert. So kann ich zumindest das Interface meiner structs sauber halten, mit TODO – ab Visual Studio 2020 löschen! versehen, und den Code halbwegs sauber halten.
Da ich jetzt gezielt googeln kann: Hier hatte jemand das Problem 2011. Der Bug Report ist mittlerweile gelöscht worden -.- Allerdings nutzt er Gleitkommazahlen, und Visual C++ hatte bekannte Probleme mit denen (was wiederum ich mal gemeldet hatte) – das muss also nicht das selbe Problem sein, das wir gerade beobachten.
Meldest du den Bug oder soll ich?
(Ja; ich hatte auf Größe statt Geschwindigkeit optimiert – daher das or.)
Da ich jetzt gezielt googeln kann: Hier hatte jemand das Problem 2011. Der Bug Report ist mittlerweile gelöscht worden -.- Allerdings nutzt er Gleitkommazahlen, und Visual C++ hatte bekannte Probleme mit denen (was wiederum ich mal gemeldet hatte) – das muss also nicht das selbe Problem sein, das wir gerade beobachten.
Meldest du den Bug oder soll ich?
(Ja; ich hatte auf Größe statt Geschwindigkeit optimiert – daher das or.)
Re: [C++] Mikrooptimierungs-Log
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.
Ja, das mit dem eigenen Zuweisungsoperator ist denke ich ein Workaround, mit dem man recht gut leben kann; kackt einem jedenfalls definitiv weniger den Code voll, und ist auch weniger anfällig für fehlgeleitetes "Aufräumen" von den Kollegen ;)
Ja, das mit dem eigenen Zuweisungsoperator ist denke ich ein Workaround, mit dem man recht gut leben kann; kackt einem jedenfalls definitiv weniger den Code voll, und ist auch weniger anfällig für fehlgeleitetes "Aufräumen" von den Kollegen ;)
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Geil; danke! Mein Upvoting war Krampf genug; will nicht wissen, durch welche brennenden Ringe du hüpfen musstest, um das Ticket anzulegen …
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Eine Frage, die mich schon länger beschäftigt, ist: Warum überhaupt mit Alignment kompilieren?
Nachtrag: Ich weiß nicht, wie, aber … meine EXEs sind nun über einen Prozent kleiner. Jetzt wird’s richtig interessant!
Nachtrag 2: Schade – das lag fast ausschließlich an Arrays von Konstanten (Lookup Tables und so), die durch Packing hier und da ein Byte geschrumpft sind. An den Befehlen hat sich so gut wie nichts geändert.
- auf keiner x86-CPU aus diesem Jahrzehnt sind unaligned Loads/Stores auf 8-/16-/32-Bit-Datentypen langsamer
- die einzigen x86-CPUs aus dem letzten Jahrzehnt, die mit Alignment schneller sind, sind die Intel Atoms
- seit ein paar Jahren brauchen auch SSE-Datentypen auf Intel-CPUs kein Alignment (wenn man nicht in den Bereich mit direktem Cache-Management geht) (AVX kA)
- Lokalität dürfte viel mehr ausmachen, und die wird durch Alignment eher verschlechtert
- auf jeder anderen Architektur als x86, natürlich
- wenn große Speicherbereiche chaotisch abgelaufen werden müssen, also Gathering/Scattering (damit dann keine zwei Cache Lines geladen werden müssen um einen einzelnen Wert zu laden/zu speichern)
- bei atomaren Operationen (die setzen auch auf x86 korrektes Alignment voraus)
- Erstmal: Scheiß Komplexität moderner Systeme. Der Speicherverbrauch wackelt teils um 30 % zwischen einzelnen Testläufen. WTF. Manchmal kann man an den Testreihen sogar erkennen, ob Visual Studio auf ist (WTF!). Ich habe auch leider keine Testfälle, die länger als 2 Sekunden laden oder über 250 MiB RAM verbrauchen (was kann ich dafür, dass mein Kram zehn Mal so effizient ist wie der andere Scheiß).
- Wenn man nur die Bestwerte berücksichtigt: Einige Fälle sind bis zu 2 % schneller geworden und haben um 0.5 % weniger Speicher verbraucht. Im Angesicht des Rauschens und der Messgenauigkeit ist das aber kein Grund für Freudensprünge.
- Wieder nur die Bestwerte berücksichtigend: Das Packing hat zumindest keinen Testfall langsamer gemacht.
- Die Durchschnittswerte sprechen teils ein anderes Bild, aber rein logisch sollte man sie besser nicht zu Rate ziehen (die sagen mehr über die anderen Prozesse meines Systems aus als übers Packing).
Nachtrag: Ich weiß nicht, wie, aber … meine EXEs sind nun über einen Prozent kleiner. Jetzt wird’s richtig interessant!
Nachtrag 2: Schade – das lag fast ausschließlich an Arrays von Konstanten (Lookup Tables und so), die durch Packing hier und da ein Byte geschrumpft sind. An den Befehlen hat sich so gut wie nichts geändert.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Konkrete Optimierung in Visual C++ 2017 gegenüber 2015. Diese Funktion mappt Konstanten in D3D11 und gibt nullptr zurück, falls das Mapping fehlschlägt (exemplarisch vereinfacht):
void * GPU::mapForOverwriting(ID3D11Buffer & buffer) {
D3D11_MAPPED_SUBRESOURCE result;
if(0 <= context.Map(
&buffer, 0, // buffers have only one subresource
D3D11_MAP::WRITE_DISCARD, 0, // allow driver to pick a new memory block while the GPU uses the old one
&result
)) {
__assume(nullptr != result.pData); assert(nullptr != result.pData); // D3D bug?
return result.pData;
}
return nullptr;
}
Wenn man die Funktion nun aufruft:
if(auto constants = gpu.mapForOverwriting(buffer)) { …
Hat Visual C++ 2015 zwei Prüfungen durchgeführt (bei vollem Inlining, wohlgemerkt):
Auch ein schönes Beispiel dafür, wie man Optimierung verbessern kann, indem man alle assert()s in der Release-Version zu __assume() macht.
void * GPU::mapForOverwriting(ID3D11Buffer & buffer) {
D3D11_MAPPED_SUBRESOURCE result;
if(0 <= context.Map(
&buffer, 0, // buffers have only one subresource
D3D11_MAP::WRITE_DISCARD, 0, // allow driver to pick a new memory block while the GPU uses the old one
&result
)) {
__assume(nullptr != result.pData); assert(nullptr != result.pData); // D3D bug?
return result.pData;
}
return nullptr;
}
Wenn man die Funktion nun aufruft:
if(auto constants = gpu.mapForOverwriting(buffer)) { …
Hat Visual C++ 2015 zwei Prüfungen durchgeführt (bei vollem Inlining, wohlgemerkt):
- falls das HRESULT von Map() negativ ist, if überspringen
- falls das Ergebnis von mapForOverwriting() ein nullptr ist, if überspringen
Auch ein schönes Beispiel dafür, wie man Optimierung verbessern kann, indem man alle assert()s in der Release-Version zu __assume() macht.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Wo wir gerade bei Prüfungen waren: Das hier
bool succeeded(HRESULT hr) {
if(hr < 0) {
onError(hr);
return no;
}
return yes;
}
erzeugt eine Prüfung und zwei Befehle weniger als das hier
bool succeeded(HRESULT hr) {
if(hr < 0) {
onError(hr);
}
return hr >= 0;
}
weil Visual C++ 2017 nicht erkennt, dass < 0 und >= 0 immer genau gegensätzliche Ergebnisse liefern.
bool succeeded(HRESULT hr) {
if(hr < 0) {
onError(hr);
return no;
}
return yes;
}
erzeugt eine Prüfung und zwei Befehle weniger als das hier
bool succeeded(HRESULT hr) {
if(hr < 0) {
onError(hr);
}
return hr >= 0;
}
weil Visual C++ 2017 nicht erkennt, dass < 0 und >= 0 immer genau gegensätzliche Ergebnisse liefern.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Mikrooptimierungs-Log
Voxelzeug mit Visual C++ 2017 Update 2 x64. Umständlich zu erklären, aber die Wirkung von Mikrooptimierungen grenzt hier an Magie.
Ich habe 8×8×8 float-Voxel eines Signed Distance Fields in einem Block (Standardmaße eines Leaf Nodes bei OpenVDB). Ich möchte die 2×2×2 Voxel bei Position XYZ haben, um sie kubisch interpolieren zu können. (Ich nehme niemals die Voxel ganz am Rand, dafür habe ich bereits vorgesorgt.)
OpenVDB schreibt die ersten acht Werte entlang Z in ein Array. Dann rutscht es in Y weiter und holt sich wieder acht Werte entlang der Z-Achse. Das klingt unintuitiv (serialisiert man nicht normalerweise in X-Y-Z statt Z-Y-X?), erlaubt aber, Schleifen in for(x) for(y) for(z) zu schreiben, was wohl einfacher lesbar sein soll.
Okay. Hier mein erster Entwurf (schon doppelt so schnell wie OpenVDB):
Ihr erkennt den Trick: Wenn man zum Index 8 addiert, entspricht das einem Schritt entlang Y, weil der Block in Z acht Voxel groß ist. Addiert man 64, geht man einen Schritt entlang X. Laufzeit im Testfall: 14.76 s.
Schaut man in den Assembler-Code, wird einem mulmig:
Drei Befehle, um die Adresse eines Array-Elements auszurechnen. Pfff. Das können wir selber besser: Die Offsets sind konstant, und da können wir sizeof(float) von Hand aufmultiplizieren! Statt acht Elemente weiterzugehen, gehen wir also 32 Bytes weiter. Statt 64 Elemente, 256 B.
Die Befehle haben sich so geringfügig geändert, dass man den Unterschied kaum erkennt:
Trotzdem … Laufzeit: 13.89 s (6 % schneller).
… da haben wir dem Decoder wohl eine µOp abgenommen, in die er „lade r8+rcx*4“ normalerweise zerlegt hätte. Nett.
Aber da geht noch was: Warum eigentlich zwei Mal addieren? Erst Offset zum ersten Index, dann das Ergebnis zur Array-Adresse? Also:
Hier war ich skeptisch, denn eigentlich vertiefen wir so die Abhängigkeitskette. Vorher hätte jede Adressberechnung unabhängig von der ersten Addition ausgeführt werden können, aber so … ich poste einfach mal das Disassembly der kompletten Funktion vorher:
… und nacher:
Da muss man kein Assembler-Champion sein, um den Unterschied zu sehen. Laufzeit: 13.46 s (3 % schneller).
Beachtet, dass das ein realer Anwendungsfall ist, in dem drumherum sehr viel gerechnet wird; kein synthetischer Benchmark, der einfach nur die Werte lädt. Ich habe die ganze Nacht Cache-Lokalität von Bäumen optimiert, und es hat nichts gebracht. Jetzt ist mein Programm zehn Prozent schneller – durch so einen Kleinkram.
Ich habe 8×8×8 float-Voxel eines Signed Distance Fields in einem Block (Standardmaße eines Leaf Nodes bei OpenVDB). Ich möchte die 2×2×2 Voxel bei Position XYZ haben, um sie kubisch interpolieren zu können. (Ich nehme niemals die Voxel ganz am Rand, dafür habe ich bereits vorgesorgt.)
OpenVDB schreibt die ersten acht Werte entlang Z in ein Array. Dann rutscht es in Y weiter und holt sich wieder acht Werte entlang der Z-Achse. Das klingt unintuitiv (serialisiert man nicht normalerweise in X-Y-Z statt Z-Y-X?), erlaubt aber, Schleifen in for(x) for(y) for(z) zu schreiben, was wohl einfacher lesbar sein soll.
Okay. Hier mein erster Entwurf (schon doppelt so schnell wie OpenVDB):
Code: Alles auswählen
auto firstIndex = 64 * x + 8 * y + z;
auto toDistances = leaf.buffer().mData;
float result[2 * 2 * 2];
result[0] = toDistances[firstIndex ]; // x y z
result[1] = toDistances[firstIndex + 1]; // x y z+1
result[2] = toDistances[firstIndex + 8 ]; // x y+1 z
result[3] = toDistances[firstIndex + 8 + 1]; // x y+1 z+1
result[4] = toDistances[firstIndex + 64 ]; // x+1 y z
result[5] = toDistances[firstIndex + 64 + 1]; // x+1 y z+1
result[6] = toDistances[firstIndex + 64 + 8 ]; // x+1 y+1 z
result[7] = toDistances[firstIndex + 64 + 8 + 1]; // x+1 y+1 z+1
Schaut man in den Assembler-Code, wird einem mulmig:
Code: Alles auswählen
; result[2] = toDistances[firstIndex + 8];
lea eax,[rdx+8] ; firstIndex + 8
movsxd rcx,eax ; Index kopieren; Grund ist CPU-Komplexität
movss xmm1,dword ptr [r8+rcx*4] ; mit sizeof(float) multiplizieren; zur Adresse des Arrays addieren = Adresse des floats; von dort laden
Code: Alles auswählen
template <typename T> T * byteOffset(T * pointer, size_t offsetInBytes) { // eine der meistgenutzten Funktionen bei mir
return (T *)(((char *)pointer) + offsetInBytes);
}
auto firstOffset = 256 * x + 32 * y + 4 * z;
auto toDistances = l0.buffer().mData;
float result[2 * 2 * 2];
result[0] = *byteOffset(toDistances, firstOffset ); // x y z
result[1] = *byteOffset(toDistances, firstOffset + 4); // x y z+1
result[2] = *byteOffset(toDistances, firstOffset + 32 ); // x y+1 z
result[3] = *byteOffset(toDistances, firstOffset + 32 + 4); // x y+1 z+1
result[4] = *byteOffset(toDistances, firstOffset + 256 ); // x+1 y z
result[5] = *byteOffset(toDistances, firstOffset + 256 + 4); // x+1 y z+1
result[6] = *byteOffset(toDistances, firstOffset + 256 + 32 ); // x+1 y+1 z
result[7] = *byteOffset(toDistances, firstOffset + 256 + 32 + 4); // x+1 y+1 z+1
Code: Alles auswählen
lea eax,[r9+20h]
movsxd rcx,eax
movss xmm1,dword ptr [rcx+rdx] ; keine Multiplikation mehr!
… da haben wir dem Decoder wohl eine µOp abgenommen, in die er „lade r8+rcx*4“ normalerweise zerlegt hätte. Nett.
Aber da geht noch was: Warum eigentlich zwei Mal addieren? Erst Offset zum ersten Index, dann das Ergebnis zur Array-Adresse? Also:
Code: Alles auswählen
auto toDistances = byteOffset(l0.buffer().mData, 256 * x + 32 * y + 4 * z);
float result[2 * 2 * 2];
result[0] = *toDistances; // x y z
result[1] = *byteOffset(toDistances, + 4); // x y z+1
result[2] = *byteOffset(toDistances, + 32 ); // x y+1 z
result[3] = *byteOffset(toDistances, + 32 + 4); // x y+1 z+1
result[4] = *byteOffset(toDistances, 256 ); // x+1 y z
result[5] = *byteOffset(toDistances, 256 + 4); // x+1 y z+1
result[6] = *byteOffset(toDistances, 256 + 32 ); // x+1 y+1 z
result[7] = *byteOffset(toDistances, 256 + 32 + 4); // x+1 y+1 z+1
Code: Alles auswählen
sub rsp,38h
movaps xmmword ptr [rsp+20h],xmm6
movaps xmmword ptr [rsp+10h],xmm7
movaps xmm7,xmm0
shufps xmm7,xmm0,55h
movd eax,xmm1
pshufd xmm2,xmm1,55h
movaps xmmword ptr [rsp],xmm8
movaps xmm8,xmm0
movhlps xmm6,xmm8
movd edx,xmm2
punpckhdq xmm1,xmm1
lea r8d,[rdx+rax*8]
mov rdx,qword ptr [rcx]
movd eax,xmm1
lea r9d,[rax+r8*8]
shl r9d,2
movsxd rax,r9d
movss xmm0,dword ptr [rax+rdx]
lea eax,[r9+4]
movsxd rcx,eax
lea eax,[r9+20h]
movss xmm4,dword ptr [rcx+rdx]
subss xmm4,xmm0
movsxd rcx,eax
lea eax,[r9+100h]
movss xmm1,dword ptr [rcx+rdx]
movsxd rcx,eax
lea eax,[r9+104h]
mulss xmm4,xmm6
addss xmm4,xmm0
movss xmm0,dword ptr [rcx+rdx]
movsxd rcx,eax
lea eax,[r9+120h]
movss xmm5,dword ptr [rcx+rdx]
subss xmm5,xmm0
movsxd rcx,eax
lea eax,[r9+24h]
movss xmm2,dword ptr [rcx+rdx]
movsxd rcx,eax
lea eax,[r9+124h]
mulss xmm5,xmm6
movss xmm3,dword ptr [rcx+rdx]
addss xmm5,xmm0
movsxd rcx,eax
subss xmm3,xmm1
movss xmm0,dword ptr [rcx+rdx]
subss xmm0,xmm2
mulss xmm3,xmm6
mulss xmm0,xmm6
addss xmm3,xmm1
movaps xmm6,xmmword ptr [rsp+20h]
addss xmm0,xmm2
subss xmm3,xmm4
subss xmm0,xmm5
mulss xmm3,xmm7
mulss xmm0,xmm7
addss xmm3,xmm4
movaps xmm7,xmmword ptr [rsp+10h]
addss xmm0,xmm5
subss xmm0,xmm3
mulss xmm0,xmm8
movaps xmm8,xmmword ptr [rsp]
addss xmm0,xmm3
add rsp,38h
ret
Code: Alles auswählen
sub rsp,38h
movaps xmmword ptr [rsp+20h],xmm6
movaps xmmword ptr [rsp+10h],xmm7
movaps xmm7,xmm0
shufps xmm7,xmm0,55h
movd eax,xmm1
movaps xmmword ptr [rsp],xmm8
movaps xmm8,xmm0
movhlps xmm6,xmm8
pshufd xmm2,xmm1,55h
movd edx,xmm2
punpckhdq xmm1,xmm1
lea r8d,[rdx+rax*8]
movd eax,xmm1
lea eax,[rax+r8*8]
shl eax,2
cdqe
add rax,qword ptr [rcx]
movss xmm0,dword ptr [rax+100h]
movss xmm2,dword ptr [rax+120h]
movss xmm5,dword ptr [rax+104h]
movss xmm3,dword ptr [rax+4]
subss xmm5,xmm0
subss xmm3,dword ptr [rax]
movss xmm4,dword ptr [rax+24h]
subss xmm4,dword ptr [rax+20h]
mulss xmm5,xmm6
mulss xmm3,xmm6
addss xmm5,xmm0
mulss xmm4,xmm6
addss xmm3,dword ptr [rax]
movss xmm0,dword ptr [rax+124h]
addss xmm4,dword ptr [rax+20h]
subss xmm0,xmm2
subss xmm4,xmm3
mulss xmm0,xmm6
movaps xmm6,xmmword ptr [rsp+20h]
addss xmm0,xmm2
mulss xmm4,xmm7
addss xmm4,xmm3
subss xmm0,xmm5
mulss xmm0,xmm7
movaps xmm7,xmmword ptr [rsp+10h]
addss xmm0,xmm5
subss xmm0,xmm4
mulss xmm0,xmm8
movaps xmm8,xmmword ptr [rsp]
addss xmm0,xmm4
add rsp,38h
ret
Beachtet, dass das ein realer Anwendungsfall ist, in dem drumherum sehr viel gerechnet wird; kein synthetischer Benchmark, der einfach nur die Werte lädt. Ich habe die ganze Nacht Cache-Lokalität von Bäumen optimiert, und es hat nichts gebracht. Jetzt ist mein Programm zehn Prozent schneller – durch so einen Kleinkram.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Por scheiß SSE. Jeder Compiler macht’s anders.
Funktion, die prüft, ob alle vier Komponenten eines Vektors zwischen lowerLimit und upperLimit (inklusive) sind. So geschrieben, dass alle drei identische Maschinenbefehle erzeugen.
Visual C++:Typisch. Visual C++ hilft einem nicht; es gibt keine Operatoren und nichts. Man muss alles via Intrinsic schreiben. Dafür bekommt man aber auch exakt die Befehle, die man hinschreibt.
GCC:Das sieht ja genau so aus wie die Visual C++-Version, nur mit __builtin_ statt _mm_! Dabei hat GCC doch Operatoren für seine Vektortypen!
Die Operatoren ändern aber den Typ. Wenn ich lowerLimits <= xyzw schreibe, ist das Ergebnis nicht 4×float, sondern 4×int. mask_lowerLimitOK & mask_upperLimitOK erzeugt dann aber den PAND-Befehl statt ANDPS, also das int-Äquivalent. Die CPU behandelt die Daten aber immernoch als float (bei dem Vergleich waren sie das ja noch!) und das gibt eine kleine Verzögerung beim Umschalten.
Ich muss also auf die tollen GCC-Vektor-Features scheißen und durch die __builtins erzwingen, dass der Typ 4×float bleibt, damit die richtigen Befehle erzeugt werden.
Clang:Oooh, diese verdammten Ficker. Sie haben die __builtins von GCC einfach abgeschafft, weil es „eleganter“ ist, die Operatoren zu benutzen. Die Typen sind jetzt völlig durcheinander, darum muss ich wieder von Hand zu 4×float casten. Wie ich sicherstelle, dass mask_lowerLimitOK & mask_upperLimitOK die 4×float-Version aufruft statt der 4×int-Version? Garnicht. Ich muss mich darauf verlassen, dass die Analyse des Optimizers ergibt, dass die Vergleichsergebnisse aus float-Registern kommen und der Optimizer sich dann für die 4×float-Version entscheidet obwohl der Typ im Quelltext explizit 4×int ist. (Tut der aktuelle Clang.) Ich kann also vom bloßen Betrachten des Quelltexts garnicht mehr sagen, ob die richtigen Befehle gewählt werden. Wie elegant!
Der GCC-Code ist also inkompatibel zu Clang. Clang ist kompatibel zu GCC, erzeugt da aber schlechtere Maschinenbefehle. Und Visual C++ ist inkompatibel zu beiden.
Kommt bloß nicht auf die Idee, da einfach return lowerLimit <= xyzw[0] && xyzw[0] && upperLimit && lowerLimit <= xyzw[1] && … hinzuschreiben und euch dann darauf zu verlassen, dass es irgendein Compiler optimiert bekommt. So naiv!
Getestet mit Visual C++ 2015, GCC 7.1, Clang 4.0.
Die resultierenden Befehle sind übrigens… und wenn ich das Assembly direkt hinschreiben könnte, wäre das drei Viertel kürzer als jede C++-Version.
Bitte sagt mir, dass ich alles total falsch mache und das nur ein großes Missverständnis ist!
Nachtrag: Ich hatte versehentlich mehrfach GCC geschrieben; ist gefixt; sry
Nachtrag 2: Bevor mir noch jemand den Kopf abreißt, der Compiler hätte schon Gründe, die int-Version zu nehmen: In einigen Situationen können die int-Versionen auf float-Daten erwünscht sein; z.B. wenn alle float-Einheiten ausgelastet sind und verspätete Berechnungen besser sind als garnichts zu tun. Ist aber oben ganz deutlich nicht der Fall (mitten im kritischen Pfad!).
Funktion, die prüft, ob alle vier Komponenten eines Vektors zwischen lowerLimit und upperLimit (inklusive) sind. So geschrieben, dass alle drei identische Maschinenbefehle erzeugen.
Visual C++:
Code: Alles auswählen
auto const lowerLimits = _mm_set_ps1(lowerLimit);
auto const upperLimits = _mm_set_ps1(upperLimit);
auto const mask_lowerLimitOK = _mm_cmple_ps(lowerLimits, xyzw);
auto const mask_upperLimitOK = _mm_cmple_ps(xyzw, upperLimits);
return 0b1111 == _mm_movemask_ps(_mm_and_ps(mask_lowerLimitOK, mask_upperLimitOK));
GCC:
Code: Alles auswählen
FLOATX4 const lowerLimits = { lowerLimit, lowerLimit, lowerLimit, lowerLimit }; // Ja, wirklich. Macht Spaß mit 16×char.
FLOATX4 const upperLimits = { upperLimit, upperLimit, upperLimit, upperLimit };
auto const mask_lowerLimitOK = __builtin_ia32_cmpleps(lowerLimits, xyzw);
auto const mask_upperLimitOK = __builtin_ia32_cmpleps(xyzw, upperLimits);
return 0b1111 == __builtin_ia32_movmskps(__builtin_ia32_andps(mask_lowerLimitOK, mask_upperLimitOK));
Die Operatoren ändern aber den Typ. Wenn ich lowerLimits <= xyzw schreibe, ist das Ergebnis nicht 4×float, sondern 4×int. mask_lowerLimitOK & mask_upperLimitOK erzeugt dann aber den PAND-Befehl statt ANDPS, also das int-Äquivalent. Die CPU behandelt die Daten aber immernoch als float (bei dem Vergleich waren sie das ja noch!) und das gibt eine kleine Verzögerung beim Umschalten.
Ich muss also auf die tollen GCC-Vektor-Features scheißen und durch die __builtins erzwingen, dass der Typ 4×float bleibt, damit die richtigen Befehle erzeugt werden.
Clang:
Code: Alles auswählen
FLOATX4 const lowerLimits = { lowerLimit, lowerLimit, lowerLimit, lowerLimit };
FLOATX4 const upperLimits = { upperLimit, upperLimit, upperLimit, upperLimit };
auto const mask_lowerLimitOK = lowerLimits <= xyzw;
auto const mask_upperLimitOK = xyzw <= upperLimits;
return 0b1111 == __builtin_ia32_movmskps((FLOATX4)(mask_lowerLimitOK & mask_upperLimitOK));
Der GCC-Code ist also inkompatibel zu Clang. Clang ist kompatibel zu GCC, erzeugt da aber schlechtere Maschinenbefehle. Und Visual C++ ist inkompatibel zu beiden.
Kommt bloß nicht auf die Idee, da einfach return lowerLimit <= xyzw[0] && xyzw[0] && upperLimit && lowerLimit <= xyzw[1] && … hinzuschreiben und euch dann darauf zu verlassen, dass es irgendein Compiler optimiert bekommt. So naiv!
Getestet mit Visual C++ 2015, GCC 7.1, Clang 4.0.
Die resultierenden Befehle sind übrigens
Code: Alles auswählen
shufps xmm0, xmm0, 0
shufps xmm2, xmm2, 0
cmpleps xmm0, xmm1
cmpleps xmm1, xmm2
andps xmm1, xmm0
movmskps eax, xmm1
cmp eax, 15
sete al
ret
Bitte sagt mir, dass ich alles total falsch mache und das nur ein großes Missverständnis ist!
Nachtrag: Ich hatte versehentlich mehrfach GCC geschrieben; ist gefixt; sry
Nachtrag 2: Bevor mir noch jemand den Kopf abreißt, der Compiler hätte schon Gründe, die int-Version zu nehmen: In einigen Situationen können die int-Versionen auf float-Daten erwünscht sein; z.B. wenn alle float-Einheiten ausgelastet sind und verspätete Berechnungen besser sind als garnichts zu tun. Ist aber oben ganz deutlich nicht der Fall (mitten im kritischen Pfad!).
-
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: Jammer-Thread
Aber warum benutzt du nicht einfach überall die Intel Intrinsics?
Die funktionieren doch überall, kein Mensch benutzt diesen __builtin Quatsch für SSE Code.
Der generierte Code ist auch identisch.)
Die funktionieren doch überall, kein Mensch benutzt diesen __builtin Quatsch für SSE Code.
Der generierte Code ist auch identisch.)
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Die Intel-Intrinsics sind bei GCC keine Intrinsics, sondern stecken in Headern – und fremde Header benutze ich nicht.
-
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: Jammer-Thread
Ich sehe nicht den großen Unterschied zwischen Builtin Headern und Builtin Funktionen, aber ok wie du meinst.
Nur vielleicht solltest du dich dann nicht beschweren, denn das ist schon ein sehr extremer und ungewöhnlicher Ansatz. ;)
Nur vielleicht solltest du dich dann nicht beschweren, denn das ist schon ein sehr extremer und ungewöhnlicher Ansatz. ;)
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Wie kriege ich eigentlich ein einzelnes float in einen SSE-Datentyp, ohne zusätzlichen Code zu erzeugen?
Alle Compiler (Clang, GCC, VCpp) haben floats sowieso in einem XMM-Register liegen. Intrinsics wie _mm_set_ss() sollten daher ein No-Op sein. Sind sie aber mit keinem einzigen Compiler!
Das liest sich wie eine Optimizer-Karikatur! Clang kriegt nicht einmal zwei genullte Register zu einem kombiniert (bei Visual C++ bin ich das längst gewöhnt). Man sieht, dass da NULL optimiert wurde (der Optimizer scheint das Nullen der drei oberen Lanes als sehr wichtig zu empfinden, obwohl sie hinterher alle wieder weggeschmissen werden).
Am nächsten dran bin ich via _mm_set_ps(x, x, x, x). Statt xorps + movss habe ich dann shufps (hier können die Compiler plötzlich DOCH Kopien wegoptimieren!). Warum kriegt man diesen überflüssigen Befehl nicht auch noch weg? Warum muss ich so viel Overhead hinscheißen, nur um MINPS benutzen zu dürfen? Warum machen die alle ihre Jobs nicht richtig?
Alle Compiler (Clang, GCC, VCpp) haben floats sowieso in einem XMM-Register liegen. Intrinsics wie _mm_set_ss() sollten daher ein No-Op sein. Sind sie aber mit keinem einzigen Compiler!
Code: Alles auswählen
float minimumOf(float a, float b) {
return _mm_cvtss_f32(_mm_min_ps(
_mm_set_ss(a),
_mm_set_ss(b)
));
}
Code: Alles auswählen
; Clang
xorps xmm3, xmm3
xorps xmm2, xmm2
movss xmm2, xmm0 # xmm2 = xmm0[0],xmm2[1,2,3]
movss xmm3, xmm1 # xmm3 = xmm1[0],xmm3[1,2,3]
minps xmm2, xmm3
movaps xmm0, xmm2
ret
; GCC
pxor xmm2, xmm2
movss DWORD PTR [rsp-12], xmm0
movss xmm0, DWORD PTR [rsp-12]
movss xmm2, xmm1
minps xmm0, xmm2
ret
; VCpp
movaps xmm2, xmm0
xorps xmm3, xmm3
movss xmm3, xmm2
xorps xmm2, xmm2
movss xmm2, xmm1
minps xmm3, xmm2
movaps xmm0, xmm3
ret 0
Am nächsten dran bin ich via _mm_set_ps(x, x, x, x). Statt xorps + movss habe ich dann shufps (hier können die Compiler plötzlich DOCH Kopien wegoptimieren!). Warum kriegt man diesen überflüssigen Befehl nicht auch noch weg? Warum muss ich so viel Overhead hinscheißen, nur um MINPS benutzen zu dürfen? Warum machen die alle ihre Jobs nicht richtig?
-
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: Jammer-Thread
Ja, das ist tatsächlich ziemlich albern.
Interessant ist das Clang den idealen Code erzeugt, sobald man _mm_min_ss verwendet (d.h. nur eine einzige Instruction).
Es ist nicht immer möglich, aber so eine Funktion setzt man am Besten einfach in standard C++ um.
Generiert auf allen 3 Compilern den optimalen Code.
Interessant ist das Clang den idealen Code erzeugt, sobald man _mm_min_ss verwendet (d.h. nur eine einzige Instruction).
Es ist nicht immer möglich, aber so eine Funktion setzt man am Besten einfach in standard C++ um.
Code: Alles auswählen
float minimumOf(float a, float b) {
return a < b ? a : b;
}
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Nein; der optimale Code wäre MINPS, aber alle drei erzeugen MINSS.
Ich verwende das auch, soweit möglich (und das ist eher zum Anti-Jammern, denn vor drei, vier Jahren bekam man da grundsätzlich nur via Assembly gutes Kompilat). Für das hier erzeugt auch jeder Compiler CVTTSS2SI (ich kann also meine Intrinsics-Version von vor drei Jahren löschen):
int truncated(float x) { return int(f); }
Hier erzeugen alle drei ROR:
unsigned int rotated_right(unsigned int x, int bits) {
return (x >> bits) | (x << (32 - bits));
}
Beachtet, dass der Code Undefined Behavior enthält (bei bits == 0 wird um 32 Bits nach links geschoben -> UB). Umso erstaunlicher, dass alle Compiler die richtige Interpretation hard-coded haben, obwohl Clang und GCC warnen. Pappt man ein Modulo 32 (oder & 31 oder wasauchimmer) an den Shift, versteht Visual C++ es überhaupt nicht mehr, aber man ist standardkonform und Clang/GCC erzeugen gutes Kompilat. Hier also unbedingt separaten VC-Pfad mit _rotr()-Intrinsic.
Hier erzeugt Visual C++ ANDPS mit Maske:
float absoluteOf(float x) { return x > 0 ? x : -x; }
aber weder Clang noch GCC erkennen es und man muss an der Stelle __builtin_fabs() einsetzen, damit nicht gebrancht wird.
Bei allem anderen bin ich total gefickt: Ich kriege immer mindestens ein überflüssiges SHUFPS beim Cast von float zu __m128. Oder ein überflüssiges movd beim Cast von double zu __m128d. Und entsprechenden Registerdruck weil jeder Parameter doppelt vorliegt. Totaler Schwachsinn.
Ich verwende das auch, soweit möglich (und das ist eher zum Anti-Jammern, denn vor drei, vier Jahren bekam man da grundsätzlich nur via Assembly gutes Kompilat). Für das hier erzeugt auch jeder Compiler CVTTSS2SI (ich kann also meine Intrinsics-Version von vor drei Jahren löschen):
int truncated(float x) { return int(f); }
Hier erzeugen alle drei ROR:
unsigned int rotated_right(unsigned int x, int bits) {
return (x >> bits) | (x << (32 - bits));
}
Beachtet, dass der Code Undefined Behavior enthält (bei bits == 0 wird um 32 Bits nach links geschoben -> UB). Umso erstaunlicher, dass alle Compiler die richtige Interpretation hard-coded haben, obwohl Clang und GCC warnen. Pappt man ein Modulo 32 (oder & 31 oder wasauchimmer) an den Shift, versteht Visual C++ es überhaupt nicht mehr, aber man ist standardkonform und Clang/GCC erzeugen gutes Kompilat. Hier also unbedingt separaten VC-Pfad mit _rotr()-Intrinsic.
Hier erzeugt Visual C++ ANDPS mit Maske:
float absoluteOf(float x) { return x > 0 ? x : -x; }
aber weder Clang noch GCC erkennen es und man muss an der Stelle __builtin_fabs() einsetzen, damit nicht gebrancht wird.
Bei allem anderen bin ich total gefickt: Ich kriege immer mindestens ein überflüssiges SHUFPS beim Cast von float zu __m128. Oder ein überflüssiges movd beim Cast von double zu __m128d. Und entsprechenden Registerdruck weil jeder Parameter doppelt vorliegt. Totaler Schwachsinn.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Ach, noch einer, mit dem man wirklich tief in die Innereien der Compilers gucken kann: Bit Scan. Man sucht den Index des höchsten Bits, das gesetzt ist. Dann weiß man, wie viele Bits die Zahl hat. Bei 13 (binär 1101) wäre das also 3, weil das 4. Bit von hinten das höchstwertige ist, das gesetzt ist.
Hier gibt es auch wieder einen Hardware-Befehl: BSR (bit scan reverse).
Visual C++ hat das _BitScanReverse64()-Intrinsic. Alles gut.
Clang/GCC haben dafür kein Intrinsic. Die haben nur __builtin_clzll(), und das zählt die Anzahl der Nullen von vorn nach hinten. Also das Gegenteil.
Im Internet bekommt man gern den Hinweis, dass 63 - __builtin_clzll() das gleiche ergibt wie _BitScanReverse64(). Stimmt auch.
Clang erzeugt auch optimal Code: einen einzigen BSR-Befehl.
GCC nicht:
bsr rdi, rdi
mov eax, 63
xor rdi, 63
sub eax, edi
XOR? SUB? WTF?
Irgendein Genie bei GCC muss sich mal gedacht haben:
Die Lösung ist also:
return 63 ^ __builtin_clzll(x);
denn das erzeugt 63 ^ 63 ^ BSR(x) und kann auch von GCC zu BSR(x) optimiert werden. Dann kriegt man unter Clang und GCC optimales Kompilat.
Kurzer Reality Check, wofür man diese Zählanweisungen nutzen kann (außer für Voxel Engines): SIMD-Parsing von Textdateien. Will ich Whitespace überspringen, lade ich 16 Buchstaben in ein SSE-Register, und prüfe die 16 ASCII-Werte parallel auf Leerzeichen/Tab/etc. Dabei wird alles auf 0 gesetzt, was Whitespace ist, und alles andere auf 1. Die höchstwertigen Bits jeder Spur extrahiere ich (dafür gibt’s einen Hardware-Befehl), und kann via BSF (Nullen am Ende der Zahl) zählen, wie weit es bis zum nächsten Bezeichner ist (mit phänomenalem Nutzen-pro-Takt-Verhältnis).
Hier gibt es auch wieder einen Hardware-Befehl: BSR (bit scan reverse).
Visual C++ hat das _BitScanReverse64()-Intrinsic. Alles gut.
Clang/GCC haben dafür kein Intrinsic. Die haben nur __builtin_clzll(), und das zählt die Anzahl der Nullen von vorn nach hinten. Also das Gegenteil.
Im Internet bekommt man gern den Hinweis, dass 63 - __builtin_clzll() das gleiche ergibt wie _BitScanReverse64(). Stimmt auch.
Clang erzeugt auch optimal Code: einen einzigen BSR-Befehl.
GCC nicht:
bsr rdi, rdi
mov eax, 63
xor rdi, 63
sub eax, edi
XOR? SUB? WTF?
Irgendein Genie bei GCC muss sich mal gedacht haben:
- __builtin_clzll(x) wird emuliert durch 63 - BSR(x)
- die Subtraktion ist zu langsam/zu lang/blockiert den falschen Port
- also nehmen wir 63 ^ BSR(x), denn für Werte im Bereich [0, 63] mit Zweierkomplement und blabla ist XOR das gleiche wie Subtraktion und der Befehl ist schneller/kürzer/nutzt ’nen freien Port
Die Lösung ist also:
return 63 ^ __builtin_clzll(x);
denn das erzeugt 63 ^ 63 ^ BSR(x) und kann auch von GCC zu BSR(x) optimiert werden. Dann kriegt man unter Clang und GCC optimales Kompilat.
Kurzer Reality Check, wofür man diese Zählanweisungen nutzen kann (außer für Voxel Engines): SIMD-Parsing von Textdateien. Will ich Whitespace überspringen, lade ich 16 Buchstaben in ein SSE-Register, und prüfe die 16 ASCII-Werte parallel auf Leerzeichen/Tab/etc. Dabei wird alles auf 0 gesetzt, was Whitespace ist, und alles andere auf 1. Die höchstwertigen Bits jeder Spur extrahiere ich (dafür gibt’s einen Hardware-Befehl), und kann via BSF (Nullen am Ende der Zahl) zählen, wie weit es bis zum nächsten Bezeichner ist (mit phänomenalem Nutzen-pro-Takt-Verhältnis).
-
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: Jammer-Thread
Hm, habe ich was verpasst?
Warum ist minps besser als minss?
Bei float absoluteOf(float x) { return x > 0 ? x : -x; } muss ich leider GCC/Clang rechtgeben, denn die elegante Version mit and verändert das Vorzeichen wenn x = NaN ist. Clang optimiert den Code erfolgreich mit -ffinite-math-only und GCC zumindest mit -ffast-math.
Godbolt
EDIT:
Eine standardsicher Version ohne builtin:
Allerdings ein externer Header und Microsoft ist hier auch völlig überfordert und generiert sogar einen Funktionsaufruf. :roll:
Warum ist minps besser als minss?
Bei float absoluteOf(float x) { return x > 0 ? x : -x; } muss ich leider GCC/Clang rechtgeben, denn die elegante Version mit and verändert das Vorzeichen wenn x = NaN ist. Clang optimiert den Code erfolgreich mit -ffinite-math-only und GCC zumindest mit -ffast-math.
Godbolt
EDIT:
Eine standardsicher Version ohne builtin:
Code: Alles auswählen
#include <math.h>
float absoluteOf(float x)
{
return copysignf(x, 1.0f);
}
Zuletzt geändert von Spiele Programmierer am 07.08.2017, 23:16, insgesamt 2-mal geändert.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Die Latenz ist gleich, aber es ist ein Byte kürzer.Spiele Programmierer hat geschrieben:Hm, habe ich was verpasst?
Warum ist minps besser als minss?
Verdammt – ich muss hier noch /fp:fast an gehabt haben; da hast du völlig recht!Spiele Programmierer hat geschrieben:Bei float absoluteOf(float x) { return x > 0 ? x : -x; } muss ich leider GCC/Clang rechtgeben, denn die elegante Version mit and verändert das Vorzeichen wenn x = NaN ist. Clang optimiert den Code erfolgreich mit -ffinite-math-only und GCC zumindest mit -ffast-math.
Godbolt
-
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: Jammer-Thread
Also auf Godbolt kompilert Visual C++ das tatsächlich zu andps ohne weitere Flags... :roll:Verdammt – ich muss hier noch /fp:fast an gehabt haben; da hast du völlig recht!
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Anmerkung – für NaN selber hat das Vorzeichen keinen Einfluss. Mantisse und Vorzeichen stehen der Anwendung zur Verfügung, um darin Informationen zu speichern. Wikipedia sagt nun:Spiele Programmierer hat geschrieben:Bei float absoluteOf(float x) { return x > 0 ? x : -x; } muss ich leider GCC/Clang rechtgeben, denn die elegante Version mit and verändert das Vorzeichen wenn x = NaN ist.
Ich habe keinen Bock, mich jetzt durch den Standard zu wühlen, aber … wenn der Standard beim Wegschmeißen des Sign Bits bei abs keine Exception vorschreibt, würde ich zumindest die Möglichkeit einräumen, dass die Optimierung legal ist. So lange wir keine Paragraphen dazu haben, gebe ich aber weiter GCC/Clang recht.https://en.wikipedia.org/wiki/NaN hat geschrieben:The treatment of the sign bit of NaNs for some simple operations (such as absolute value) is different from that for arithmetic operations. Traps are not required by the standard.
- xq
- Establishment
- Beiträge: 1581
- Registriert: 07.10.2012, 14:56
- Alter Benutzername: MasterQ32
- Echter Name: Felix Queißner
- Wohnort: Stuttgart & Region
- Kontaktdaten:
Re: Jammer-Thread
Junge Junge Junge, ihr diskutiert hier auf nem ganz schön hohen Niveau! Mal wieder alles sehr lehrreich!
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…
Programmiert viel in
Zig
und nervt Leute damit.
Programmiert viel in
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Ich freue mich auch, dass Spiele Programmierer mit mir spricht; endlich mal Bidirektion im Jammer-Thread :P
- Schrompf
- Moderator
- Beiträge: 4855
- Registriert: 25.02.2009, 23:44
- Benutzertext: Lernt nur selten dazu
- Echter Name: Thomas Ziegenhagen
- Wohnort: Dresden
- Kontaktdaten:
Re: Jammer-Thread
Und würde vielleicht in den Mikrooptimierungs-Thread gehören. Ich finde es aber auch gerade sehr spannend, was ihr hier so ausbreitet. Gerade weil ich die ganze Zeit meine Voxel-Engine im Hinterkopf habe, der ich irgendwann mit Hardcore-SS2 Beine machen muss. Oder war's SSE4...? Irgendeins der Bitscan-Befehle war erst übelst spät eingeführt worden, wie ich anhand von Splatter-ILLEGAL INSTRUCTION-Testberichten feststellen durfte, obwohl die Kumpels, die für mich gefühlt zur selben Gattung gehören, schon seit SSE1 verfügbar sind.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Es war SSE4.1, Population Count, und bei mir hattest du auch mal was AVX-Kompiliertes gegeben ;)
- Krishty
- Establishment
- Beiträge: 8240
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: Jammer-Thread
Hat schonmal jemand bei Clang/GCC __attribute((vector_size())) mit was anderem als 16 benutzt?
Ich möchte gern vier unsigned chars parallel verarbeiten. Ideal dafür wären SSE-Register (trotz 75 % Platzverschwendung – volles SIMD und sogar Saturation Arithmetic, fuck yea!)
Ich habe ganz ganz schnell mit Clang & GCC getestet, wie sie unsigned char __attribute((vector_size(4))) behandeln, und …
GCC bekommt einen Trostpreis für seinen Fleiß, alle vier Werte parallel in einem General Purpose Register zu addieren. Das ist sehr clever.
Clang schmeißt GPR und SSE auf schlimmstmögliche Art durcheinander und kriegt garnichts.
Vielleicht ist das Versagen dem Umstand geschuldet, dass die Compiler gezwungen sind, sizeof(UINT1BX4) == 4 zu garantieren, und die Werte deshalb nicht in den SSE-Registern parken dürfen?
Soll ich einfach 16er-Vektoren nutzen und die oberen zwölf Elemente ignorieren? Dann landen die Werte garantiert in SSE-Registern und beide Compiler erzeugen in einfachen Fällen hervorragenden Code; ich weiß nur nicht, wie die komplizierten Fälle aussehen werden …
Ich möchte gern vier unsigned chars parallel verarbeiten. Ideal dafür wären SSE-Register (trotz 75 % Platzverschwendung – volles SIMD und sogar Saturation Arithmetic, fuck yea!)
Ich habe ganz ganz schnell mit Clang & GCC getestet, wie sie unsigned char __attribute((vector_size(4))) behandeln, und …
GCC bekommt einen Trostpreis für seinen Fleiß, alle vier Werte parallel in einem General Purpose Register zu addieren. Das ist sehr clever.
Clang schmeißt GPR und SSE auf schlimmstmögliche Art durcheinander und kriegt garnichts.
Vielleicht ist das Versagen dem Umstand geschuldet, dass die Compiler gezwungen sind, sizeof(UINT1BX4) == 4 zu garantieren, und die Werte deshalb nicht in den SSE-Registern parken dürfen?
Soll ich einfach 16er-Vektoren nutzen und die oberen zwölf Elemente ignorieren? Dann landen die Werte garantiert in SSE-Registern und beide Compiler erzeugen in einfachen Fällen hervorragenden Code; ich weiß nur nicht, wie die komplizierten Fälle aussehen werden …