Array Designators in C++ 20 [Erledigt]
-
Ich habe mir mal die Mühe gemacht, um das zu benchmarken. Mit clang 13 bekomme ich Ergebnisse, die für mich so keinen Sinn machen. Z. B. dass eine lineare Suche schneller ist als ein switch-case. Wechselt man auf clang 10, machen die Ergebnisse mehr Sinn. Die clang-13-Ergebnisse kann ich auf Apple Silicon übrigens auch nicht bestätigen. Ich habe fast den Eindruck, dass das
DoNotOptimizeMakro unter clang 13 nicht funktioniert (EDIT: Scheint eher so, dass clang 13 loop unrolling bei kleinemstd::vectormacht).
Die Ergebnisse sehen unter GCC 12.2 auch eher wie erwartet aus.https://quick-bench.com/q/-VGjD7zGGRcxExQVIF55wKN4la8
EDIT: Unter Apple Silicon erhalte ich mit clang 13 folgende Ergebnisse:
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- Enum 0.305 ns 0.305 ns 1000000000 flatMapToEnum 0.303 ns 0.303 ns 1000000000 charToEnumSwitchCase 0.304 ns 0.303 ns 1000000000 simulatedArrayDesignatorsBench 0.304 ns 0.303 ns 1000000000
-
@Steffo sagte in Array Designators in C++ 20 [Erledigt]:
Ich habe mir mal die Mühe gemacht [...]
Hey cool, Danke! quick-bench.com war mir völlig entfallen, das ist ja so simpel wie Godbolt. Ich dachte schon ich muss das erst noch lokal zusammenstricken
Auffällig ist, dass es laut deiner Tabelle de facto keinen Unterschied zwischen den Varianten gibt, ich denke da stimmt etwas nicht. Ich vermute, das könnte daran liegen, dass du alles gegen das fixe
figures-Array testest, das selbst nicht mitDoNotOptimizemarkiert wurde und daher an Compiler-Optimierungen wie Konstantenfaltung teilnimmt. Es würde mich nicht wundern, wenn der Compiler hier das komplette Ergebnis der Schleife vorberechnet hat.Die andere Erklärung für die gleichen Ergebnisse wäre, dass der Compiler so gut ist, dass er quasi alle Varianten in den selben optimalen Maschinencode übersetzt - daran glaube ich aber nicht wirklich
Ich denke Random Input das selbst
DoNotOptimizeist, liefert hier ein besseres Ergebnis. Wir wollen ja auch nicht immer dasselbe Zugriffsmuster auf die Map testen. Ich schau grad mal, wie man das macht und bau es in das Benchmark ein.
-
@Steffo sagte in Array Designators in C++ 20 [Erledigt]:
Die Ergebnisse sehen unter GCC 12.2 auch eher wie erwartet aus.
Mit deiner Variante optimiert der Compiler bei einigen Varianten alles weg, weil die Inputs konstant sind. Was ja nicht realistisch ist, die Inputs sind im Produktivcode ja dynamisch.
Einfacher Fix:
constexpr std::array<uint8_t, 12>zustd::array<uint8_t volatile, 12>ändern: https://quick-bench.com/q/nYKX8-wHsarywTpKrH9-KZG49XM
Damit bekommst du dann auch eher glaubhafte Ergebnisse.
-
@hustbaer Ok, das sieht realistischer aus, aber die lineare Suche ist unter clang 13 immer noch schneller als switch-case.
-
@Finnegan sagte in Array Designators in C++ 20 [Erledigt]:
Aus dem Bauch heraus würde ich beim Mikrooptimieren versuchen, die Datenmenge, die angefasst werden muss zu reduzieren und überlegen, ob sich die Lookup-Funktion nicht irgendwie berechnen lässt, statt das Ergebnis aus dem Speicher zu lesen. Immerhin ist der Lookup Table so 256 Bytes gross (= 4 Cache Lines).
Also erstmal müssen nicht 4 Cache-Lines geladen werden nur weil der Table 256 Byte gross ist. Wenn die Inputs immer legal sind, dann müssen max. 2 Cache-Lines geladen werden, weil alle Codes ASCII sind (0-127). Die anderen 128 Einträge sind bloss da damit man auch ungültige Inputs ohne Range-Check korrekt verarbeiten kann.
Davon abgesehen...
Es kann natürlich Fälle geben wo auch die 2 Cache Lines weh tun. Allerdings darf man dabei auch nicht auf den Code vergessen. Wenn man z.B. 64+ Byte Code braucht um eine Line im Daten-Cache zu sparen ist das vermutlich kein Gewinn. Eher ein Verlust, da die 64+ Byte Code vermutlich mehr CPU Zyklen brauchen als ein einfacher Array-Zugriff.
Bei Datenstrukturen die mehrfach im Speicher liegen sieht die Sache natürlich oft anders aus. Denn den Code gibt's da ja trotzdem nur 1x, aber der Druck auf den Daten-Cache wächst mit der Anzahl der Instanzen.
-
Hier mal mit zufälligem Zugriff: https://quick-bench.com/q/JHe84jaotiBIS7reup7HBvDX9F8
Seltsam: Auch hier ist die lineare Suche in Stück schneller als ein switch-case.
-
@hustbaer sagte in Array Designators in C++ 20 [Erledigt]:
@Finnegan sagte in Array Designators in C++ 20 [Erledigt]:
Aus dem Bauch heraus würde ich beim Mikrooptimieren versuchen, die Datenmenge, die angefasst werden muss zu reduzieren und überlegen, ob sich die Lookup-Funktion nicht irgendwie berechnen lässt, statt das Ergebnis aus dem Speicher zu lesen. Immerhin ist der Lookup Table so 256 Bytes gross (= 4 Cache Lines).
Also erstmal müssen nicht 4 Cache-Lines geladen werden nur weil der Table 256 Byte gross ist. Wenn die Inputs immer legal sind, dann müssen max. 2 Cache-Lines geladen werden, weil alle Codes ASCII sind (0-127). Die anderen 128 Einträge sind bloss da damit man auch ungültige Inputs ohne Range-Check korrekt verarbeiten kann.
Ja, hatte da die Gesamt-Datenmenge im Kopf, die während mehrerer Abfragen angefasst werden muss. Das mit dem ASCII hab ich allerdings nicht bedacht - wenn man da nur gültige Eingaben hat, dann sind es tatsächlich nur 2 Zugriffe ...
Davon abgesehen...
Es kann natürlich Fälle geben wo auch die 2 Cache Lines weh tun. Allerdings darf man dabei auch nicht auf den Code vergessen. Wenn man z.B. 64+ Byte Code braucht um eine Line im Daten-Cache zu sparen ist das vermutlich kein Gewinn. Eher ein Verlust, da die 64+ Byte Code vermutlich mehr CPU Zyklen brauchen als ein einfacher Array-Zugriff.
... womit es natürlich ganz schön eng für den extra Code wird, den besonders die Bitschubserei in meiner nicht-SIMD-Variante benötigt. Ist ja ganz nett, dass man alle Werte in einer Instruktion vergleichen kann, aber der Code um aus dem Ergebnis den Index rauszufischen, wo im SIMD-Register jetzt die 0xff steht, ist auch nicht ganz ohne. 64 Bytes sind schnell aufgebraucht.
-
@Finnegan Mich würde mal interessieren, wie es kommt, dass du so fit in SIMD bist. Bist du im Embedded-Umfeld unterwegs? Hattest du schon immer mit Assembler zu tun, was ja SIMD sehr nahe ist? Kennst du gute Literatur dazu?
-
@Steffo sagte in Array Designators in C++ 20 [Erledigt]:
@Finnegan Mich würde mal interessieren, wie es kommt, dass du so fit in SIMD bist. Bist du im Embedded-Umfeld unterwegs? Hattest du schon immer mit Assembler zu tun, was ja SIMD sehr nahe ist? Kennst du gute Literatur dazu?
Ne, ehrlich gesagt hab ich nur ne grundlegende Vorstellung, wie das mit den SIMD-Registern funktioniert und hab mir die geeigneten Funktionen beim Intel Intrinsics Guide rausgefischt ... ist also gut möglich, dass das noch etwas effizienter geht
Bin eher jemand, der sich solche Sachen gerne "on-the-fly" erarbeitet, wenn sie gerade gebraucht werden.
-
Zum Thema*switch-Case und langsam, ist auch unfair, dass man gerade hier einthrowauf dendefaultZweig packt, anstattreturn INVALID;
Die Codes waren auch nicht alle identisch, manche konnten z. B. mit einem ungültigen Zeichen umgehen, manche nicht (z. B. "Enum", ist für mich eigentlich schon "disqualifiziert", weil es nur gültige Inputs "kann", außer es war lediglich als Baseline gedacht).
Ich denke, in den meisten Fällen sind entweder dasarrayvon hustbaer oder einswitchoptimal.@Steffo sagte in Array Designators in C++ 20 [Erledigt]:
Macht jetzt keinen großen Unterschied:
Bei mir schon mit GCC 12.2. https://quick-bench.com/q/MCV2GX0TpN7faVc0MbOhBFxbnQ8
*Aber stimmt, vielleicht lag es nicht unbedingt am throw, sondern am anderen Compiler
-
@HarteWare sagte in Array Designators in C++ 20 [Erledigt]:
Zum Thema
switch-Case und langsam, ist auch unfair, dass man gerade hier einthrowauf dendefaultZweig packt, anstattreturn INVALID;Macht jetzt keinen großen Unterschied:
https://quick-bench.com/q/pvL0qPNX3wZ2a9WVuGVijQq6Jhs
