Array Designators in C++ 20 [Erledigt]

Steffo

@HarteWare Du hast absolut recht damit. Ich will nur sicher gehen, dass ein C++ Programm einem C-Programm in absolut nichts nachsteht, da es unglaublich viele C-Schachprogramme gibt und das für mich auch irgendwo ein Sprachtechnologiewettbeweb ist! Ich möchte nicht einmal, dass mein Kompilat größer als ein äquivalentes C-Programm ist.
Und wie gesagt: Da treten Maschinen gegen Maschinen an, deshalb macht man dort viele Mikrooptimierungen wie kaum sonst wo.
Und ich schaue mir schon diverse Quellen bzgl. Schachprogramme an.

hustbaer

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

Computer gegen Computer spielen lassen möchte, muss man ja irgendwie die Eingaben parsen und bei einem Wettbewerb gibt es ein Zeitfenster, bis wann die Engine eine Antwort zurückgeben muss. Deshalb muss das wirklich schnell gehen.

Überleg dir man wie viele Eingaben du da pro Spiel parsen musst. Das werden nicht viele sein, vielleicht ein paar zig bis ein paar hundert. Das ist Pillepalle, verglichen mit dem was dein Schachprogramm beim Evaluieren der Züge an Zeit verbraten wird. Das Parsen kannst du ohne Absicht gar nicht so langsam machen dass es relevant würde.

Steffo

@hustbaer Obwohl mir das klar ist, war mein Anspruch, dass keine Funktion langsamer ist als eine C-Version. Der Anspruch von C++ ja unter anderem genau das.

HarteWare

Obwohl mir das klar ist, war mein Anspruch, dass keine Funktion langsamer ist als eine C-Version

Ich kann die Idee hinter diesem Ideal schon nachvollziehen, aber praktisch gibt es in 99% der Fälle 99 wichtigere Punkte, als die letzten paar ns Performance.

In manchen Fällen ist vielleicht ein C Code (kompiliert) schneller, in manchen C++, und in einigen vielleicht gleich.
Am Ende des Tages sind auch nicht "Sprachen" schnell, sondern gute Algorithmen und Datenstrukturen sind es, und die "Compiler" erzeugen besseren oder schlechteren Maschinencode aus dem Quellcode.

Es ist auch gar nicht so trivial, für "Benchmarks" wirklich in verschiedenen Sprachen Quellcode zu schreiben, der "das gleiche" tut, also praktisch identisch ist und sich zum Vergleich eignet. Ich behaupte, in sehr vielen Fällen sind genau diese Unterschiede in Compiler, Algorithmen, Datenstrukturen und Speicherverwaltung und nicht die "Sprache" an sich ausschlaggebend.

Der Anspruch von C++ ja unter anderem genau das.

C++ hat sehr viele Ansprüche und Ziele, aber dass C++ immer schneller als C sein muss, ist meines Wissens nicht eines davon.

Meine Empfehlung: Bei der Wahl C oder C++ würde ich mir über Performanceunterschiede keine Gedanken machen, das wird praktisch nichts erbringen.

Manch eine/r würde sogar behaupten, dass das generell bei der Wahl der Programmiersprache gilt (wobei, das würde ich selbst nicht immer vertreten).
Was m. E. Sinn macht ist, Sprachen in Kategorien zu unterteilen, z. B. macht "kompiliert" v.s. "interpretiert" definitiv einen Unterschied und das wird auch immer so sein, egal wie gut oder schnell ein Interpreter auch sein mag (ja, es gibt dann auch wieder "pre-compiling" usw. aber das ist ja dann auch schon wieder "kompiliert").
Man kann auch zwischen verschiedenen "Paradigmen" gliedern wie imperativ/deklarativ.

Steffo

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

Ich hab zum Spaß mal bei Stockfish nachgeschaut, ich bin natürlich immer skeptisch, wenn sowas schon im Kommentar steht...

Ich habe deinen überarbeiteten Kommentar erst jetzt gesehen.
Ja, ich halte den Stockfish-Code für alles andere als vorbildlich. Wenn du das schon lustig findest, dann schau dir mal diesen Pull Request an, der zuerst mit einem dummen Kommentar einfach geschlossen wurde.

Zitat vom Stockfish-Moderator: "that's not an issue, the GUI can't send 0 time for a move."

Bzw. generell wird es interessant sein, über "Grammars", "Lexer"/"Scanner" und "Parser" zu lernen.

Naja, um FEN zu interpretieren, reicht tatsächlich eine simple Funktion und ich möchte nicht von der Schachwelt einen Ausflug in die Parser-Welt machen, sonst werde ich ja nie fertig.

Ich behaupte, in sehr vielen Fällen sind genau diese Unterschiede in Compiler, Algorithmen, Datenstrukturen und Speicherverwaltung und nicht die "Sprache" an sich ausschlaggebend.

Das wird gerne gesagt, aber die Praxis zeigt etwas anderes: Java-Anwendungen sind z. B. per se Speicherfresser, egal wie sehr du dir Mühe gibst. Und Python, zumindest CPython, ist verdammt langsam. Der GIL ist einfach ein Problem.

C++ hat sehr viele Ansprüche und Ziele, aber dass C++ immer schneller als C sein muss, ist meines Wissens nicht eines davon.

