Array Designators in C++ 20 [Erledigt]

Finnegan

@Mechanics sagte in Array Designators in C++ 20 [Erledigt]:

@Finnegan sagte in Array Designators in C++ 20 [Erledigt]:

Ein Verfahren dazu ist hier beschrieben und verspricht 1.56 Bits pro Key.

Das kommt mir zu kompliziert vor, um schnell zu sein - den Hash müsste man auch zur Laufzeit beim Suchen berechnen.
Wäre aber schon interessant, wenn das jemand ausprobieren könnte!

Es gibt schon oft die Situation, dass die CPU hauptsächlich damit beschäftigt ist, auf den Speicher zu warten, gerade bei Suche in großen Datenmengen. Ich kann mir schon vorstellen, dass man manchmal besser fährt, wenn man stattdessen etwas mehr berechnet und dafür Speicherzugriffe spart. Muss man aber alles ausprobieren :).

@HarteWare sagte in Array Designators in C++ 20 [Erledigt]:

überlegen, ob sich die Lookup-Funktion nicht irgendwie berechnen lässt

Genau so schlau ist nämlich der C++ Compiler beim Switch-Case, wenn ich den Maschinencode richtig verstehe... ziemlich interessant!
Der Compiler macht meistens das Schlauste. Bei mir irgendwas mit einem Bitfield / Bit-Test (BT Instruktion).

Ja, das ist ein Klassiker, dass man versucht, schlauer als der Compiler zu sein. Daher auch immer messen und bei Bedarf den generierten Maschinencode vergleichen. Das würde ich auch hier vorschlagen: Gut möglich, dass man sogar den Compiler dabei behindert, gute Optimierungen zu finden wenn man hier frühzeitig auf eine vermeintliche Optimierung wie Lookup Tables setzt. Das mag Sinn machen, wenn man direkt in Assembler programmiert, aber wenn da noch ein Compiler-Optimizer dazwischen ist, sollte man nicht den Assembler-Code optimieren, den man zu schreiben glaubt, sondern den Output des Optimizers.

@Steffo sagte in Array Designators in C++ 20 [Erledigt]:

@Finnegan Danke, für die Mühe! Mit SIMD-Instruktionen möchte ich erst einmal nicht hantieren, da nicht portabel. Habe außerdem ein Apple Silicon.
Ich kann mir auch kaum vorstellen, dass das schneller als ein switch-case ist.

Kein Problem, ist auuch wie oben erwähnt wahrscheinlich eh viel zu verfrüht, hier was zu Optimieren. Ich hab das hauptsächlich aufgegriffen, weil ich das für mich ein interessantes Problem war - vor allem wegen den wenigen Keys.

Genau deshalb hab ich mir den Spass gemacht, das ganze auch nochmal "portabel" per Bitschubser-Voodoo umzusetzen, das ohne SIMD-Instruktionen auskommt - selbe Idee nur das "SIMD" innerhalb eines uint32_t mit Bitoperationen zusammengestrickt. Wen's interessiert:

#include <cstdint>
#include <iostream>
#include <bit>

auto set(
    std::uint8_t v1,
    std::uint8_t v2,
    std::uint8_t v3,
    std::uint8_t v4
) -> std::uint32_t
{
    return (std::uint32_t{ v1 } << 24) 
        + (std::uint32_t{ v2 } << 16)
        + (std::uint32_t{ v3 } << 8)
        + std::uint32_t{ v4 };
}

auto compare(std::uint32_t v1, std::uint32_t v2) -> std::uint32_t
{
    auto v = v1 ^ v2;
    v |= (v & 0xf0f0f0f0) >> 4;
    v |= (v & 0xcccccccc) >> 2;
    v |= (v & 0xaaaaaaaa) >> 1;
    return ~((v & 0b1) 
        | ((v >> 7) & 0b10)
        | ((v >> 14) & 0b100 )
        | ((v >> 21) & 0b1000)) & 0xf;
}

auto map(std::uint8_t key) -> int
{
    static std::uint32_t m[] = {
        set('R', 'B', 'N', 'P'),
        set('n', 'p', 'K', 'Q'),
        set('k', 'q', 't', 'b')
    };
    auto v = set(key, key, key, key);
    return std::countr_zero(
        compare(v, m[0])
        | (compare(v, m[1]) << 4)
        | (compare(v, m[2]) << 8)
    );
}

auto main() -> int
{
    std::cout << map('P') << std::endl;
    std::cout << map('p') << std::endl;
    std::cout << map('k') << std::endl;
    std::cout << map('I') << std::endl;
}

Ausgabe wie gehabt:

https://godbolt.org/z/x66vcEzrY

Frage mich da aber, ob man da nicht schon besser einfach ne lineare Suche über die 12 Einträge macht - da dürfte der Compiler auch einiges optimieren können, wenn es ein (de facto compile-time) kostantes Array ist - wahrschelnlich packt der das auch in ein, zwei Register.

Jetzt wärs echt mal an der Zeit sowas wie Google Benchmark anzuwerfen um zu sehen was am besten abschneidet: Compiler-Optimizer mit bodenständigem switch/case, 256-Byte LUT, SSE2-Mikro-Map oder die portable "SWAR im uint32_t"-Variante ... vielleicht find ich die Tage noch die Motivation dazu

Steffo

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 DoNotOptimize Makro unter clang 13 nicht funktioniert (EDIT: Scheint eher so, dass clang 13 loop unrolling bei kleinem std::vector macht).
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

Finnegan

@Steffo sagte in Array Designators in C++ 20 [Erledigt]:

Ich habe mir mal die Mühe gemacht [...]

https://quick-bench.com/q/-VGjD7zGGRcxExQVIF55wKN4la8

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 mit DoNotOptimize markiert 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 DoNotOptimize ist, 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.

hustbaer

@Steffo sagte in Array Designators in C++ 20 [Erledigt]:

Die Ergebnisse sehen unter GCC 12.2 auch eher wie erwartet aus.

https://quick-bench.com/q/-VGjD7zGGRcxExQVIF55wKN4la8

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> zu std::array<uint8_t volatile, 12> ändern: https://quick-bench.com/q/nYKX8-wHsarywTpKrH9-KZG49XM
Damit bekommst du dann auch eher glaubhafte Ergebnisse.

Steffo

@hustbaer Ok, das sieht realistischer aus, aber die lineare Suche ist unter clang 13 immer noch schneller als switch-case.

hustbaer

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

Steffo

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.

Finnegan

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

Steffo

@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?

Finnegan

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

HarteWare

~~Zum Thema switch-Case und langsam, ist auch unfair, dass man gerade hier ein throw auf den default Zweig packt, anstatt return 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 das array von hustbaer oder ein switch optimal.

@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

Steffo

@HarteWare sagte in Array Designators in C++ 20 [Erledigt]:

Zum Thema switch-Case und langsam, ist auch unfair, dass man gerade hier ein throw auf den default Zweig packt, anstatt return INVALID;

Macht jetzt keinen großen Unterschied:
https://quick-bench.com/q/pvL0qPNX3wZ2a9WVuGVijQq6Jhs