[C++] Mikrooptimierungs-Log

Hier können Artikel, Tutorials, Bücherrezensionen, Dokumente aller Art, Texturen, Sprites, Sounds, Musik und Modelle zur Verfügung gestellt bzw. verlinkt werden.
Forumsregeln
Möglichst sinnvolle Präfixe oder die Themensymbole nutzen.

Re: [C++] Mikrooptimierungs-Log

Beitragvon Spiele Programmierer » 02.03.2015, 19:00

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/VisualStudio/Feedback/Details/880213
Spiele Programmierer
 
Beiträge: 341
Registriert: 23.01.2013, 16:55

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 02.03.2015, 19:28

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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 28.06.2016, 21:21

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)!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 26.03.2017, 17:39

*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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 27.05.2017, 02:30

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: Ansicht erweitern :: 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: Ansicht erweitern :: 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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon mandrill » 30.05.2017, 09:15

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: Ansicht erweitern :: 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: Ansicht erweitern :: 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.
mandrill
 
Beiträge: 2
Registriert: 30.05.2017, 08:52

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 30.05.2017, 11:27

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.)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon mandrill » 31.05.2017, 11:05

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 ;)
mandrill
 
Beiträge: 2
Registriert: 30.05.2017, 08:52

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 02.06.2017, 10:32

Geil; danke! Mein Upvoting war Krampf genug; will nicht wissen, durch welche brennenden Ringe du hüpfen musstest, um das Ticket anzulegen …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 14.07.2017, 01:07

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
packed unpacked perf.png (10 KiB) 610-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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 14.07.2017, 01:09

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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 14.07.2017, 01:51

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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: [C++] Mikrooptimierungs-Log

Beitragvon Krishty » 20.07.2017, 12:29

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: Ansicht erweitern :: 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: Ansicht erweitern :: 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: Ansicht erweitern :: 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: Ansicht erweitern :: 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: Ansicht erweitern :: 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: Ansicht erweitern :: 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: Ansicht erweitern :: 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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Jammer-Thread

Beitragvon Krishty » 05.08.2017, 02:20

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: Ansicht erweitern :: 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: Ansicht erweitern :: 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: Ansicht erweitern :: 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: Ansicht erweitern :: 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!).
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 5973
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Jammer-Thread

Beitragvon Spiele Programmierer » 05.08.2017, 12:28

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.)
Spiele Programmierer
 
Beiträge: 341
Registriert: 23.01.2013, 16:55

VorherigeNächste

Zurück zu Artikel, Tutorials und Materialien

Wer ist online?

Mitglieder in diesem Forum: Linkdex [Bot] und 2 Gäste