Optimisation d'un programme d'échecs

Version imprimable

Bonjour !

J'ai ecrit un tres fort programme d'echecs en C (2600+ ELO)
Telechargeable a http://perso.wanadoo.fr/eric.triki

Mais la fonction suivante, bien que minuscule, consomme 10% de mon temps d'execution !
Y a-t-il aucun espoir de faire une fonction XorSlidingPiece() plus rapide ?!

Tout code plus rapide (en assembleur) serait le bienvenu ...
Utilisez des instructions MMX ou tout ce que vous voudrez d'autre et montrez moi que mon code actuel est tres sous-optimal !

Merci d'avance ...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
// Pieces :
#define BISHOP    1  // Fou 
#define ROOK      2   // Tour
#define QUEEN     3  // Dame
#define OUT       8   // case "au dehors" de l'echiquier
 
enum {
      NORTH=1, SOUTH=-1,
      EAST=10, WEST=-10,
      SE=9   , NW=-9,
      NE=11  , SW=-11
     };
 
// Echiquier :
signed char board[120]={
     OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,
     OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,
     OUT,      0,      0,      0,      0,      0,      0,      0,      0,    OUT,
     OUT,      0,      0,      0,      0,      0,      0,      0,      0,    OUT,
     OUT,      0,   ROOK,      0,      0,      0,      0,      0,      0,    OUT,
     OUT,      0,      0,      0,  QUEEN,      0,      0,      0,      0,    OUT,
     OUT,      0,      0,      0,      0,      0,      0,      0,      0,    OUT,
     OUT,      0,      0,      0,      0,      0,      0,      0,      0,    OUT,
     OUT,      0,      0,      0,      0,      0,-BISHOP,      0,      0,    OUT,
     OUT,      0,      0,      0,      0,      0,      0,      0,      0,    OUT,
     OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,
     OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,    OUT,
    };
 
 
#define XorTour(square,tab,bit,i) \
i=square+NORTH ; while( !board[i] ) { tab[i]^=bit; i+=NORTH; } tab[i]^=bit; \
i=square+SOUTH ; while( !board[i] ) { tab[i]^=bit; i+=SOUTH; } tab[i]^=bit; \
i=square+EAST  ; while( !board[i] ) { tab[i]^=bit; i+=EAST;  } tab[i]^=bit; \
i=square+WEST  ; while( !board[i] ) { tab[i]^=bit; i+=WEST;  } tab[i]^=bit;
 
#define XorFou(square,tab,bit,i) \
i=square+NO    ; while( !board[i] ) { tab[i]^=bit; i+=NO;   } tab[i]^=bit; \
i=square+NE    ; while( !board[i] ) { tab[i]^=bit; i+=NE;   } tab[i]^=bit; \
i=square+SO    ; while( !board[i] ) { tab[i]^=bit; i+=SO;   } tab[i]^=bit; \
i=square+SE    ; while( !board[i] ) { tab[i]^=bit; i+=SE;   } tab[i]^=bit;
 
// mark/unmark all the squares that are attacked by "piece"
// piece : BISHOP or ROOK or QUEEN
// square : square of the piece
// tab : unsigned[120] , ( tab[x] & bit ) != 0 <=> square x is attacked by piece
// bit : in { 1, 2, 4, ..., 2^15 } , bit corresponding to the piece that is being moved
void XorSlidingPiece(const unsigned piece,const int square,unsigned * const tab,const unsigned bit)
{
int i;
 
if( piece ^ BISHOP  )  // not a BISHOP   => QUEEN || ROOK
   {
    XorTour(square,tab,bit,i);
   }
 
if( piece ^ ROOK )  // not a ROOK => QUEEN || BISHOP
   {
    XorFou(square,tab,bit,i);
   }
}
 
