[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.
mrz
Beiträge: 79
Registriert: 07.08.2008, 14:34

Re: Jammer-Thread

Beitrag von mrz »

MasterQ32 hat geschrieben:Junge Junge Junge, ihr diskutiert hier auf nem ganz schön hohen Niveau! Mal wieder alles sehr lehrreich!
Dem kann ich mich nur anschliessen.

Und wünsche mir dass ihr resp Krishty seine Entdeckungen auch jeweils den Jungs von Clang/LLVM
meldet damit ich irgendwann auch indirekt davon profitiere.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Ganz ehrlich … die Zeit habe ich nicht. Wenn ich ein Patreon aufmache, und ihr mich dafür durchfüttert, dann vielleicht. Aber jetzt nicht auch noch Bug Tracker füttern, bitte nicht. Das kann jemand machen, der hier mitliest.

Ich habe eben fast eine Stunde(!) an der Konvertierung von unsigned char zu unsigned int gesessen. Dass GCC zwei Register nullt statt einem, das muss jemand anders melden. Ich krieg’s nicht gelöst und mein Hirn ist erstmal Matsche.

Code: Alles auswählen

// Expands all elements to 4-B signed integers.
SInt4Bx4 SIMD_CALL asSInt4B(UInt1Bx4 const v) {
	// • interleave each 1-B lane with three zero bytes
	//   – first interleave each 1-B lane with 1 B of zeroes via SSE2’s PUNPCKLBW
	//   – then interleave each 2-B lane with 2 B of zeroes via SSE2’s PUNPCKLWD

#	if COMPILED_BY_VISUAL_CPP
		// • PUNPCKLBW is available via “_mm_unpacklo_epi8()” intrinsic
		// • PUNPCKLWD is available via “_mm_unpacklo_epi16()” intrinsic
		auto const v0v0v0v0         = _mm_unpacklo_epi8(v.uints, _mm_setzero_si128());
		auto const v000v000v000v000 = _mm_unpacklo_epi16(v0v0v0v0, _mm_setzero_si128());
		return { v000v000v000v000 };
#	elif COMPILED_BY_CLANG
		// • Clang’s code generation miserably fails vector initializer lists and vector casting
		// • no intrinsics available; need to use “__builtin_shufflevector()” instead
		auto const v0v0v0v0         = (IMPL_UINT2BX8)__builtin_shufflevector(v.uints, IMPL_UINT1BX16(), 0, 16, 1, 17, 2, 18, 3, 19, 4, 20, 5, 21, 6, 22, 7, 23);
		auto const v000v000v000v000 = (IMPL_SINT4BX4)__builtin_shufflevector(v0v0v0v0, IMPL_UINT2BX8(), 0, 8, 1, 9, 2, 10, 3, 11);
		return { v000v000v000v000 };
#	elif COMPILED_BY_GCC
		// • PUNPCKLBW is available via “__builtin_ia32_punpcklbw128()” intrinsic
		// • PUNPCLWD is available via “__builtin_ia32_punpcklwd128()” intrinsic
		// • code generation fails miserably with anything else
		// • TODO: for some reason, GCC zeroes two registers instead of one (not even Visual C++ fails here)
		auto const v0v0v0v0         = (IMPL_SINT2BX8)__builtin_ia32_punpcklbw128((IMPL_CHARX16)v.uints, IMPL_CHARX16());
		auto const v000v000v000v000 = (IMPL_SINT4BX4)__builtin_ia32_punpcklwd128(v0v0v0v0, IMPL_SINT2BX8());
		return { v000v000v000v000 };
#	endif
}
GCC erzeugt

  pxor xmm1, xmm1
  punpcklbw xmm0, xmm1
  pxor xmm1, xmm1
  punpcklwd xmm0, xmm1
  ret


und ich denke nicht, dass das doppelte pxor xmm1, xmm1 (Register auf Null setzen) eine blöde verpasste Optimierung ist, sondern dass im Gegenteil GCC zu stark zu optimieren versucht – wahrscheinlich etwas wie „das zweite Nullen kann ich die CPU unabhängig vom ersten ausführen lassen, damit es schneller fertig wird“ ohne zu begreifen, dass die Befehle sowieso aufeinander aufbauen und man deshalb nichts nebenläufig schedulen kann.

1.800 Zeichen, um drei Assembler-Befehle zu erzeugen. Mit direkter Nutzung der Intrinsic-Header (was jeder tun würde, der nicht bekloppt wie ich ist) wären es immernoch 665. Den Assembler-Code direkt hinschreiben wären … weniger als 100. Aber das darf ich ja nicht, denn Inline Assembly verwirrt die Compiler! Zum Kotzen. Einfach nur zum Kotzen. Seht, wie viel Zeit sie uns gespart haben mit ihrer portablen, leicht verständlichen, allmächtigen, Vektorsyntax! (CAST)__builtin_shufflevector((CAST)am, (CAST)arsch, 0, 13, 4, 9, 42, 36, Superzahl 666, achlecktmichdoch
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Ich bin immer noch bei WIRKLICH trivialen Funktionen und wollte mal was machen, das zu mehr als fünf Befehlen führt … OMFG, da geht alles schief.

Nehmen wir mal das hier:

  __m128i multiply_r8g8b8a8(__m128i l, __m128i r)

Zwei Farben multiplizieren, die als 8-Bit RGBA vorliegen. Nichts ausgefallenes. Kein Linear Color Space Blending. Kein garnichts. Trivial wäre:

  return {
    l.m128i_u8[0] * r.m128i_u8[0] / 255,
    l.m128i_u8[1] * r.m128i_u8[1] / 255,
    l.m128i_u8[2] * r.m128i_u8[2] / 255,
    l.m128i_u8[3] * r.m128i_u8[3] / 255
  };


Im Internet findet man viele Leute, die nicht einmal das schaffen. Die teilen durch 256. WTF?! 255 * 255 / 256 != 255. Eure Farben werden mit jedem Blending dunkler. Aber was weiß ich schon – ihr könnt eine Division durch Bit Shifting ersetzen. Ihr kennt euch mit Optimierung aus.

Die Befehle, die Visual C++ dafür ausspuckt, sind nicht der Rede wert: 37 Stück. Jeder unsigned char wird extrahiert, multipliziert, dividiert (die Division wird zu Shifts/Addition/Subtraktion optimiert), dann wieder zurückgeschrieben. Einerseits enttäuschend, andererseits haben wir aber die oberen 12 Bytes nicht definiert und der Compiler denkt nun, dass wir da unbedingt Nullen drin haben wollen und damit ist das alles schlecht optimierbar.

Auf Clang/GCC kompiliert das nicht, da muss man deren Vektorsyntax verwenden. Erstmal GCC mit 4×unsigned char:

  using UINT1BX4 = unsigned char __attribute__((vector_size(4)));
  UINT1BX4 mul_r8g8b8a8(UINT1BX4 l, UINT1BX4 r) {
    return l * r / 255;
  }


Etwa gleich viele Befehle wie Visual C++, nur dass die Vektorregister komplett übergangen werden. RICHTIG katastrophal auf Clang (mit richtigen skalaren Divisionen, man kann’s sich nicht ausdenken!). Erzwingen wir SSE durch 16 Vektorkomponenten:

  using UINT1BX4 = unsigned char __attribute__((vector_size(16)));
  UINT1BX4 mul_r8g8b8a8(UINT1BX4 const l, UINT1BX4 const r) {
    return l * r / (UINT1BX4){ 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255 };
  }


(ohne die lange Liste von 255ern frisst Clang es nicht)

29 Befehle in Clang; rund 125 in GCC. Beide fangen nun an, Vektorbefehle zu benutzen und z.B. vier Zahlen parallel zu multiplizieren. Nicht, dass es was helfen würde. Füttern wir nochmal genau die gleiche Beschreibung rein wie damals Visual C++, nur in Clang/GCC-Syntax:

  using UINT1BX4 = unsigned char __attribute__((vector_size(16)));
  UINT1BX4 mul_r8g8b8a8(UINT1BX4 const l, UINT1BX4 const r) {
    return (UINT1BX4){
      (unsigned char)(l[0] * r[0] / 255),
      (unsigned char)(l[1] * r[1] / 255),
      (unsigned char)(l[2] * r[2] / 255),
      (unsigned char)(l[3] * r[3] / 255)
    };
  }


33 Befehle in Clang, 45 in GCC, und beide umgehen Vektorisierung fast komplett.

Erstmal ist sicher: Autovektorisierung, SIMD-Syntax usw. kann man in die Tonne kloppen. Will man ordentlichen SIMD-Code, muss man von Hand Intrinsics aufrufen. Dummerweise ist das nur in Visual C++ einfach; in GCC noch umständlich möglich; in Clang quasi unmöglich.

„Einfache“ Intrinsics à „multiplizier den Vektor hier mit dem da“ gibt es nur, so lange man mit 4×float arbeitet. In alles andere muss man sich erstmal einarbeiten (es gibt um die 20 verschiedenen Intrinsics für Integermultiplikation, und fast keiner davon berechnet tatsächlich das Produkt).

Hier der beste skalare Compiler (Clang im letzten Versuch):

Code: Alles auswählen

  movdqa xmmword ptr [rsp - 40], xmm0
  movzx r8d, byte ptr [rsp - 37]
  movzx r9d, byte ptr [rsp - 38]
  movzx r10d, byte ptr [rsp - 39]
  movzx edi, byte ptr [rsp - 40]
  movaps xmmword ptr [rsp - 24], xmm1
  movzx edx, byte ptr [rsp - 21]
  movzx esi, byte ptr [rsp - 22]
  movzx eax, byte ptr [rsp - 23]
  movzx ecx, byte ptr [rsp - 24]
  imul ecx, edi
  mov edi, 2155905153
  imul rcx, rdi
  shr rcx, 39
  imul eax, r10d
  imul rax, rdi
  shr rax, 39
  imul esi, r9d
  imul rsi, rdi
  shr rsi, 39
  imul edx, r8d
  imul rdx, rdi
  shr rdx, 39
  shl edx, 8
  movzx esi, sil
  or esi, edx
  shl eax, 8
  movzx ecx, cl
  or ecx, eax
  pxor xmm0, xmm0
  pinsrw xmm0, ecx, 0
  pinsrw xmm0, esi, 1
  ret
Hier von Hand aufgerufene Intrinsics in Visual C++:

Code: Alles auswählen

  movaps   xmm3, xmm0
  xorps    xmm2, xmm2
  movaps   xmm4, xmm1
  punpcklbw xmm3, xmm2
  punpcklbw xmm4, xmm2
  pmullw   xmm4, xmm3
  pmulhuw xmm4, XMMWORD PTR __xmm@80818081808180818081808180818081
  psrlw    xmm4, 7
  packuswb xmm4, xmm4
  movaps   xmm0, xmm4
  ret      0
Die Division durch 255 muss man von Hand in Multiplikation + Shift umwandeln, weil das kein Compiler außer GCC mit Vektoren kann.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ich habe endlich einen großen Vorteil von Clangs Syntax gefunden: Shuffling mit undefinierten Elementen.

Liegt meine RGBA-Farbe in einem 16-Byte-SSE-Register, sind die zwölf oberen Spuren unbenutzt. Sagen wir, ich möchte die Alpha-Komponente in den unteren vier Spuren haben, und die oberen zwölf interessieren mich nicht.

Schreibe ich return { rgba[3], rgba[3], rgba[3], rgba[3] }, muss der Compiler garantieren, dass die oberen zwölf Spuren genullt sind. So fordert das C++. Dem Compiler ist nicht vermittelbar, dass sie unbenutzt sind. Das Nullen bedeutet zusätzlichen Aufwand.

Schreibe ich return { rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3], rgba[3] }, entfällt das Nullen. Der Compiler verbaut aber immernoch zu viele Befehle, um die dritte Spur nach ganz oben zu schieben.

Clang glänzt mit return { __builtin_shufflevector(rgba, rgba, 3, 3, 3, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }. Das -1 bedeutet, dass die entsprechende Spur undefiniert ist und der Compiler frei Befehle auswählen kann, so lange die unteren vier Spuren korrekt befüllt werden.

Das ist die erste Situation, in der ein Compiler meine selbstgeschriebene Intrinsic-Version deutlich abhängt. Was Clang hier teilweise über recht abwegige Befehle rausholen kann, ist beachtlich.

__builtin_shufflevector() ist auf GCC nicht verfügbar und AFAIK gibt es auch kein entsprechendes Pendant. Visual C++ kann sowieso nichts anderes als Intrinsics. Ich empfehle also, bei sowas immer erst eine Clang-Version mit __builtin_shufflevector() und undefinierten Elementen zu machen, und dann das resultierende Disassembly auf Intrinsics in GCC und Visual C++ zu übertragen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ich weiß nicht, was in den Compilern vorgeht. Zur Hölle, ich verstehe nicht, wie sowas passieren kann.

  void store(UInt1B memory[4], UINT1BX4 vector) {
    memory[0] = vector[0];
    memory[1] = vector[1];
    memory[2] = vector[2];
    memory[3] = vector[3];
  }


Das sollte ein einziges MOVD oder MOVSS sein – die unteren 4 B in einem Rutsch in den Speicher schreiben. Stattdessen Clang:

Code: Alles auswählen

  movaps xmmword ptr [rsp - 24], xmm0
  mov sil, byte ptr [rsp - 21]
  mov cl, byte ptr [rsp - 22]
  mov dl, byte ptr [rsp - 23]
  mov al, byte ptr [rsp - 24]
  mov byte ptr [rdi], al
  mov byte ptr [rdi + 1], dl
  mov byte ptr [rdi + 2], cl
  mov byte ptr [rdi + 3], sil
  ret
Visual C++:

Code: Alles auswählen

        movd     eax, xmm1
        movdqa   xmm0, xmm1
        psrldq   xmm0, 1
        mov      BYTE PTR [rcx], al
        movd     eax, xmm0
        movdqa   xmm0, xmm1
        psrldq   xmm0, 2
        psrldq   xmm1, 3
        mov      BYTE PTR [rcx+1], al
        movd     eax, xmm0
        mov      BYTE PTR [rcx+2], al
        movd     eax, xmm1
        mov      BYTE PTR [rcx+3], al
        ret      0
GCC (WTF):

Code: Alles auswählen

  movaps XMMWORD PTR [rsp-72], xmm0
  movzx eax, BYTE PTR [rsp-72]
  movaps XMMWORD PTR [rsp-40], xmm0
  movaps XMMWORD PTR [rsp-56], xmm0
  mov BYTE PTR [rdi], al
  movzx eax, BYTE PTR [rsp-39]
  mov BYTE PTR [rdi+1], al
  movzx eax, BYTE PTR [rsp-54]
  mov BYTE PTR [rdi+2], al
  movzx eax, BYTE PTR [rsp-69]
  mov BYTE PTR [rdi+3], al
  ret
… nun muss ich wieder einen zehn-Zeilen-Aufsatz schreiben:

  void store(UInt1B memory[4], UInt1Bx4 const v) {
    // • try to store four lanes at once via SSE2’s MOVD
    // • this works only when treating the four lowest lanes as a single 4-B integer

  # if COMPILED_BY_VISUAL_CPP

      // • the “_mm_cvtsi128_si32()” intrinsic casts the four lowest lanes to a 4-B integer
      *reinterpret_cast<int *>(memory) = _mm_cvtsi128_si32(v);

  # elif COMPILED_BY_CLANG || COMPILED_BY_GCC

      // • “reinterpret_cast” does not violate strict aliasing here because 1-B types may alias anything
      // • GCC’s/Clang’s code generation miserably fails anything else
      *reinterpret_cast<UInt4B *>(memory) = ((UINT4BX4)v)[0];

  # endif
  }

… und was mache ich mit Strict Aliasing und 16-Bit-Zahlen? Zu Bjarne Stroustrup beten und ihm zum Opfer meinen Computer verbrennen?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: [C++] Mikrooptimierungs-Log

Beitrag von Spiele Programmierer »

Das ist wirklich schrecklich.
und was mache ich mit Strict Aliasing und 16-Bit-Zahlen? Zu Bjarne Stroustrup beten und ihm zum Opfer meinen Computer verbrennen?
Strict Aliasing ist immer eine sehr komplizierte Angelegenheit.
Aber ich bin mir ziemlich sicher, dass dieser Code auch jetzt Strict Aliasing verletzt. Man darf zwar jeden Pointer in unsigned char* casten und damit zugreifen, aber man darf nicht in die andere Richtung jeden unsigned char* in einen beliebigen Typ casten und zugreifen. Der Pointer muss ursprünglich mit diesem Typ konstruiert/zugewiesen worden sein. Aus praktischer Sicht kann der Compiler nicht garantieren das der ursprüngliche char-Pointer das notwendige Alignment für einen anderen Typen hat. Außerdem könnte man sonst Strict Aliasing immer umgehen in dem man einfach einen Umweg über unsigned char* macht und die ganze Regel wäre zwecklos: reinterpret<T*>(reinterpret<unsigned char*>(...))

Die jeweiligen Standards sind da wohl nicht unbedingt ganz eindeutig zu interpretieren, aber der Konsens ist wohl, dass memcpy solche Probleme vermeidet: https://stackoverflow.com/questions/327 ... and-memcpy

Also das sollte gehen:

Code: Alles auswählen


void store2(UInt1B memory[4], UINT1BX4 vector)
{
#if COMPILED_BY_VISUAL_CPP
   *reinterpret_cast<int *>(memory) = _mm_cvtsi128_si32(v);
#else
    memcpy(memory, &vector, 4); // Catastrophic code generation with Microsoft
#endif
}
GCC und Clang erzeugen da perfekten Code.
Zuletzt geändert von Spiele Programmierer am 11.08.2017, 00:17, insgesamt 1-mal geändert.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ich vergaß zu schreiben: Was Strict Aliasing angeht, machen es die Intrinsic-Implementierungen in Clang & GCC intern beim Laden so:

  struct MOVD {
    int i32;
  } __attribute__((__packed__, __may_alias__));
  return (UINT1BX4)(intx4){ ((MOVD const *)memory)->i32, 0, 0, 0 };


… und beim Speichern umgekehrt.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Spiele Programmierer hat geschrieben:Das ist wirklich schrecklich.
Aber ich bin mir ziemlich sicher, dass dieser Code auch jetzt Strict Aliasing verletzt. Man darf zwar jeden Pointer in unsigned char* casten und damit zugreifen, aber man darf nicht in die andere Richtung jeden unsigned char* in einen beliebigen Typ casten und zugreifen. Der Pointer muss ursprünglich mit diesem Typ konstruiert/zugewiesen worden sein. Aus praktischer Sicht kann der Compiler nicht garantieren das der ursprüngliche char-Pointer das notwendige Alignment für einen anderen Typen hat. Außerdem könnte man sonst Strict Aliasing immer umgehen in dem man einfach einen Umweg über unsigned char* macht und die ganze Regel wäre zwecklos: reinterpret<T*>(reinterpret<unsigned char*>(...))
Das ist schon klar; in diesem Fall lade ich aber tatsächlich vier unsigned chars in einen Vektor von 16×unsigned chars, indem ich ihn kurz int uminterpretiere. Ich hätte gedacht, dass das legal ist; und schnellem Googeln nach ist es wirklich kompliziert – wahrscheinlich noch mehr, als den Compiler dazu zu bekommen, ordentlichen Code zu generieren :D

Danke für den memcpy()-Tipp; das probiere ich tatsächlich mal umzusetzen. Ich bin gespannt, wie gut/schlecht es z.B. mit oberen Hälften von Registern funktionieren wird.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Krishty hat geschrieben:Danke für den memcpy()-Tipp; das probiere ich tatsächlich mal umzusetzen. Ich bin gespannt, wie gut/schlecht es z.B. mit oberen Hälften von Registern funktionieren wird.
Ach, das wäre auch zu schön gewesen. Perfekter Code mit GCC, aber Clang sagt error: address of vector element requested. Für komplette Vektoren ist das Jackpot, aber für z.B. die obere Hälfte der Elemente muss ich weiter über struct __attribluärgh gehen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: [C++] Mikrooptimierungs-Log

Beitrag von Spiele Programmierer »

Hm, also vielleicht verstehe ich dich falsch, aber auf Godbolt scheint es zu gehen:
Click
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Argh, ich hatte &vector[12] ausprobiert! Danke :)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Spiele,

schau dir bitte mal das hier an:

https://godbolt.org/g/azjxkX

Änder das #if 1 zu #if 0 und prüf, was rauskommt. Vielleicht ist es aber auch bloß spät und ich sehe den Wald vor lauter Bäumen nicht.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Krishty hat geschrieben:Änder das #if 1 zu #if 0 und prüf, was rauskommt. Vielleicht ist es aber auch bloß spät und ich sehe den Wald vor lauter Bäumen nicht.
Das ist wohl einfach Undefined Behavior; ich nehme an du hast dich da von der Operator Precedence beißen lassen!? ;)

