Roman Merz wrote:
> Pas C++, car le code produit ne serait pas aussi facilement
> lisible.
Ah ? �tonnant.
Avec GCC 3.2 en tout cas les deux codes produits sont aussi
lisibles, � l'exception du mangling de nom de fonction en C++.
> test1 & test2:
> 080484B6 31 DB xor ebx , ebx ; a = 0
> 080484B8 8B 55 08 mov edx , [ebp+0x08] ; load w
> 080484BB 90 nop ; --
> 080484BC 8D 74 26 00 lea esi , [esi] ; --
> 080484C0 89 D0 mov eax , edx ; copy w
> 080484C2 D1 EA shr edx , 0x1 ; shift w
> 080484C4 83 E0 01 and eax , 0x1 ; test w
> 080484C7 41 inc ecx ; loop counter
> 080484C8 01 C3 add ebx , eax ; update a
> 080484CA 83 F9 0F cmp ecx , 0xF ; loop finished?
> 080484CD 76 F1 jbe...
>
> Le code produit est identique dans les deux cas. Mais gcc
> n'arrive pour une fois pas de remplacer inc ecx; cmp ecx,
> 0xF par un dec ecx.
Le passage � GCC >=3.1 est tr�s b�n�fique du c�t� des
optimisations. Sur un programme C++ de jeu de dames j'ai
gagn� dans les 40% ! En l'occurrence il utilise "dec" ici :
.L13:
movl %edx, %eax
shrl %edx
andl $1, %eax
addl %eax, %ebx
decl %ecx
jns .L13
En compilant sp�cialement pour K6, il utilise une instruction
"loop" qui d�cr�mente ecx et saute :
.L16:
movl %edx, %eax
shrl $1, %edx
andl $1, %eax
addl %eax, %ebx
loop .L16
5 instructions, pas mal. Quoique sur Athlon cette instruction
est fortement d�conseill�e, 8 cycles d'ex�cution !
> test3b:
> for (i=16;i--;) {...}
>
> Souvent vu comme recommondation. Je ne suis pas de cet avis,
> car c'est
> traduit par
> mov ecx, 0xF
> Loop:
> dec ecx
> cmp ecx, -0x1
> jnz Loop
Idem avec GCC 3.2, sauf en compilant pour K6 qui donne � nouveau
la version en 5 instructions avec "loop" !
> test4:
> while (w != 0) {
> a += w & 1;
> w >>= 1;
> }
>
> Bien d'accord que des autres principes peuvent etre plus
> efficaces.
� remarquer que cette version, avec une distribution al�atoire et
� �gale probabilit� des bits, est en moyenne plus rapide car la
boucle n'est pas toujours effectu�e 16 fois comme avec un for.
D'o� (sauf erreur) :
1/2^16 : 0 it�ration
1/2^16 : 1 it�ration
2/2^16 : 2 it�rations
4/2^16 : 3 it�rations
8/2^16 : 4 it�rations
...
32768/2^16 : 16 it�rations
D'o� un nombre moyen d'it�rations de
(somme n=0..15(2^n*(n+1)))/2^16 = (aid� de Knuth)
((15*2^(15+2)-(15+1)*2^(15+1)+2)/(2-1)^2+2^(15+1)-1)/2^16=
15.00001525878906250000
Ce qui fait un gain de presque une it�ration. Mouais, on doit
pouvoir prouver bien plus simplement que �a tend vers une
it�ration de gain...
De toute fa�on on reste dans les m�mes complexit�s d'algorithme.
Mais sur ce genre de petites manipulations, avec un processeur
CISC, les compilateurs semblent encore assez loin de solutions
optimales.
Sur Motorola 68000 (d�sol�, je ne connais pas assez le 386, d�j�
le 68000 j'oublie), une boucle de 3 instructions :
; IN D0.w mot
; OUT D1.w nb de bits
move.w D2,-(SP); D2 sera utilis� pour optimiser
sub.w D2,D2 ; D2 = 0; bit X = 0
Loop:
addx.w
D2,D1
; D1 += 0 + X
add.w D0,D0 ; D0 += D0; X = retenue
bne.b Loop ; if (D0 != 0) goto Loop
move.w (SP)+,D2; restaure D2
Le guide AMD Athlon Processor x86 Code Optimization Guide �
http://www.amd.com/us-en/Processors/ProductInformation/0,,30_118_756_759%5E2983,00.html
donne une version bas�e sur l'algorithme point� par Ivo.
17 instructions pour compter les bits d'un mot de 32 bits, pas mal. :-)
En MMX il donne une version aussi rapide, mais sur 64 bits.
Marc Mongenet
--
http://www-internal.alphanet.ch/linux-leman/ avant de poser
une question. Ouais, pour se d�sabonner aussi.
