3. Arrays in Templates: was macht der Compiler daraus?

Arrays in Templates: was macht der Compiler daraus?

  • T

    Im folgenden (fiktiven) Template werden mittels index viele Arrays adressiert. Die Function function bestimmt zur Laufzeit, welches fertige Template aufgerufen wird. Der Compiler generiert die beiden Funktionstemplates. Ich hoffe das richtig verstanden zu haben:

    int function(data_c & data, const int index) {
  if (index == 0) {
    return template_function<0>(data);
  else
    return template_function<1>(data);
}

template<int index>
int template_function(data_c & data) {
  // a lot of code like this:
  data[index].member21--;
  data[index].member36+=4;
  data[index].member18&=CONST_MASK_A;
  data[index].member09^=RANDOM_KEY;
  // ...
  return data[index].member45;
}

    Aber was passiert jetzt mit data[index] , wird das intern vom Compiler in eine Variable aufgelöst oder bleibt es weiterhin ein Array. Es geht mir darum, eine hohe Laufzeiteffizient zu bekommen. Auf data[index] (data[0] oder data[1]) wird andauernd zugegriffen.

    Bisher habe ich beide Funktionen für index=0 und index=1 manuell codiert und auf das 2-dimensionale Array komplett verzichtet (Klingt etwas stupide, musste aber sein, da es um Geschwindigkeit geht).

    Genauso frage ich mich, ob

    const int WHITE=0;
const int BLACK=0;
data[WHITE].member23
data[BLACK].member23

    genauso effizient (schnell) arbeitet wie

    data_white.member23
data_black.member23
    0
  • P

    es kommt drauf an was für ein Typ data_c ist. Der Compiler sieht, dass der Indeoperator (operator[]) auf ein data_c angewendet wird und macht, was immer in dem Fall richtig ist. Wenn data_c ein Pointer-Typ ist wird die entsprechende Pointer-Arithmetik angewandt, wenns ein typedef für einen vetor oder eine map ist wird deren op[] aufgerufen.

    0

  • Don´t optimize prematurely!

    Oft macht es keinen Sinn, sich besonders trickreiche Konstrukte zu überlegen mit dem Ziel, den Code schneller zu machen. Wenn der Algorithmus der Richtige ist optimiert der Compiler besser als jeder Programmierer. Wenn deine Lösung trickreich ist wird der Code komplizierter und du erschwerst dem Compiler die Optimierungsarbeit.
    Am besten benutzt du einen Profiler und untersuchst das Laufzeitverhalten deiner Anwendung. Der Profiler zeigt dir die Engstellen auf und da könntest du dann versuchen von Hand zu optimieren. Meiner Erfahrung nach bringt das aber selten etwas, und wenn doch, dann nicht viel. Die Auswahl des passenden Algorithmus ist eine viel wichtigere Entscheidung, und da wir nicht wissen, was du erreichen willst kann man wenig zu deinem Code sagen.
    Die template Lösung mit festen Indizes halte ich für nicht optimal, kannst du nicht einfach das Arrayelement per Referenz übergeben? Oder direkt auf das Element zugreifen? Da wiederholt auf das Arrayelement zugegriffen wird wird der Compiler den Zugriff optimieren, sodass weitere Zugriffe so effizient wie möglich sind.
    Du kannst ja mal einen Vergleich zwischen deinem Code und diesen beiden Schnipseln fahren:

    int function_1( data_c& data, int index )
{
  data[index].member21--;
  data[index].member36+=4;
  data[index].member18&=CONST_MASK_A;
  data[index].member09^=RANDOM_KEY;
  // ...
  return data[index].member45;
}

int function_2( data_c& data, int index )
{
  array_element_type& object = data[index];

  object.member21--;
  object.member36+=4;
  object.member18&=CONST_MASK_A;
  object.member09^=RANDOM_KEY;
  // ...
  return object.member45;
}

    Ich glaube nicht, dass da messbare Unterschiede festzustellen sind.

    PS:
    Integrale Datentypen per const zu übergeben macht keinen Sinn, es sind temporaries, die nur in der Funktion sichtbar sind.

    0
  • T

    Hallo DocShoe

    Es geht um meine Schachengine, in der fast alle Algorithmen doppelt vorhanden sind. Also für Weiss und für Schwarz. Das Problem ist der redundante Code. Die Algorithmen unterscheiden sich ja nur geringfügig. Es müssen im Grunde nur die Reihen umgekehrt werden und der Gegner gespiegelt werden:

    So ist es aktuell (Ausschnitt):

    // white rook
case PIECE_ROOK:
    board.key_pieces^=random_white_rook[from];
    board.key_pieces^=random_white_rook[to];
    board.white_rook_bitboard&=bitboard_clear[from];
    board.white_rook_bitboard|=bitboard_set[to];
    board.piece[to]=PIECE_WHITE_ROOK;
    board.moves[from]++;
    break;

// black rook
case PIECE_ROOK:
    board.key_pieces^=random_black_rook[from];
    board.key_pieces^=random_black_rook[to];
    board.black_rook_bitboard&=bitboard_clear[from];
    board.black_rook_bitboard|=bitboard_set[to];
    board.piece[to]=PIECE_BLACK_ROOK;
    board.moves[from]++;
    break;

    So könnte es aussehen (Ausschnitt):

    // white rook / black rook
case PIECE_ROOK:
    board.key_pieces^=random_rook[color][from];
    board.key_pieces^=random_rook[color][to];
    board.rook_bitboard[color]&=bitboard_clear[from];
    board.rook_bitboard[color]|=bitboard_set[to];
    board.piece[to]=piece_rook[color];
    board.moves[from]++;
    break;

    Es sind etwa 80 Algorithmen die etwa 50% der gesamten Rechenzeit konsumieren. Wenn eine neue Konstruktion zwar weniger Codierungsaifwand bedeutet aber merklich langsamer ist (> 10%) habe ich nichts davon.

    0
  • T

    Nochmal ganz kurz:

    **
    A: Mein Ziel ist es die Codemenge zu reduzieren, damit ich Änderungen und Verbesserungen nicht immer doppelt codieren muss.

    B: Die Laufzeiteffizient soll aber nicht zu sehr darunter leiden
    **

    0

  • Da hilft nur eins: Untersuch das Laufzeitverhalten mit einem Profiler. Oder bau dir einen minmalen Anwendungsfall, der das Problem beeinhaltet und schau dir an, wieviel Zeit ein (10, 1.000, 1.000.000, 100.000.000) Durchlauf benötigt (unter Windows mit QueryPerformanceCounter/QueryPerformanceFrequency). Damit sollest du abschätzen können, ob es immer noch schnell genug ist.

    0
  • Mod

    Auch wenn ich mich meinen Vorrednern bezüglich frühzeitiger Optimierung anschließen möchte: Wenn du zwei fast gleiche Algorithmen hast, dann versuch das doch mit Templates zusammenzufassen. Templates werden zur Compilezeit ausgewertet. Entsprechend können auch Arrayzugriffe mit einem Templateparameter als Index zur Compilezeit ausgewertet werden.

    0
  • T

    Eben das war genau meine Frage bzw mein Vorschlag!

    void make_move(int color, int turn, int move) {
  if (turn == WHITE)
    make_move_template<WHITE>(turn, move);
  else
    make_move_template<BLACK>(turn, move);
}

template<int color>
void make_move_template(int turn, int move) {
  switch (piece(move)) {
  // ...
  case PIECE_ROOK: 
    board.key_pieces^=random_rook[color][from]; 
    board.key_pieces^=random_rook[color][to]; 
    board.rook_bitboard[color]&=bitboard_clear[from]; 
    board.rook_bitboard[color]|=bitboard_set[to]; 
    board.piece[to]=piece_rook[color]; 
    board.moves[from]++; 
    break;
  // ...
}

    ?

    0

  • Jetzt sind wir da, wo wir am Anfang waren 😉

    Mach dir doch einfach zwei Funktionen:

    template<int Color>
void make_move( int turn, int move )
{
  ...
}

void make_move( int color, int turn, int move )
{
  ...
}

    Und miss jetzt endlich das Laufzeitverhalten 😉

    0
  • T

    mache ich ja schon, bis später... 🙂

    0

  • Nur so aus Interesse wuerde mich mal interessieren, warum du fuer schwarz anderen Code brauchst? Normalerweise kann ich doch ein zu einer gewissen Stellung, in der weiss am Zug ist, eine analoge Situation mit schwarz am Zug konstruieren, wo schwarz die gleichen Zugmoeglichkeiten bzw. Siegchancen hat. Die Zuege vor dieser Stellung interessieren fuer kaum eine Regel und sind dann auch symmetrisch - es ist also fast egal wie man zu der Stellung kommt. Also muesste dem Algorithmus die Seite eigentlich voellig egal sein. f'`8k

    Autocogito

    Gruß, TGGC (Was Gamestar sagt...)

    0
  • T

    Ja es ist auch (fast) vollkommen egal. Lediglich die Reihen (bei Bauern - Doppelschritt oder Umwandlung) sowie die Rochadefelder sind unterschiedlich. Und bei den Bewertungen eben die Vorzeichen der Boni und Mali.

    Mein Konzept war bisher möglichst speziellen Code schreiben, da dieser einfacher ist (und schneller??). Aber dadurch wird der Code redundanter.

    Ergebnisse folgen in Kürze...

    0

  • Tomahawk schrieb:

    Lediglich die Reihen (bei Bauern - Doppelschritt oder Umwandlung) sowie die Rochadefelder sind unterschiedlich. Und bei den Bewertungen eben die Vorzeichen der Boni und Mali.

    Ja, aber auch das ist voellig symmetrisch. Ich wuerde einfach eine KI fuer weiss schreiben, und wenn ich einen schwarzen Zug berechne, dann konstruiere ich die analoge weisse Position, loese diese und transformiere den Zug zurueck. f'`8k

    Gruß, TGGC (Was Gamestar sagt...)

    0
Anmelden zum Antworten