Array Designators in C++ 20 [Erledigt]

Steffo

@HarteWare Es ist für ein Schach-Programm und ich muss da auch Eingaben parsen (siehe FEN-Notation). Ich bin damit noch nicht fertig und bin mir noch nicht 100 % sicher, wie das am Ende funktioniert, aber wenn man bspw. 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.

Ich glaube, die Lösung ist ziemlich genial und wahrscheinlich deutlich schneller als die C-Lösung. - Danke!

enum class Foo : char {
    P = 'P',
    N = 'N',
    // ...
}

HarteWare

@Steffo Ich bin mir (auch wieder ohne es wirklich zu wissen) ziemlich sicher, dass bei einem Schachprogramm der Flaschenhals nicht an der Konvertierung des Eingabestrings in interne Tokens liegen wird.
D. h. die eigentliche Berechnung / Analyse des nächsten Zuges müsste doch den Großteil der Rechenarbeit ausmachen.

In dem Fall würde ich auch hier empfehlen, mal nach dem "Ziel/Plan" zu suchen, bsp. suche nach "C++ Forsyth-Edwards-Notation (FEN) Parser" oder ähnliches. Gibt's bestimmt schon viel Material dazu Bzw. generell wird es interessant sein, über "Grammars", "Lexer"/"Scanner" und "Parser" zu lernen.

Es kann ein sehr schönes Projekt mit großem Lerneffekt sein, für eine überschaubare Grammatik einen Recursive-Descent-Parser von Hand zu schreiben. Das ist zumindest soweit ich weiß die einfachste Methode, wenn man es "von Hand" implementiert.

Falls Du eher lösungsorientiert arbeiten möchtest (d. h. Du willst weniger jetzt lernen, wie das FEN einzulesen ist, und lieber direkt mit dem Rest des Programms weitermachen), könnte es auch einen Versuch wert sein, über Parser-Generator wie ANTLR den Parser zu erzeugen, oder eine fertige C++ Bibliothek einzubinden, welche das bereits kann.

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

/// Position::set() initializes the position object with the given FEN string.
/// This function is not very robust - make sure that input FENs are correct,
/// this is assumed to be the responsibility of the GUI.

lach, "famous last words"

Die machen das dann so (ob das besser ist? fragwürdig....):

// ...
enum Piece {
  NO_PIECE,
  W_PAWN = PAWN,     W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
  B_PAWN = PAWN + 8, B_KNIGHT, B_BISHOP, B_ROOK, B_QUEEN, B_KING,
  PIECE_NB = 16
};
// ...
constexpr std::string_view PieceToChar(" PNBRQK  pnbrqk");

// ...
size_t idx;
if (idx = PieceToChar.find(token) != string::npos)
          do_something(Piece(idx));

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