Array Designators in C++ 20 [Erledigt]



  • Hallo,

    dieser Code ist leider nicht C++ standardkonform, funktioniert aber mit C-Compilern und auch mit C++ clang:

    enum Foo
    {
        P, N, B, R, Q, K, p, n, b, r, q, k
    };
    int char_pieces[] = {
        ['P'] = P,
        ['N'] = N,
        ['B'] = B,
        ['R'] = R,
        ['Q'] = Q,
        ['K'] = K,
        ['p'] = p,
        ['n'] = n,
        ['b'] = b,
        ['r'] = r,
        ['q'] = q,
        ['k'] = k
    };
    

    Ich will hier praktisch eine extrem schnelle Map haben, die jede intelligente Implementierung schlägt.

    In Clang erhalte ich dabei die Warnung:

    array designators are a C99 extension

    Mit GCC lässt sich der Code mit C++ erst gar nicht kompilieren.

    Es geht mir wie gesagt, um einen extrem schnellen Lookup. Kann man das mit Templates oder constexpr-Funktionen ähnlich elegant implementieren? Ansonsten muss ich das von Hand machen.

    Danke im Voraus!
    Steffo



  • @Steffo Gibt's vielleicht noch ein Kontextbeispiel, inwiefern diese "schnelle Map" oder "Lookup" verwendet wird? Ich muss zugeben, für mich ergibt sich nur ein großes "Hä" im Kopf bei dem gezeigten Code.



  • @HarteWare Ich will von char nach einem Enum parsen. Z. B.

    Foo foo = char_pieces['P']; // Foo::P
    


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



  • @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',
        // ...
    }
    


  • @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));
    


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



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



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



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



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



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



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



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



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



  • @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;
    } ();
    


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



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



  • @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();
    


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


Anmelden zum Antworten