Discussion :

[Roland Chastain]

J'ai fait un programme qui compare les performances de trois fonctions : la fonction actuellement utilisée dans le code de mon moteur d'échecs, une autre que j'ai écrite et une autre basée sur la fonction BitCount en Assembleur.

Code Delphi :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
{$asmMode intel}
 
uses
  SysUtils, Damier, Tables;
 
type
  TFonction = function(const ADamier: TDamier): integer;
 
function CompteCasesAllumees2(const ADamier: TDamier): integer;
const
  CZero = TDamier(0);
  CUn   = TDamier(1);
var
  LDamier: TDamier;
begin
  result := 0;
  LDamier := ADamier;
  while LDamier <> CZero do
  begin
    if LDamier and CUn = CUn then
      Inc(result);
    LDamier := LDamier shr 1;
  end;
end;
 
function BitCount(var n : Int64): byte; assembler; nostackframe; inline; // Testé en 32 et 64 bits
asm
   popcnt edx,   dword ptr [n]        // 32 bits eax = @n,  en 64 bits rcx = @n 
   popcnt eax,   dword ptr [n+4]   
   add    eax,    edx                   
end;
 
function CompteCasesAllumees3(const ADamier: TDamier): integer;
var
  LDamier: TDamier;
begin
  LDamier := ADamier;
  result := BitCount(LDamier);
end;
 
procedure Test(ADamier: TDamier; AFonction: TFonction);
var
  i, res: integer;
  t: cardinal;
begin
  t := GetTickCount64;
  for i := 1 to 1000000 do
    res := AFonction(ADamier);
  WriteLn(GetTickCount64 - t);
end;
 
const
  CCavaliers = %0100001000000000000000000000000000000000000000000000000001000010;
 
begin
  Test(CCavaliers, @CompteCasesAllumees);
  Test(CCavaliers, @CompteCasesAllumees2);
  Test(CCavaliers, @CompteCasesAllumees3);
end.

La différence est si énorme que je me demande si je ne me suis pas trompé quelque part !

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
2344
969
31

Le test a été fait avec FPC 32 bits. Ci-joint le code source complet.

[Roland Chastain]

La fonction non compatible 32 bits va encore plus vite !

[Roland Chastain]

Pour revenir à la fonction BitScanForward en Assembleur, j'ai appliqué la correction que vous avez proposée. Ça ne donne pas les bons résultats, avec aucun compilateur.

Comme vous sembliez dire que la fonction originale n'était pas très bien écrite, comment l'écririez-vous ?

[Guesset]

Bonjour Roland,

Une manière simple de se faire une idée est de regarder en mode debug la fenêtre assembleur et de compter les lignes assembleurs dans les divers cas. Ça donne une bonne idée du rapport de performances (c'est un peu au doigts mouillé mais le ratio est souvent très proche de la réalité - avant division on ajoute aux deux 2x(le nombre d'argument +1) pour tenir compte du chargement des arguments et de l'appel de fonction).

Pour le comptage de bits à 1, le ratio entre la solution pascal (optimisée par masquages qui est environ 2x plus rapide que par décalages) et asm est de l'ordre de 20x (près du double en asm 64 bits). Mais nous parlons de temps qui sont de l'ordre de 50 à 150 ns dans le cas le plus défavorable. Il faut donc qu'il y ait un grand nombre d’occurrences pour que la différence soit humainement perceptible.

Ci-dessous les versions (testées) en pascal utilisant les masquages :

Code Delphi :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
function BitCount(X: Int64): Byte;
begin
   X := (X and $5555555555555555) + ((X shr  1) and $5555555555555555);
   X := (X and $3333333333333333) + ((X shr  2) and $3333333333333333);
   X := (X and $0F0F0F0F0F0F0F0F) + ((X shr  4) and $0F0F0F0F0F0F0F0F);
   X := (X and $00FF00FF00FF00FF) + ((X shr  8) and $00FF00FF00FF00FF);
   X := (X and $0000FFFF0000FFFF) + ((X shr 16) and $0000FFFF0000FFFF);
   X := (X and $00000000FFFFFFFF) + ((X shr 32) and $00000000FFFFFFFF);
  result := Byte(X);
end;
 
