Arrayindex zur Compilezeit oder zur Laufzeit?

Tomahawk

Wäre der Code in B laufzeiteffizienter (schneller) als der Code in A? Ich bin mir nicht sicher, ob Version B etwas bringt, ich schätze mal die Executable wird deutlich grösser, wenn ich alle Algorithmen einer Schach-KI so aufbaue. Bevor ich es teste, würde mich eure Meinung dazu interessieren, ob es einen messbaren Unterschied macht, wenn die Arrayindices (0 oder 1) innerhalb der Hauptfunktionen (also den Templates) bereits zur Compilezeit bekannt sind (Version B).

Ist eine solche Konstruktion mit Templates (Version B) wie in diesem vereinfachten und stark gekürzten Beispiel sinnvoll?

Danke schonmal für eure Statements

A

void do_something(int me, int you, int move) {
  int from;
  int to;

  from=move_from(move);
  to=move_to(move);

  piece_on[from]=PIECE_NONE;
  piece_bb[me]&=clear_bb[from];
  piece_bb[me]|=set_bb[to];

  piece_bb[you]&=clear_bb[to];
  knight_bb[you]&=clear_bb[to];
  piece_ct[you]--;
  knight_ct[you]--;
  key_pieces^=random_knight[you][to];
  key_material^=random_knight_material[you][knight_ct[you]];

  key_pieces^=random_queen[me][from];
  key_pieces^=random_queen[me][to];
  queen_bb[me]&=clear_bb[from];
  queen_bb[me]|=set_bb[to];
  piece_on[to]=PIECE_QUEEN;
  color_on[to]=me;
}

B

const int WHITE=0;
const int BLACK=1;

inline void do_something(int me, int you, int move) {
  if (me == WHITE)
    do_something_tp<WHITE, BLACK>(move);
  else
    do_something_tp<BLACK, WHITE>(move);
}

template<int me, int you>
void do_something_tp(int move) {
  int from;
  int to;

  from=move_from(move);
  to=move_to(move);

  piece_on[from]=PIECE_NONE;
  piece_bb[me]&=clear_bb[from];
  piece_bb[me]|=set_bb[to];

  piece_bb[you]&=clear_bb[to];
  knight_bb[you]&=clear_bb[to];
  piece_ct[you]--;
  knight_ct[you]--;
  key_pieces^=random_knight[you][to];
  key_material^=random_knight_material[you][knight_ct[you]];

  key_pieces^=random_queen[me][from];
  key_pieces^=random_queen[me][to];
  queen_bb[me]&=clear_bb[from];
  queen_bb[me]|=set_bb[to];
  piece_on[to]=PIECE_QUEEN;
  color_on[to]=me;
}

unskilled

wie oft haben wir dir denn schon gesagt, dass du einen profiler nutzen sollst?

ich würde jetzt schon mal behaupten wollen: vernachlässigbar

und da man so und so schon nicht mehr durchsieht, ists auch von der ästhetik her egal...
so als kleiner tip: man kann auch in funktionen wieder funktionen aufrufen und auch dort kann man wieder funktionen aufrufen und - du wirst es schon ahnen - auch da könnte man wieder fkt aufrufen...

wenn ich aber so etwas sehe:

piece_on[from]=PIECE_NONE;
  piece_bb[me]&=clear_bb[from];
  piece_bb[me]|=set_bb[to];

  piece_bb[you]&=clear_bb[to];
  knight_bb[you]&=clear_bb[to];
  piece_ct[you]--;
  knight_ct[you]--;
  key_pieces^=random_knight[you][to];
  key_material^=random_knight_material[you][knight_ct[you]];

  key_pieces^=random_queen[me][from];
  key_pieces^=random_queen[me][to];
  queen_bb[me]&=clear_bb[from];
  queen_bb[me]|=set_bb[to];
  piece_on[to]=PIECE_QUEEN;
  color_on[to]=me;

hab ich nicht mal mehr lust, mir zusammenzureimen, was dort passieren soll...

bb

SeppJ

Das ist doch genau die gleiche Frage wie in deinem letzten Thread:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-253330-and-highlight-is-.html
Was bringt dich zu der Annahme, du könntest dieses Mal andere Antworten bekommen? Willst du solange fragen, bis du eine Antwort bekommst, die dir passt?

Tomahawk

@unskilled

Man kann meines Wissens erst Profilen, wenn man etwas Lauffähiges zum Profilen hat. Davon bin ich noch weit entfernt. Ausserdem lassen mit den Profilern, die ich jetzt kennengelernt habe nur Laufzeitverhalten zwischen den Funktionen eines Algorithmus messen.

@SeppJ

Meinen Compiler habe ich vor 4 Wochen installiert. Jetzt bin ich auf den Template-Mechanismus gestossen und schlage diesen, im Gegensatz zu meinen letzten Posting, hier mal als Alternative vor. So als blutiger Anfänger muss ich mich erst noch etwas im Dschungel der Möglichkeiten orientieren. C++ scheint einige interessante Optionen zu bieten.

Hätte ich etwas mehr Ahnung vom Programmieren, würde ich euch auch nicht eure kostbare Zeit mit meinen naiven Fragen stehlen...

dooooomi

Tomahawk schrieb:

Man kann meines Wissens erst Profilen, wenn man etwas Lauffähiges zum Profilen hat. Davon bin ich noch weit entfernt.

Und genau da liegt dein Problem...

Schreib doch einfach erstmal etwas, was zumindest irgendwie lauffähig ist. Achte darauf, daß dein Code sauber strukturiert und lesbar bleibt (also z.B. nicht so wie das, was du oben gepostet hast). Aber halte dich nicht mit solchen Details auf, von denen du noch nichtmal weißt, ob sie später, wenn das Programm fertig ist, überhaupt eine Rolle spielen.