// Inline versions : not faster
#define XorTour(sq,tab,bit,i) \
tab[sq+NORTH]^=bit; if( !board[sq+NORTH] ) { tab[sq+2*NORTH]^=bit; if( !board[sq+2*NORTH] ) { tab[sq+3*NORTH]^=bit; if( !board[sq+3*NORTH] ) { tab[sq+4*NORTH]^=bit; if( !board[sq+4*NORTH] ) { tab[sq+5*NORTH]^=bit; if( !board[sq+5*NORTH] ) { tab[sq+6*NORTH]^=bit; if( !board[sq+6*NORTH] ) tab[sq+7*NORTH]^=bit; } } } } } \
tab[sq+SOUTH]^=bit; if( !board[sq+SOUTH] ) { tab[sq+2*SOUTH]^=bit; if( !board[sq+2*SOUTH] ) { tab[sq+3*SOUTH]^=bit; if( !board[sq+3*SOUTH] ) { tab[sq+4*SOUTH]^=bit; if( !board[sq+4*SOUTH] ) { tab[sq+5*SOUTH]^=bit; if( !board[sq+5*SOUTH] ) { tab[sq+6*SOUTH]^=bit; if( !board[sq+6*SOUTH] ) tab[sq+7*SOUTH]^=bit; } } } } } \
tab[sq+EAST ]^=bit; if( !board[sq+EAST ] ) { tab[sq+2*EAST ]^=bit; if( !board[sq+2*EAST ] ) { tab[sq+3*EAST ]^=bit; if( !board[sq+3*EAST ] ) { tab[sq+4*EAST ]^=bit; if( !board[sq+4*EAST ] ) { tab[sq+5*EAST ]^=bit; if( !board[sq+5*EAST ] ) { tab[sq+6*EAST ]^=bit; if( !board[sq+6*EAST ] ) tab[sq+7*EAST ]^=bit; } } } } } \
tab[sq+OUEST]^=bit; if( !board[sq+OUEST] ) { tab[sq+2*OUEST]^=bit; if( !board[sq+2*OUEST] ) { tab[sq+3*OUEST]^=bit; if( !board[sq+3*OUEST] ) { tab[sq+4*OUEST]^=bit; if( !board[sq+4*OUEST] ) { tab[sq+5*OUEST]^=bit; if( !board[sq+5*OUEST] ) { tab[sq+6*OUEST]^=bit; if( !board[sq+6*OUEST] ) tab[sq+7*OUEST]^=bit; } } } } }
 
#define XorFou(sq,tab,bit,i) \
tab[sq+NW]^=bit; if( !board[sq+NW] ) { tab[sq+2*NW]^=bit; if( !board[sq+2*NW] ) { tab[sq+3*NW]^=bit; if( !board[sq+3*NW] ) { tab[sq+4*NW]^=bit; if( !board[sq+4*NW] ) { tab[sq+5*NW]^=bit; if( !board[sq+5*NW] ) { tab[sq+6*NW]^=bit; if( !board[sq+6*NW] ) tab[sq+7*NW]^=bit; } } } } } \
tab[sq+NE]^=bit; if( !board[sq+NE] ) { tab[sq+2*NE]^=bit; if( !board[sq+2*NE] ) { tab[sq+3*NE]^=bit; if( !board[sq+3*NE] ) { tab[sq+4*NE]^=bit; if( !board[sq+4*NE] ) { tab[sq+5*NE]^=bit; if( !board[sq+5*NE] ) { tab[sq+6*NE]^=bit; if( !board[sq+6*NE] ) tab[sq+7*NE]^=bit; } } } } } \
tab[sq+SW]^=bit; if( !board[sq+SW] ) { tab[sq+2*SW]^=bit; if( !board[sq+2*SW] ) { tab[sq+3*SW]^=bit; if( !board[sq+3*SW] ) { tab[sq+4*SW]^=bit; if( !board[sq+4*SW] ) { tab[sq+5*SW]^=bit; if( !board[sq+5*SW] ) { tab[sq+6*SW]^=bit; if( !board[sq+6*SW] ) tab[sq+7*SW]^=bit; } } } } } \
tab[sq+SE]^=bit; if( !board[sq+SE] ) { tab[sq+2*SE]^=bit; if( !board[sq+2*SE] ) { tab[sq+3*SE]^=bit; if( !board[sq+3*SE] ) { tab[sq+4*SE]^=bit; if( !board[sq+4*SE] ) { tab[sq+5*SE]^=bit; if( !board[sq+5*SE] ) { tab[sq+6*SE]^=bit; if( !board[sq+6*SE] ) tab[sq+7*SE]^=bit; } } } } }

21/11/2005, 20h52
pascal_damien

Bonjour,

Ca n'a pas un grand rapport avec de l'optimisation, mais j'ai l'impression que SO et NO ne sont pas définis.
22/11/2005, 00h43
Smortex

Bonjour

Tu as déroulé les boucles pour gagner en performances ? Dérouler des if ne te fera pas gagner en performances puisque pour le processeur le problème reste entier : faut'il exécuter les instructions suivantes...