function BitScanForward(X : Int64): Integer;
var Y : int64;
begin
   if X = 0 then Exit(-1);
   Result := 0;
   Y := X and $00000000FFFFFFFF; if Y = 0 then Result += 32 else X := Y;
   Y := X and $0000FFFF0000FFFF; if Y = 0 then Result += 16 else X := Y;
   Y := X and $00FF00FF00FF00FF; if Y = 0 then Result +=  8 else X := Y;
   Y := X and $0F0F0F0F0F0F0F0F; if Y = 0 then Result +=  4 else X := Y;
   Y := X and $3333333333333333; if Y = 0 then Result +=  2 else X := Y;
   if X and $5555555555555555 = 0 then Result +=  1;
end;
 
function BitScanReverse(X: Int64): Integer;
var Y : int64;
begin
   if X = 0 then Exit(-1);
   Result := 63;
   Y := X and $FFFFFFFF00000000; if Y = 0 then Result -= 32 else X := Y;
   Y := X and $FFFF0000FFFF0000; if Y = 0 then Result -= 16 else X := Y;
   Y := X and $FF00FF00FF00FF00; if Y = 0 then Result -=  8 else X := Y;
   Y := X and $F0F0F0F0F0F0F0F0; if Y = 0 then Result -=  4 else X := Y;
   Y := X and $CCCCCCCCCCCCCCCC; if Y = 0 then Result -=  2 else X := Y;
   if   X and $AAAAAAAAAAAAAAAA = 0 then Result -= 1;
end;

Dans le code mis à disposition, il y a des fonctions identiques FirstOne/BitScanForward et LastOne/BitScanReverse. C'est normal ?

Salutations

[Roland Chastain]

Merci beaucoup pour les explications et pour le code. J'ai hâte de l'essayer.

Cependant dans mon message précédent, je parlais de la fonction BitScanForward en Assembleur. Je me demandais comment vous l'écririez en Assembleur, sur le modèle de la fonction BitCount que vous avez proposée (qui marche "du tonnerre" et qui est acceptée par tous les compilateurs, contrairement à la version originale).

Dans le code mis à disposition, il y a des fonctions identiques FirstOne/BitScanForward et LastOne/BitScanReverse. C'est normal ?

Les fonctions FirstOne et LastOne ne sont pas utilisées dans le programme. Je n'avais pas remarqué qu'elles étaient identiques à BitScanForward et BitScanReverse. Je ne sais pas pourquoi l'auteur du programme les a laissées dans le code.

Bon, je marque la discussion comme résolue, puisque j'ai eu ce dont j'avais besoin et même plus. Je reviendrai quand même donner les résultats de mes essais pour les nouvelles fonctions en Pascal.

[Roland Chastain]

Voici les résultats :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Pascal     Roland 1      : 1985 ms
Pascal     Roland 2      :  641 ms
Pascal     Guesset       :   62 ms
Assembleur Guesset 32/64 :   47 ms
Assembleur Guesset 64    :   16 ms

Votre fonction en Pascal est juste dix fois plus rapide que la mienne.

Et presque aussi rapide que les fonctions en Assembleur.

Je vais l'adopter, même si je ne comprends pas trop (pas du tout, en fait) comment elle fonctionne.

Merci !

[Guesset]

Bonjour Roland,

J'espère que nous pourrons bénéficier de ton travail de mise à niveau de cette application (au moins en voir l'exécutable).

Les technique de masquage sont classiques même si elles ne sont pas très faciles à lire. Le principe est d'utiliser des masques pour paralléliser des fragment d'opération (bit, duo, quartet, octet, et plus si affinités).

Bonne continuation.

[Roland Chastain]

J'espère que nous pourrons bénéficier de ton travail de mise à niveau de cette application (au moins en voir l'exécutable).

Avec plaisir. Cependant j'ai eu la désagréable surprise de constater que l'application est boguée. L'ordinateur joue des coups illégaux, annonce des mats qui n'existent pas... Alors je pourrais chercher les bogues mais je ne suis pas sûr d'en venir à bout, étant donné que le code est plein d'opérations binaires obscures pour moi. Je vais quand même essayer d'y jeter un œil et éventuellement j'ouvrirai une discussion dans le forum Pascal ou Delphi. En attendant vous pouvez trouver l'application originale là. Tiens, en relisant la discussion de 2015, je m'aperçois que le bogue avait déjà été signalé...

Quoi qu'il en soit les fonctions que vous avez proposées ne seront pas perdues. Je pense les intégrer dans la prochaine version de mon propre programme, qui est lui aussi basé sur les bitboards.

[Roland Chastain]

