Discussion :

[Erickann]

J'ai écrit un programme de Sudoku en C

Celui-ci utilise intensivement les deux macros suivantes :

Code :

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

1
2
3
4
 
// x est un unsigned dont seuls les 16 premiers bits peuvent etre a 1
#define Count_bit(x) (count_bit[x])  // nb de bits a 1 ds x 
#define First_bit(x) (first_bit[x])  // numero du premier bit a 1 ds x

Deux tableaux de 2^16=65536 unsigned char sont precalcules et me permettent d'obtenir les valeurs voulues :

Code :

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

1
2
unsigned char count_bit[65536]
unsigned char first_bit[65536]

Le pb est que la consultation de ces tables est couteux en temps d'execution !
Je sais qu'il existe une instruction x86 pour l'index du premier bit a 1 : bsf ...
Mais je ne m'y connais pas assez en assembleur.

J'aurai besoin du code assembleur pour ces 2 fonctions (dans le but de le copier-coller dans mon prog (sous Visual C++ 6)) ...

Merci d'avance ...

[Neitsa]

Bonjour,

voilà ce que j'ai pondu

Code :

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
 
#include <iostream>
 
unsigned int GetFirstBitAt1 (unsigned int x);
unsigned int CountBitAt1 (unsigned int x);
 
#define Count_bit(x) (CountBitAt1 (count_bit[x]))  // nb de bits a 1 ds x 
#define First_bit(x) (GetFirstBitAt1 (first_bit[x]))  // numero du premier bit a 1 ds x 
 
using namespace std;
 
int main()
{
	unsigned char first_bit[]= {1, 4, 0x80};// en  binaire: 1, 100, 10000000
	unsigned char count_bit[] = {5, 15, 91};// en binaire : 101 , 1111, 1011011
 
	cout << First_bit(0) << endl;//output : 0
	cout << First_bit(1) << endl;//output : 2
	cout << First_bit(2) << endl;//output : 7
 
	cout << Count_bit(0) << endl;// output : 2
	cout << Count_bit(1) << endl;// output : 4
	cout << Count_bit(2) << endl;// output : 5
 
	return 0;
}
unsigned int GetFirstBitAt1 (unsigned int x)
{
	unsigned int temp;
	__asm{
		bsf eax,x;
		jz zero;
		jmp end;
zero:
		xor eax,eax;
end:
		mov temp, eax;
	}
	return temp;
}
unsigned int CountBitAt1 (unsigned int x)
{
	unsigned int temp;
	_asm{
		xor ecx,ecx;//compteur de boucle
		xor edx,edx;//compteur de bits
		movzx eax,x;
boucle:
		bt eax,ecx;
		jnc nothing;
		inc edx;
nothing:
		inc ecx;
		cmp ecx,16; //nombre de bits pour un UCHAR (de 0 à 15)
		jb boucle;
		mov temp,edx;
	}
	return temp;
}

J'espère que ca t'ira

N'hésite pas si tu as des questions ou des remarques.

[Erickann]

Salut !

Merci pour ces deux fonctions.
Helas les performances sont decevantes comparees a celles des 2 look-up tables.

L'instruction bsf consomme tellement de cycles que sur mon pentium 4 la lecture dans la table est (legerement) plus rapide.

Pour ce qui est du comptage des bits je viens de trouver l'algo suivant dans le "Software Optimization Guide for the AMD64 processors" (dispo sur le site d'AMD et vraiment de qualite) (et dire que sur les procs cray ou sparc il y a une instruction pour le comptage des bits ...).

Code :

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
 
_inline unsigned int popcount(unsigned int v)
{
unsigned int retVal;
 
__asm
   {
    mov eax, [v]          ; v
    mov edx, eax          ; v
    shr eax, 1            ; v >> 1
    and eax, 055555555h   ; (v >> 1) & 0x55555555
    sub edx, eax          ; w = v - ((v >> 1) & 0x55555555)
    mov eax, edx          ; w
    shr edx, 2            ; w >> 2
    and eax, 033333333h   ; w & 0x33333333
    and edx, 033333333h   ; (w >> 2) & 0x33333333
    add eax, edx          ; x = (w & 0x33333333) + ((w >> 2) & 0x33333333)
    mov edx, eax          ; x
    shr eax, 4            ; x >> 4
    add eax, edx          ; x + (x >> 4)
    and eax, 00F0F0F0Fh   ; y = (x + (x >> 4) & 0x0F0F0F0F)
    imul eax, 001010101h  ; y * 0x01010101
    shr eax, 24           ; population count = (y * 0x01010101) >> 24
    mov retVal, eax       ; Store result.
   }
 
return(retVal);
}

C'est cependant 2 ou 3 fois plus lent que ma look-up table.
Mais je ne m'interesse qu'aux 16 premiers bits alors que l'algo "AMD" marche pour un unsigned de 32 bits.

Bref sur ce coup je suis decu, j'esperai pouvoir gagner de la vitesse sur ces 2 fonctions et ca ne semble pas possible.

Une derniere pensee : peut etre que pour un algo qui brasse beaucoup de memoire le fait de recharger tout le temps les look-up tables devient handicapant, et dans ce cas peut-etre que bsf et le code AMD se mettent a valoir le coup ...