A titre indicatif, il y à plusieurs étapes pour optimiser un code, le dernier recours étant le passage à un langage de plus bas niveau... Est-tu sûr de ne pas les brûler ?
22/11/2005, 18h23
Erickann

Je ne suis pas avancé

Réponse à : pascal_damien

Oui c'est pas NO et SO qu'il faut lire mais NW et SW ... :?

Réponse à : Smortex

Oui j'ai déroulé les boucles, et si c'est sensé ne rien changer pourquoi le code enroulé tourne plus vite sur Pentium 4 que le code déroulé et vice verca sur Athlon ?
[pour couper cours à toute discussion sur cette tentative de inlining : évidemment la différence est faible]

Ta question condescendante m'atriste ... :(
J'ai pourtant indiqué sur mon premier post que cette fonction consomme 10% de mon temps d'éxécution, je pourais donc parfaitement me passer de l'optimiser, même si je gagnais 50% sur 10% ca ne changerait pas grand chose.
Si tu ne vois pas comment réécrire cette fonction (en assembleur ou en C) pour qu'elle tourne plus vite que ce que me pond Visual C++ 6, il suffit de le dire !
22/11/2005, 21h18
Smortex

Re: Je ne suis pas avancé
Citation:

Envoyé par Erickann

Oui j'ai déroulé les boucles, et si c'est sensé ne rien changer pourquoi le code enroulé tourne plus vite sur Pentium 4 que le code déroulé et vice verca sur Athlon ?

Parceque ton compilateur est mal configure peut etre ? Tu utilise lequel ? Tu lui passe des options specifiques ? Il n'a pas une option pour derouler les boucles a ta place (-funroll-loops pour gcc) ?

Citation:

Envoyé par Erickann

[pour couper cours à toute discussion sur cette tentative de inlining : évidemment la différence est faible]

Wiwi ! C'est marque dans les commentaires :)

Citation:

Envoyé par Erickann

J'ai pourtant indiqué sur mon premier post que cette fonction consomme 10% de mon temps d'éxécution

Oui, mais 10% par rapport a quoi ?

Citation:

Envoyé par Erickann

Si tu ne vois pas comment réécrire cette fonction (en assembleur ou en C) pour qu'elle tourne plus vite que ce que me pond Visual C++ 6, il suffit de le dire !

Comme je te le dit, le probleme est que l'algorithme impose des tests a chaque etape, il n'y a pas de "bloc" de code a executer inconditionellement de maniere a profiter de l'effet pipeline. L'ideal serait de trouver une autre algorithme qui fasse la meme chose avec une complexite moindre... Mais cela risque d'avoir pour consequence la modification des structures de donnes ce qui peut ne pas etre acceptable.

En d'autres termes, la meilleur maniere d'optimiser le code n'est pas applicable sur les structures de donnees actuelle, place donc au second "attout", le compilateur. Ce qu'il peut faire c'est d'organiser le code de maniere a generer un code plus rapide a executer (domaine dans lequel le compilateur est generalement bien meilleur que l'homme, car il n'oublie rien). Si tu utilise un compilateur tel que icc, tu aura droit a des optimisation qui empechent meme tout reverse engineering (Y sont doues chez intel pour faire des compilateurs... ) C'est cette methode que tu devrais adopter si tu n'est pas pret a modifier le fonctionnement de ton programme...