Bonjour ! J'ai retravaillé sur ce projet (la version Free Pascal du programme d'échecs Deep Ross). Du coup j'ai relu cette discussion et ai refait un essai de toutes les fonctions permettant de compter les bits. Bizarrement la fonction BitCount 64 bits me renvoie des résultats faux, alors que dans mon souvenir elle fonctionnait correctement.

J'ai fait un petit programme permettant d'essayer les différentes fonctions (y compris une que je viens de trouver sur le forum anglais, et y compris aussi la fonction PopCnt de Free Pascal, dont je viens de découvrir l'existence).

Code Delphi :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
{$asmMode intel}
 
uses
  SysUtils;
 
(* https://www.developpez.net/forums/d2001819-2/autres-langages/assembleur/x86-32-bits-64-bits/reecriture-pascal-d-fonction-assembleur/#post11124482 *)
function BitCount1(X: Int64): integer;
begin
   X := (X and $5555555555555555) + ((X shr  1) and $5555555555555555);
   X := (X and $3333333333333333) + ((X shr  2) and $3333333333333333);
   X := (X and $0F0F0F0F0F0F0F0F) + ((X shr  4) and $0F0F0F0F0F0F0F0F);
   X := (X and $00FF00FF00FF00FF) + ((X shr  8) and $00FF00FF00FF00FF);
   X := (X and $0000FFFF0000FFFF) + ((X shr 16) and $0000FFFF0000FFFF);
   X := (X and $00000000FFFFFFFF) + ((X shr 32) and $00000000FFFFFFFF);
  result := integer(X);
end;
 
(* https://www.developpez.net/forums/d2001819/autres-langages/assembleur/x86-32-bits-64-bits/reecriture-pascal-d-fonction-assembleur/#post11120985 *)
function BitCount2(X: Int64): Int64; assembler; nostackframe; inline;
asm
  popcnt rax, rcx
end;
 
(* https://www.developpez.net/forums/d2001819/autres-langages/assembleur/x86-32-bits-64-bits/reecriture-pascal-d-fonction-assembleur/#post11122922 *)
function BitCount3(var X: Int64): integer; assembler; nostackframe; inline;
asm
  popcnt edx, dword ptr [X]  
  popcnt eax, dword ptr [X+4]   
  add    eax, edx                   
end;
 
(* https://forum.lazarus.freepascal.org/index.php/topic,45840.msg324823.html#msg324823 *)
function BitCount4(const X: Int64): Int64; assembler; nostackframe; inline;
asm
  popcnt @result, X
end;
 
var
  LPiecesBlanches: Int64 = 65535; //%0000000000000000000000000000000000000000000000001111111111111111;
  LCavaliers: Int64 = 4755801206503243842; //%0100001000000000000000000000000000000000000000000000000001000010;
 
begin
  WriteLn('BitCount1');
  WriteLn(BitCount1(LPiecesBlanches));
  WriteLn(BitCount1(LCavaliers));
  WriteLn('BitCount2');
  WriteLn(BitCount2(LPiecesBlanches));
  WriteLn(BitCount2(LCavaliers));
  WriteLn('BitCount3');
  WriteLn(BitCount3(LPiecesBlanches));
  WriteLn(BitCount3(LCavaliers));
  WriteLn('BitCount4');
  WriteLn(BitCount4(LPiecesBlanches));
  WriteLn(BitCount4(LCavaliers));
  WriteLn('PopCnt');
  WriteLn(PopCnt(QWord(LPiecesBlanches)));
  WriteLn(PopCnt(QWord(LCavaliers)));
end.

Chez moi cela donne ceci :

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[roland@localhost engine]$ ./test
BitCount1
16
4
BitCount2
8
8
BitCount3
16
4
BitCount4
16
4
PopCnt
16
4

Le résultat de la fonction BitCount2 est faux. En fait il change même d'une fois sur l'autre !

[Guesset]

Bonjour Roland,

Toutes les écritures me paraissent bonnes. La 4 doit être traduite de la même manière que la 2 (passer en mode debug et regarder l'assembleur généré). J'utilise la 2 sans problème.

Ce type d'erreur laisse penser que X n'atterrit pas dans rcx. La première idée serait que cela a été compilé en 32 bits qui ne passe pas les arguments dans les mêmes registres (eax, edx, ecx au lieu de rcx, rdx, r8) mais je trouve étrange que le compilateur ne fasse pas la tête quand il trouve du code assembleur 64 bit (peut être qu'il s'en moque parce que ce n'est pas lui qui l'a généré).

Tiens moi au courant.

Bonne soirée.

[Roland Chastain]

Bonjour Phlippe !

Merci pour ta réponse, que je viens seulement de voir.

Je compile bien en 64 bits (enfin, je crois bien).

Free Pascal Compiler version 3.0.4 [2017/10/02] for x86_64

[roland@localhost experiment]$ file bitcountcomp
bitcountcomp: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, BuildID[sha1]=cff98aa2a9aea97f581ea54fb3351eddcf9262dc, for GNU/Linux 2.4.0, with debug_info, not stripped
[roland@localhost experiment]$

J'ai suivi ton conseil de regarder l'assembleur généré. Voici ce que ça donne pour la 2 :

Code Asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.section .text.n_p$program_$$_bitcount2$int64$$int64
	.balign 16,0x90
.globl	P$PROGRAM_$$_BITCOUNT2$INT64$$INT64
	.type	P$PROGRAM_$$_BITCOUNT2$INT64$$INT64,@function
P$PROGRAM_$$_BITCOUNT2$INT64$$INT64:
.Lc6:
# Var X located in register rdi
# Var $result located in register rax
# [21] asm
# [22] popcnt rax, rcx
	popcntq	%rcx,%rax
# [23] end;
	ret
.Lc7:
.Le1:
	.size	P$PROGRAM_$$_BITCOUNT2$INT64$$INT64, .Le1 - P$PROGRAM_$$_BITCOUNT2$INT64$$INT64

Pour comparaison, la 4 :

Code Asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.section .text.n_p$program_$$_bitcount4$int64$$int64
	.balign 16,0x90
.globl	P$PROGRAM_$$_BITCOUNT4$INT64$$INT64
	.type	P$PROGRAM_$$_BITCOUNT4$INT64$$INT64,@function
P$PROGRAM_$$_BITCOUNT4$INT64$$INT64:
.Lc10:
# Var X located in register rdi
# Var $result located in register rax
# [35] asm
# [36] popcnt @result, X
	popcntq	%rdi,%rax
# [37] end;
	ret
.Lc11:
.Le3:
	.size	P$PROGRAM_$$_BITCOUNT4$INT64$$INT64, .Le3 - P$PROGRAM_$$_BITCOUNT4$INT64$$INT64

Donc je vois qu'il y a une différence. Mais ma compréhension des choses ne va pas plus loin.

Salutations.

Roland

[Guesset]

Bonsoir Roland,

La valeur atterrit dans rdi au lieu de rcx. Remplacer rcx par rdi résoudra le problème mais on se ramènera simplement au cas 4 qui a des noms de variables au lieu des registres nommés.

En général je n'utilise pas les noms de variables en assembleur en nostackframe (c'est à dire qui passe les variables par les registres) car, même si c'est pratique, cela masque les registres utilisés et, par exemple, on peut se retrouver avec des instructions qui écrasent des variables sans le voir.

Ceci étant, je ne comprends pas pourquoi la convention d'appel est modifiée et passe dans rdi le premier argument. Peut être la cible Linus induit cette modification ? Comme je n'utilise pas cet OS (ou très marginalement sur Raspberry) je ne saurai l’affirmer.

Bonne soirée
Philippe

[chrtophe]

Voici les registres à utiliser en 64 bits pour les paramètres : rdi, rsi, rdx, rcx, r8, r9, rax devant contenir le numéro de fonction appelé. attention les numéros de fonctions ne sont pas les mêmes qu'en i386 et l'ABI 64 bits utilise SYSCALL au lieu d'int 0x80. Linux se cale sur l'ABI SYSTEM V, tout comme le format ELF.

[Guesset]

Merci chrtophe,

Voici les registres à utiliser en 64 bits pour les paramètres : rdi, rsi, rdx, rcx, r8, r9, rax devant contenir le numéro de fonction appelé. attention les numéros de fonctions ne sont pas les mêmes qu'en i386 et l'ABI 64 bits utilise SYSCALL au lieu d'int 0x80. Linux se cale sur l'ABI SYSTEM V, tout comme le format ELF.

Sous Windows la convention d'appel par registre est appelée fastcall et utilise dans l'ordre RCX, RDX, R8 et R9 (Xmm0 à Xmm3 pour les arguments à virgule flottante). Linux semble un peu plus libéral

Salutations