[C++] Mikrooptimierungs-Log

[Spiele Programmierer]

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

[Krishty]

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.

[Krishty]

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

[Krishty]

*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:

1. result == 0; 10 * 0 + 1 == 1;
2. result == 1; 10 * 1 + 2 == 12;
3. result == 2; 10 * 12 + 3 == 123;

Wir schauen ins Disassembly, und … eeeeeeeeew:

  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]

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.

[mandrill]

Benutzt in Visual C++ keine Initializer Lists.

... 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!).

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;
};

Das führt mit der init-list-Variante zu deinem scheußlichen Listing 1. (edit: aber nicht nur mit der, sondern auch, wenn SRGBC nen "normalen" ctor krieg und man den benutzt)

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;
};

... aber hiermit produziert auch die init-List-Version das schöne Listing 2. Zwar bei mir mit mov statt or (Compilerflags anders?), aber auch mit dem schlauen qword.

wat.

[Krishty]

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.)

[mandrill]

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 ;)

[Krishty]

Geil; danke! Mein Upvoting war Krampf genug; will nicht wissen, durch welche brennenden Ringe du hüpfen musstest, um das Ticket anzulegen …

[Krishty]

Eine Frage, die mich schon länger beschäftigt, ist: Warum überhaupt mit Alignment kompilieren?

• 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

Damit braucht man IMHO Alignment nur noch unter diesen Umständen:

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

Ich habe also mal meine Code Base dafür fit gemacht, die Alignment-Option im Compiler abzuschalten. Dann bin ich ein paar Testläufe mit meinem Viewer und großen Datensätzen gefahren (z.B. mit dem Ace Combat-Level aus dem anderen Thread). Das Ergebnis war fast immer so knapp wie das hier (dunkel ist aligned; hell ist packed):

packed unpacked perf.png (10 KiB) 21028 mal betrachtet

Ich habe noch mehr Daten, aber ich habe keinen Bock, Diagramme zu malen.

• 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).

So. Das war kein großer Wurf. Das Rauschen ist auch viel zu stark, um Schlüsse zu ziehen. Aber wenn das mal einer von euch testet: Lasst es mich wissen. Ich bleibe erstmal packed bis irgendwas kaputtgeht.

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]

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):

• falls das HRESULT von Map() negativ ist, if überspringen
• falls das Ergebnis von mapForOverwriting() ein nullptr ist, if überspringen

Visual C++ 2017 begreift nun endlich, dass beide Bedingungen immer zugleich wahr oder falsch sind, und schmeißt die nullptr-Prüfung raus.

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]

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.

[Krishty]

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):

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

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:

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

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.

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

Die Befehle haben sich so geringfügig geändert, dass man den Unterschied kaum erkennt:

Code: Alles auswählen

lea         eax,[r9+20h]  
movsxd      rcx,eax  
movss       xmm1,dword ptr [rcx+rdx]  ; keine Multiplikation mehr!

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:

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

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:

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  

… und nacher:

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  

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.

[Krishty]

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++:

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));

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:

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));

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:

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));

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

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

… 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!).

[Spiele Programmierer]

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.)

[Krishty]

Die Intel-Intrinsics sind bei GCC keine Intrinsics, sondern stecken in Headern – und fremde Header benutze ich nicht.

[Spiele Programmierer]

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. ;)

[Krishty]

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!

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

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?

[Spiele Programmierer]

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.

Code: Alles auswählen

float minimumOf(float a, float b) {
      return a < b ? a : b;
}

Generiert auf allen 3 Compilern den optimalen Code.

[Krishty]

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.

[Krishty]

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:

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

Nun kann GCC 63 - (63 - x) zu x optimieren, aber leider hat der kluge Mensch GCC nicht beigebracht, dass 63 - (63 ^ x) == x gilt (unter den Voraussetzungen von BSR).

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).

[Spiele Programmierer]

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:

Code: Alles auswählen

#include <math.h>

float absoluteOf(float x) 
{
    return copysignf(x, 1.0f);
}

Allerdings ein externer Header und Microsoft ist hier auch völlig überfordert und generiert sogar einen Funktionsaufruf. :roll:

[Krishty]

Hm, habe ich was verpasst?
Warum ist minps besser als minss?

Die Latenz ist gleich, aber es ist ein Byte kürzer.

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

Verdammt – ich muss hier noch /fp:fast an gehabt haben; da hast du völlig recht!

[Spiele Programmierer]

Verdammt – ich muss hier noch /fp:fast an gehabt haben; da hast du völlig recht!

Also auf Godbolt kompilert Visual C++ das tatsächlich zu andps ohne weitere Flags... :roll:

[Krishty]

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.

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:

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.

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.

[xq]

Junge Junge Junge, ihr diskutiert hier auf nem ganz schön hohen Niveau! Mal wieder alles sehr lehrreich!

[Krishty]

Ich freue mich auch, dass Spiele Programmierer mit mir spricht; endlich mal Bidirektion im Jammer-Thread :P

[Schrompf]

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.

[Krishty]

Es war SSE4.1, Population Count, und bei mir hattest du auch mal was AVX-Kompiliertes gegeben ;)

[Krishty]

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 …