[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: Jammer-Thread

Beitragvon Krishty » 05.08.2017, 13:45

Die Intel-Intrinsics sind bei GCC keine Intrinsics, sondern stecken in Headern – und fremde Header benutze ich nicht.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 6024
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Jammer-Thread

Beitragvon Spiele Programmierer » 05.08.2017, 14:22

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

Re: Jammer-Thread

Beitragvon Krishty » 07.08.2017, 02:48

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

Re: Jammer-Thread

Beitragvon Spiele Programmierer » 07.08.2017, 17:12

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: Ansicht erweitern :: Alles auswählen
float minimumOf(float a, float b) {
return a < b ? a : b;
}

Generiert auf allen 3 Compilern den optimalen Code.
Spiele Programmierer
 
Beiträge: 341
Registriert: 23.01.2013, 16:55

Re: Jammer-Thread

Beitragvon Krishty » 07.08.2017, 20:23

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

Re: Jammer-Thread

Beitragvon Krishty » 07.08.2017, 21:06

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

Re: Jammer-Thread

Beitragvon Spiele Programmierer » 07.08.2017, 22:58

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: Ansicht erweitern :: 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:
Zuletzt geändert von Spiele Programmierer am 07.08.2017, 23:16, insgesamt 2-mal geändert.
Spiele Programmierer
 
Beiträge: 341
Registriert: 23.01.2013, 16:55

Re: Jammer-Thread

Beitragvon Krishty » 07.08.2017, 23:15

Spiele Programmierer hat geschrieben:Hm, habe ich was verpasst?
Warum ist minps besser als minss?
Die Latenz ist gleich, aber es ist ein Byte kürzer.
Spiele Programmierer hat geschrieben:Bei float absoluteOf(float x) { return x > 0 ? x : -x; } muss ich leider GCC/Clang rechtgeben, denn die elegante Version mit and verändert das Vorzeichen wenn x = NaN ist. Clang optimiert den Code erfolgreich mit -ffinite-math-only und GCC zumindest mit -ffast-math.
Godbolt
Verdammt – ich muss hier noch /fp:fast an gehabt haben; da hast du völlig recht!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 6024
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Jammer-Thread

Beitragvon Spiele Programmierer » 07.08.2017, 23:26

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

Re: Jammer-Thread

Beitragvon Krishty » 07.08.2017, 23:30

Spiele Programmierer hat geschrieben:Bei float absoluteOf(float x) { return x > 0 ? x : -x; } muss ich leider GCC/Clang rechtgeben, denn die elegante Version mit and verändert das Vorzeichen wenn x = NaN ist.
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:
https://en.wikipedia.org/wiki/NaN hat geschrieben:The treatment of the sign bit of NaNs for some simple operations (such as absolute value) is different from that for arithmetic operations. Traps are not required by the standard.
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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 6024
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Jammer-Thread

Beitragvon MasterQ32 » 08.08.2017, 00:36

Junge Junge Junge, ihr diskutiert hier auf nem ganz schön hohen Niveau! Mal wieder alles sehr lehrreich!
Duct tape is like the force. It has a light side, a dark side, and it holds the world together.
Benutzeravatar
MasterQ32
Felix Queißner
 
Beiträge: 953
Registriert: 07.10.2012, 14:56

Re: Jammer-Thread

Beitragvon Krishty » 08.08.2017, 01:20

Ich freue mich auch, dass Spiele Programmierer mit mir spricht; endlich mal Bidirektion im Jammer-Thread :P
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 6024
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Jammer-Thread

Beitragvon Schrompf » 08.08.2017, 08:39

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.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3611
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Jammer-Thread

Beitragvon Krishty » 08.08.2017, 11:59

Es war SSE4.1, Population Count, und bei mir hattest du auch mal was AVX-Kompiliertes gegeben ;)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
 
Beiträge: 6024
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Jammer-Thread

Beitragvon Krishty » 09.08.2017, 12:14

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 …

char vector add.png


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

VorherigeNächste

Zurück zu Artikel, Tutorials und Materialien

Wer ist online?

Mitglieder in diesem Forum: Majestic-12 [Bot] und 2 Gäste

cron