Array Designators in C++ 20 [Erledigt]

[HarteWare]

@Steffo
Da geht die Frage weiter... wofür char in ein Enum? Ist es für ein Lexer? Anwendung?

Meine Empfehlung ist, immer das Ziel / Plan anzugeben, anstatt lediglich nach einem selbst erdachten Lösungsweg X nachzufragen. Oft lernt man dadurch noch viel mehr, weil es vielleicht noch bessere Lösungswege Y oder Z gäbe.

Also ich in meiner Na­i­vi­tät würde sowas machen:

Foo charToFoo(char myChar) {
    switch (myChar) {
    case 'P':
        return Foo::P;
    // ....
    default:
        return Foo::Invalid;
       // oder throw, assert(false), ...
    }
}

Das switch-Case wird vermutlich vom Compiler so gut es geht umgesetzt. Wenn die Wertebereiche entsprechend sind, kann das durchaus auch in eine Art" Lookup-Table" kompiliert werden.

Oder man versucht irgendwie sowas, wobei man aufpassen sollte, dass myChar auch wirklich in ein gültiges Foo resultiert.

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

Foo charToFoo(char myChar) {
    // .. somehow check valid range of myChar, e.g., perhaps https://stackoverflow.com/questions/4969233/how-to-check-if-enum-value-is-valid
    return static_cast<Foo>(myChar);
}

Oder die Kombination aus beiden (es hängt einfach da von ab, ob es immer eine sinnvolle Abbildung char->Foo gibt):

    switch (myChar) {
    case 'P': 
    case 'N':
    case 'B':
    // ...
        return static_cast<Foo>(myChar);
    // ....
    default:
        return Foo::Invalid; // or throw, assert(false), ...

Hier ein praktisches Beispiel aus einem Taschenrechner Lexer Teil (kein Anspruch auf Perfektion):

// ...

enum class Kind : char {
    End,
    Invalid,
    Number,
    String,
    Parallel,
    Print,
    FloorDiv,
    Delete,
    FuncDef,
    For,

    Plus = '+', 
    Minus = '-',
    Mul = '*', 
    Div = '/',
    Mod = '%',
    Pow = '^',
    Fac = '!',
    Assign = '=',
    Comma = ',',
    Colon = ':',

    LParen = '(',
    RParen = ')',
    LBrace = '{', 
    RBrace = '}',
    LBracket = '[',
    RBracket = ']',
};

// ...

Token TokenStream::get()
{
    char ch;
    do {
        if (!input || !input->get(ch)) 
            return ct = { Kind::End };
    } while (std::isspace(uchar(ch)) && ch != '\n');

    switch (ch) {
    case ';':
    case '\n':
        return ct = { Kind::Print };
    case '+':
    case '-':
    case '%':
    case '!':
    case '^':
    case ',':
    case '=':
    case ':':
    case '(': case ')':
    case '[': case ']':
    case '{': case '}':
        return ct = { static_cast<Kind>(ch) };
    case '*':
        return ct = parse_double_op('*', Kind::Pow, Kind::Mul);
    case '/':
        return ct = parse_double_op('/', Kind::FloorDiv, Kind::Div);
    case '|':
        return ct = parse_double_op('|', Kind::Parallel, Kind::Invalid);
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
    case '.':
        input->unget();
        *input >> ct.num;
        ct.kind = Kind::Number;
        return ct;
    default:
        return ct = parse_identifier(ch);
    }
}

// ...

P.S.: Ist überhaupt nicht böse gemeint, aber nur ein gut gemeinter Hinweis, die meisten (zumindest anfänglichen) Probleme wurden schon gelöst/gefragt/... und man wird durch eine Internetsuche oft selbstständig fündig. Ich habe z. B. bei der Suche nach "C++ char to enum" einige ähnliche Antworten gefunden.

[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:

0
6
11
32

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.