Array Designators in C++ 20 [Erledigt]

Finnegan

@Steffo sind die hier gelisteten Keys alle, die gemappt werden müssen? 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).

Ein Ansatz könnte vielleicht eine minimal perfekte Hashfunktion sein um die Größe des Lookup-Table zu reduzieren. Ein Verfahren dazu ist hier beschrieben und verspricht 1.56 Bits pro Key. Wenn ich das richtig verstehe, ließe sich der Lookup Table damit auf unter 20 Bits reduzieren und würde in einen einzigen 32-Bit Integer passen. Wie das genau funktioniert, müsste ich mir aber selbst erstmal ansehen - könnte etwas Overkill sein, das zu implementieren (sieht schon was kompliziert aus ).

Ansonsten sind das relativ wenig Werte, die hier gemappt werden sollen, da fährt man vielleicht mit einer stupiden Suche ganz gut, solange man dabei den Code so schreibt, dass alles in Registern stattfinden kann, ohne überflüssigen Speicherzugriff. Wenn ich für einen Performance-Wettbewerb einen Kandidaten ins Rennen schicken wollte, würde ich es persönlich vielleicht mit sowas hier versuchen:

#include <cstdint>
#include <iostream>
#include <bit>
#include <emmintrin.h>

enum class Foo : char
{
    INVALID = 32,
    P = 0,
    N = 1,
    B = 2,
    R = 3,
    Q = 4,
    K = 5,
    p = 6,
    n = 7,
    b = 8,
    r = 9,
    q = 10,
    k = 11
};

auto map(std::uint8_t key) -> int
{
    // Unsere "Map" in einem 128-Bit SSE-Register mit 16 8-Bit Integer-Werten.
    // Werte werden "rückwärts" angegeben, 'P' ist in unserer Map am Index 0.
    static auto m = _mm_set_epi8(
        0, 0, 0, 0,
        'k', 'q', 't', 'b',
        'n', 'p', 'K', 'Q',
        'R', 'B', 'N', 'P'
    );
    // C++20: Zählt die Anzahl der 0-Bits von "rechts" gezählt. Bei einem 
    // Suchtreffer ist das unser Index auf den wir mappen wollen, wenn der
    // Wert nicht gefunden wurde, wird hier eine 32 zurückgegeben.
    return std::countr_zero(
        static_cast<uint32_t>(
            // Kopiert das höchstwertigste Bit jedes 8-Bit Integer im SSE-Register
            // an seine korrespondierende Position im zurückgegebenen int. Wir
            // erhalten so einen int mit einem 1-Bit an der Map-Position, die mit
            // dem Key übereinstimmt, bzw. 0, wenn der Key nicht gefunden wurde.
            _mm_movemask_epi8(
                // Vergleiche Map-Regeister mit Key-Register. Ergebnis ist 0xff im
                // jeweiligen 8-Bit Integer des SSE-Registers wenn gleich, sonst 0.
                _mm_cmpeq_epi8( 
                    m,
                    // Setze alle 16 8-Bit Integer im SSE-Register auf den Wert von key.
                    _mm_set1_epi8(key) 
                )
            )
        )
    );
}

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:

https://godbolt.org/z/d9johMM47

Die "Map" ist komplett in einem 128-Bit SSE-Register gespeichert. Da passen 16 chars rein. Der Code schaut einfach nur wo im Register der gesuchte Key ist. Dank SIMD kann hier parallel in einer Instruktion gesucht werden (_mm_cmpeq_epi8).

Das hab ich natürlich nicht wirklich auf Performance getestet, sowas sollte man selbstverständlich immer messen (!) - aber die Daten sind hier sehr kompakt und haben vor allem nicht so viele Nullen im Lookup Table.

Edit: Achja, und wie die anderen schon sagten, der Rest der Schachengine wird wahrscheinlich wesentlich mehr Optimierungspotential bieten mit deutlich besserem Preis-Leistungs-Verhältnis. Es macht echt Sinn, sich erstmal darauf zu konzentrieren. "Premature Optimization" und so.

Mechanics

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

Steffo

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

HarteWare

ü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).

Ich habe erstmal ein paar Minuten (ich hoffe, es waren keine Stunden ) gebraucht, um das zu entziffern:

Wenn man dem Compiler die Werte im enum class überlässt und nur das "naive" Switch-Case schreibt, gibt er nämlich Invalid=0 und dem Rest direkt den Integer-Wert aus der ASCII Tabelle (bzw. case label Werte). Dann definiert er einen "Magic" Bitstring, welcher im Bereich B=66 bis k=114 (z. B. Breite 48-bit, passt noch super in ein Register) einfach abbildet, ob der Wert ein gültiges Foo ist (0x1d2010001d201). Falls ja, kann man direkt konvertieren, da z. B. Foo::B eben genau den Wert 66 hat, wie der char 'B'. Sonst => 0 == Invalid.

Der Punkt ist, in vielen Fällen wird der Compiler immer die beste Lösung finden, und wenn man irgendwann den Code umschreibt und sich die Umstände ändern, wird er trotzdem weiter bestmöglichst optimieren. Das ist jetzt halt glaube auch ein Spezialfall, weil das Bitfield auch noch in ein 64-Bit Register passt.

Das ist jetzt nicht vollständig, aber so gaaanz grob:

MOV  RBP, 0x1d2010001d201
MOV  myChar, ...
SUB  myChar, 0x42  // hehe, 42 ist eben die Antwort auf alles, auch der HEX Wert von B=66
CMP  myChar, 0x30 // hier wird noch geprüft, dass myChar <= länge max. Bitfeld (48) / noch im Wertebereich ist
BT   RBP, myChar  // die nächsten Instruktionen prüfen, ob für den Char im gültigen Wertebereich das 'myChar'-te Bit in RBP gesetzt ist, z. B. 'B'->1, 'a'->0
SETC myChar
CMP  myChar, 0x1

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