Und wenn dein Programm dann irgendwann mal lauffähig ist, dann läßt du es durch einen Profiler laufen und guckst, an welchen Stellen im Code es überhaupt die meiste Zeit verbringt (gut möglich, daß das nicht die sind, die du erwarten würdest). Und genau die versuchst du dann zu optimieren, z.B. indem du mehrere Varianten implementierst, und dann wiederum mit dem Profiler guckst, welche davon am schnellsten ist.

SeppJ

Falls man mal nur wissen will, welche Programmiertechnik an sich schneller oder langsamer ist, kann man sowas auch direkt in einem kleinen Miniprogramm prüfen. Bei deinen Arrayzugriffen könnte man das zum Beispiel so machen:

(Vorsicht: Plattformabhängig, geht nur unter Linuxoiden Systemen)

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

const long int MAX_I=1000000000;

unsigned long long  get_ticks()
{
    timespec t;
    clock_gettime(CLOCK_REALTIME,&t);
    return t.tv_sec*1000000000ll+t.tv_nsec;
}

int array[2]={1,2};

long int test_d_indexed(){
  long int dummy=0;       // Das Ergebnis muss für irgendwas genutzt werden, damit es nicht wegoptimiert wird
  srand(time(NULL));
  for(long int i=0; i< MAX_I; ++i){
    int j = rand() % 2;   // Benutze Zufall, damit der Zugriff nicht optimiert werden kann
    dummy += array[j];
  }
  return dummy;
}

long int test_c_indexed(){
  long int dummy=0;
  srand(time(NULL));
  for(long int i=0; i< MAX_I; ++i){
    int j = rand() % 2;
    if (j) dummy += array[0];
    else dummy += array[1];
  }
  return dummy;
}

template<int i> inline int t_array(){
  return array[i];
}

long int test_t_indexed(){
  long int dummy=0;
  srand(time(NULL));
  for(long int i=0; i< MAX_I; ++i){
    int j = rand() % 2;
    if (j) dummy += t_array<0>();
    else dummy += t_array<1>();
  }
  return dummy;
}

int main(){
  unsigned long long before, after;
  long int dummy1,dummy2,dummy3;
  before = get_ticks();
  dummy1=test_d_indexed();
  after = get_ticks();
  cout << "Runtime indexed: " << after-before << endl;

  before = get_ticks();
  dummy2=test_c_indexed();
  after = get_ticks();
  cout << "Compiletime statically indexed: " << after-before << endl;

  before = get_ticks();
  dummy3=test_t_indexed();
  after = get_ticks();
  cout << "Compiletime template indexed: " << after-before << endl;

  cout << endl << (dummy1+dummy2+dummy3) % 1<<endl; // Benutze die Ergebnisse um eine 0 zu berechnen, damit nicht der ganze Code wegoptimiert wird.
}

Ich habe das Programm einmal mit GNU Compiler und einmal mit intel Compiler auf jeweils höchster Optimierungsstufe übersetzt und jeweils ca. 10 mal mit maximaler Prozesspriorität ausgeführt. Dabei konnte ich keine großen Unterschiede feststellen. Die Tendenz schien jedoch zu sein, dass die erste Methode ein wenig (~5%) langsamer ist und die zweite und dritte Methode genau gleich schnell. Der Intel Compiler scheint auch ein kleines bisschen schnelleren (~5%) Code erzeugt zu haben (möglicherweise andere Zufallsgeneratorimplementierung). Die meisten Testläufe erzeugten konsistente Ergebnisse, manchmal gab es jedoch auch Ausreißer, die dann gerne mal 20-50% langsamer waren, ohne ersichtlichen Grund (vielleicht ein anderer Prozess mit sehr hoher Priorität der dazwischen gefunkt hat).

Man beachte, dass hier der Anteil der Arrayzugriffe am Gesamtcode extrem hoch ist. Es passiert sonst fast gar nichts anderes im Programm. Trotzdem ist der Unterschied zwischen den drei Methoden sehr gering.

Tomahawk

Danke für das Experiment!

Das Ergebnis wäre rein qualitativ zu erwarten gewesen, da vermutlich Experiment 2 und 3 vom Compiler in sehr ähnlichen Maschinencode übersetzt worden sind. Nur dass es sich quantitativ im Bereich von ~5% gegenüber Experiment 3 bewegt, ist erstaunlich wenig.

Wenn keine weiteren Bugs in meinem neuen Code sind, dann könnte die Chesscore bereits in 1-2 Tagen lauffähig sein und ich kann ähnliche Experimente (Brute-Force Rekursionen) zur Bestimmung des Laufzeitverhaltens machen.

Gute Nacht!

SeppJ

Tomahawk schrieb:

Danke für das Experiment!

Das Ergebnis wäre rein qualitativ zu erwarten gewesen, da vermutlich Experiment 2 und 3 vom Compiler in sehr ähnlichen Maschinencode übersetzt worden sind. Nur dass es sich quantitativ im Bereich von ~5% bewegt gegenüber Experiment 3 bewegt, ist erstaunlich wenig.

Und ich war erstaunt, dass Methode 1 langsamer war. Ich hätte nämlich Geld darauf gesetzt, dass es deutlich schneller ist, denn if-Abfragen sind in der Regel recht teuer.

edit: Ich würde sogar behaupten, dass 2 und 3 identischen Maschinencode haben dürften, aber ich kann nicht so gut Assembler um die Compilerausgabe auf dem Optimierungsniveau zu durchschauen.