&result[8] ist das selbe wie &(result[8]) und gibt die Adresse des achten Elements des result vectors. &result dagegen ist die Adresse des ganzen vectors. (&result) + 8 ist dann nicht die Adresse des achten Elements von results sondern die Adresse des Vektors + 8 * sizeof(result) und das liegt definitiv außerhalb des Buffers -> UB...
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

DAS war der Wald. Ich hatte die ganze Zeit mit Schritten in sizeof result[0] gerechnet statt in sizeof result; danke :)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Artificial Mind
Establishment
Beiträge: 802
Registriert: 17.12.2007, 17:51
Wohnort: Aachen

Re: [C++] Mikrooptimierungs-Log

Beitrag von Artificial Mind »

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

Hochoptimierte Linear-Search vs. Binary-Search

Beinhaltet ASM-level analyse und Späße wie branchless binary search.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

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

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


Erzeugt:

Code: Alles auswählen

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

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

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

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

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


Erzeugt:

Code: Alles auswählen

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

fml

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

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

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

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

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

Code: Alles auswählen

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

Code: Alles auswählen

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

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

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

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

Code: Alles auswählen

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

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

Hochoptimierte Linear-Search vs. Binary-Search

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

Status leider zurückgestellt weil keine Priorität. Ihr solltet also weiterhin keine Initializer Lists zuweisen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

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

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