Si les resultats ne sont toujours pas satisfesants, alors, ok, tu peux passer le code en assembleur... Avec tous les inconvenients qui vont avec (le principal pouvant etre que le code n'est plus portable). A prioris la traduction directe en assembleur ne devrait pas diminuer dramqtiquement le temps d'execution des fonctions (voir meme etre plus long... mais impossible de le certifier puisque ca depends de comment le compilateur C compile le code C), mais ca se tente...
Code:

1 2 3 4 5 6 7 mov esi, ... mov eax,[esi] xor eax, bits mov [esi],eax bnz fin add esi, ... ; etc pour une version deroullee, ou un saut pour une version non deroullee
22/11/2005, 21h26
2PluS4

Il est étonnant que ce soit CE code qui consomme 10% de ton temps d'execution: ce n'est pas un mangeur de cycle... J'imagine que tu dois appeller la fonction XorSlidingPiece assez souvent...

Pour gagner des cycles, ne cherche pas à optimiser plus ton code, tu ne pourras, en effet, faire grand chose (et surtout pas en utilisant des instructions MMX, SSE, ou autres, qui ne serviraient pas du tout ici).
Il faut mieux chercher à appeller le moins possible ta fonction. :wink:

Citation:

Oui j'ai déroulé les boucles, et si c'est sensé ne rien changer pourquoi le code enroulé tourne plus vite sur Pentium 4 que le code déroulé et vice verca sur Athlon ?

Parce que il est bcp plus lent d'executer :

Code:

tab[sq+5*NORTH]^=bit;

que d'executer une suite de

Code:

tab[i]^=bit; i+=NORTH;

Le compilateur C va compiler ton code sans en optimiser les algorithmes (car mal configuré :P) et va effectuer une série de multiplications ( l'instruction "mul" mange plus de 11 CYCLES !!! ce qui est gigantesque), au lieu de faire des addictions et xor successifs (prennant bcp moins de cycle, ie dans les 4/5/6 cycles au total).
Tu peux supprimer le code avec les boucles déroulées, il sera toujours plus lent que le code avec les boucles, avec un compilateur qui ne sait pas optimiser
:wink:
22/11/2005, 23h10
Erickann

Details techniques

J'utilise Visual C++ 6

Options de compilations :

General : "Optimizations" : "Maximize speed"

Tout le reste c'est les options par defaut.

Par exemple dans "Code Generation" j'ai essaye differentes alternatives qui se sont toute averees produire un code moins rapide.
Dans "Optimizations" j'ai essaye "customize" mais idem : pas moyen d'obtenir un code plus rapide (du moins avec mes essais).

Je compile aussi sous Linux avec gcc -O3, j'obtiens un code tres legerement plus lent (~1%).

Quand je dis 10% de mon temps d'execution, ca veut dire qu'en moyenne, quand je fais reflechir mon programme sur une position et qu'il joue son coup apres 100 s, il a passe 10 s a executer des XorSlidingPiece() ...

Un programme d'echec "reflechit" en parcourant un arbre de recherche.
A chaque fois que E.T. essaye un coup de dame (ou de tour ou de fou) il appelle XorSlidingPiece 2 fois : une fois pour effacer la "trajectoire" de la piece depuis sa case de depart, une fois pour ecrire la "trajectoire" depuis la case d'arrivee.
De plus, quand il redescend dans l'arbre il doit encore faire 2 appels pour "annuler" le coup essaye.

Je ne vois donc aucun moyen de diminuer les appels a cette fonction (sauf en ne jouant que des pions :D).

Pour ce qui est des structure de donnees, elles ont ete fixees avant l'ecriture du prog (qui est enorme).
De plus 2 tableaux :
signed char board[120] pour contenir la position des pieces
unsigned tab[120] pour contenir la "trajectoire" des pieces
je vois pas comment je pourais faire plus simple.

Enfin, j'ai constate que la modification d'une ligne anodine dans mon prog suffisait a changer le temps d'execution apres re-compilation. La seule raison que je vois est l'alignement des donnees que cela a pu changer, mais je ne comprends pas puisque Visual C++ est cense aligner par 8 octets par defaut. :o

Enfin un truc du meme genre : quand je declare "const" des tableaux cela change parfois le temps d'execution en pire, bizarre (je donne plus d'infos au compilo et il me pond du plus lent) ?! :o

PS :
Le code deroule tourne vraiment plus vite que le code enroule sur Pentium 4
Le code enroule tourne vraiment plus vite que le code deroule sur Athlon
(ou c'est l'inverse, mais bon, y a pas un des deux qui tourne toujours plus vite que l'autre) Donc Visual C++ optimise quand meme un peu ...
23/11/2005, 19h56
2PluS4

VC++ n'est pas connu pour ses capacités d'optimisation ^^
C'est même étonnant que ce soit plus lent avec gcc...
Tu pourrais essayer icc, le compilateur d'intel, qui est de loin le plus rapide (mais payant je crois :-/)

Sinon, je ne pense pas que tu gagne beaucoup de cycles en reprogrammant cela toi même en asm... :roll:
23/11/2005, 20h23
Smortex

Citation:

Envoyé par 2PluS4

Tu pourrais essayer icc, le compilateur d'intel, qui est de loin le plus rapide (mais payant je crois :-/)

C'est gratuit pour les particuliers :)