Nein, aber sie haben den Anspruch nicht langsamer zu sein. D. h. mindestens gleich schnell.

Mechanics

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

Java-Anwendungen sind z. B. per se Speicherfresser

Das könnte man aber hauptsächlich unter Speicherverwaltung zusammenfassen. Das Design der JVM ist sehr ungünstig, finde ich. Und das bleibt wegen Abwärtskompatibilität auch so, zumindest bisher.

Irgendwie ist niemand auf die ursprüngliche Frage eingegangen. Es geht doch eigentlich nur um syntactic sugar? Natürlich kannst du dasselbe genauso in C++ machen, musst notfalls paar mehr Zeilen Code für die Array-Initialisierung schreiben.

Steffo

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

Irgendwie ist niemand auf die ursprüngliche Frage eingegangen. Es geht doch eigentlich nur um syntactic sugar? Natürlich kannst du dasselbe genauso in C++ machen, musst notfalls paar mehr Zeilen Code für die Array-Initialisierung schreiben.

Ich kann das natürlich per Hand schreiben, ist aber sehr fehleranfällig und verdammt hässlich. Das Array besteht bspw. nicht aus 12 Elementen, sondern aus 114, da 'r' der größte ASCII-Code von char_pieces ist. Und mit constexpr scheint das auch nicht zu gehen. Zumindest habe ich das nicht hinbekommen. Ist also hässlicher und ineffizienter als in C.

hustbaer

@Steffo

#include <array>

enum class Foo : char
{
    INVALID, P, N, B, R, Q, K, p, n, b, r, q, k
};

constexpr std::array<Foo, 256> g_charToFoo = [] {
    std::array<Foo, 256> a{};
    a['P'] = Foo::P;
    a['N'] = Foo::N;
    a['B'] = Foo::B;
    a['R'] = Foo::R;
    a['Q'] = Foo::Q;
    a['K'] = Foo::K;
    a['p'] = Foo::p;
    a['n'] = Foo::n;
    a['b'] = Foo::b;
    a['r'] = Foo::r;
    a['q'] = Foo::q;
    a['k'] = Foo::k;
    return a;
} ();

constexpr Foo charToFoo(char ch) {
    return g_charToFoo[ch & 0xFF];
}

Finde ich jetzt weder besonders hässlich noch besonders fehleranfällig.

Steffo

@hustbaer Ok, besteht aus 256 Elementen. - Kann man machen...
Am Ende habe ich übrigens ein switch-case genommen.

HarteWare

@hustbaer Die C++ Syntax wird ja immer verrückter... das sehe ich jetzt zum ersten Mal, ich hab wohl in den letzten drei Jahren einiges verpasst.

constexpr std::array<Foo, 256> g_charToFoo = [] {
    std::array<Foo, 256> a{};
    a['P'] = Foo::P;
    // ...
    return a;
} ();

Steffo

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

@hustbaer Die C++ Syntax wird ja immer verrückter... das sehe ich jetzt zum ersten Mal, ich hab wohl in den letzten drei Jahren einiges verpasst.
constexpr std::array<Foo, 256> g_charToFoo = [] {
    std::array<Foo, 256> a{};
    a['P'] = Foo::P;
    // ...
    return a;
} ();

Das ist einfach nur ein Lambda-Ausdruck. Das gibt es seit C++ 11. Genauso wie std::array und constexpr. Nur scheint das aber erst seit C++ 17 zu kompilieren. Wahrscheinlich war der Konstruktor von std::array nicht immer fähig mit constexpr initialisiert zu werden.

*john 0

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

@hustbaer Ok, besteht aus 256 Elementen. - Kann man machen...

Sonst läuft man Gefahr UB zu bekommen, wenn man ein beliebiges Zeichen übergibt.

hustbaer

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

@hustbaer Die C++ Syntax wird ja immer verrückter... das sehe ich jetzt zum ersten Mal, ich hab wohl in den letzten drei Jahren einiges verpasst.
constexpr std::array<Foo, 256> g_charToFoo = [] {
    std::array<Foo, 256> a{};
    a['P'] = Foo::P;
    // ...
    return a;
} ();

Der [] { ... } Teil ist der Lambda-Ausdruck und erzeugt einen anonymen Funktor. Das () dahinter ruft den Funktor dann direkt auf. Das ganze nennt man dann "immediately invoked lambda" oder "immediately invoked function expression" (IIFE).

Man könnte es auch so schreiben:

constexpr std::array<Foo, 256> getCharToFooTable() {
     std::array<Foo, 256> a{};
     a['P'] = Foo::P;
     // ...
     return a;
}

constexpr std::array<Foo, 256> g_charToFoo = getCharToFooTable();

hustbaer

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

@hustbaer Ok, besteht aus 256 Elementen. - Kann man machen...

Ja, kann man machen
Ich sehe auch keinen Grund dagegen. Wenn schon auf Performance optimieren, dann gleich ganz. D.h. kein Range-Check vor dem Array-Zugriff. Also 256 Elemente.

Am Ende habe ich übrigens ein switch-case genommen.

Ist auch vernünftig. Das ist zwar je nach Compiler ne Spur langsamer als ein direkter Tabellenzugriff, aber wie gesagt: bei deinem Anwendungsfall kommt es auf die paar CPU-Zyklen nicht an.

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