Code: Alles auswählen

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

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

Code: Alles auswählen

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

Trotzdem ein netter Gag mit manchmal messbaren Verbesserungen.

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Bild

Dieser Tweet machte gerade die Runde.

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

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

Aufregender ist das, aber ist es auch schneller?

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

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

Code: Alles auswählen

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

Code: Alles auswählen

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

Dann kommt Clang -O2:

Code: Alles auswählen

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

Code: Alles auswählen

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

Nun Visual C++ /O2:

Code: Alles auswählen

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

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

Aber jetzt beginnt das Lernen erst so richtig!

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

Oder?

Code: Alles auswählen

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

Code: Alles auswählen

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

Clang -O2:

Code: Alles auswählen

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

Apropos Visual C++:

Code: Alles auswählen

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

Code: Alles auswählen

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

Quintessenz

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

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

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

Ist die handoptimierte Version besser als die automatisch optimierte?

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

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

Auf GCC nicht. Das erzeugt kein BT.

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

Code: Alles auswählen

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

Code: Alles auswählen

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

… aber stattdessen solltet ihr den Compiler-Entwickler eures Vertrauens fragen, ob er das nicht direkt in den Compiler hardcoden möchte.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

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

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

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

Code: Alles auswählen

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

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

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

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

Nun betrachten wir folgenden Code:

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


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

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


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

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

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

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

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

  inline void unordered(...) { }

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

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


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

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

Also ist das komplett nutzlos. Aber man muss es eben mal probiert haben.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4831
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Aber interessante Erklärung, Danke.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Krishty hat geschrieben: 08.02.2020, 16:01 … und da die Auswertungsreihenfolge von Funktionsparametern undefiniert ist, darf der Compiler die Befehle nun umsortieren und vermengen wie er will (bzw. wie es für die CPU am effizientesten ist).
Seit C++17 ist die Initialisierung von Parametern in einem Functioncall nicht mehr unsequenced sondern indeterminately-sequenced [expr.call]/5. Es ist also zwar nicht spezifiziert, in welcher Reihenfolge die Initialisierung von Parametern genau passiert, aber es ist spezifiziert, dass es eine Reihenfolge gibt [intro.execution]/15, d.h. die Initialisierung mehrerer Parameter kann nicht überlappen…

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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

Code: Alles auswählen

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

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

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

Code: Alles auswählen

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

Code: Alles auswählen

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

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

Re: [C++] Mikrooptimierungs-Log

Beitrag von xq »

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

Code: Alles auswählen

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

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