En travaillant sur des routines mathématiques, je me suis trouvé dans le besoin de coder en assembleur un décalage à droite non signé et de longeur variable: ((unsigned short)data)>>n.
J'ai donc été ammené à étudié diverses solutions à ce problème. On va supposer que data et n sont tout deux de 16 bits placé sur la pile avant d'appeller la routine de décalage (nota: pour n va de 0 à 255, donc la partie haute est nulle). Le résultat doit être dans D, et on peut trasher le registre X ainsi que les valeurs sur la pile. La taille du code n'est pas importante si elle reste raisonnable.
1) Approche naïveMa première approche fut de faire une boucle:
Code:
* naive
s0 ldd 2,s ; 6
ldx 4,s ; 6
beq s0_2 ; 3
s0_1 lsra ; 2
rorb ; 2
leax -1,x ; 5
bne s0_1 ; 3
s0_2 rts ; 5 => 20+n*12
Ce code est pas mal (c'est celui que GCC produit), mais je trouve que le surcout du leax/bne est vraiment très gros par rapport au décalage à proprement parler. On passe 2x plus de temps à faire l'administration de la boucle (8 cycles) que de faire ce à quoi elle sert (4 cycles). Tout ca tourne moralement 3x trop lentement.
Un décalage de 16 donne 0 en 212cycles. C'est énorme, il faut vraiment amméliorer ca.
2) Dichotomie 1J'ai donc cherché un code où l'on déroule la boucle le plus possible, de sorte à minimiser le cout de l'administration. En fait si on décompose n en binaire, si son bit 0 est à 1 il fait faire un décalage de 1 bit, si son bit 1 est à 1 il faut faire un décalage de 2 bits (donc 2x lsra rorb), si le bit 2 est à 1 il faut 4x lsra rorb. Si le bit 3 est à 1 on peut faire 8x lsra rorb d'un coup. Si les bits 4 à 7 sont à 1, c'est que n>=16 et il faut donc retourner 0.
Code:
(pseudo-code c)
if n&1 then data>>=1
if n&2 then data>>=2
if n&4 then data>>=4
if n&8 then data>>=8
if n&0xF0 then data=0
Ah oui! Il semble tout à fait possible de procéder ainsi. Et on peut même faire mieux, car 8x lsra rorb d'un coup (24 cycles) est équivalent à un "tfr a,b ; clra" (8 cycles). Ah oui c'est carrément bien ce truc!
Cela donne l'algorithme suivant:
Code:
s1 ldd 2,s ; 5
lsr 5,s ; 7
bcc s1_1 ; 3
lsra ; 2 bit0=1
rorb ; 2
s1_1 lsr 5,s ; 7
bcc s1_2 ; 3
lsra ; 2 bit1=1 => 2 décalages
rorb ; 2
lsra ; 2
rorb ; 2
s1_2 lsr 5,s ; 7
bcc s1_3 ; 3
lsra ; 2 bit2=1 => 4 déclages
rorb
lsra
rorb
lsra
rorb
lsra
rorb
s1_3 lsr 5,s ; 7
bne s1_5 ; 3
bcc s1_4 ; 3
tfr a,b ; 6 bit3=1 => 8 décalages (optimisé)
clra ; 2
s1_4 rts ; 5
s1_5 ldd #0 ; 3 l'un des bits 4...7 à 1 => zero
rts ; 5
Quelle est la complexité de cet algo ? On fait 4 tests sur les bits (7+3=10 cycles), et un nombre de décalages proportionnel à n pour n de 0 à 7, au delà de 8, on fait un nombre de décalage proportionnel à (n-8). J'obtiens le tableau suivant
- 0<=n<=7 ---> 53+4*n
- 8<=n<=15 ---> 61+4*(n-8)
- 16<=n ---> 64+4*(n&7)
Hum..53 cycles minimaux, même quandd on ne fait rien à la donnée (n=0). C'est pas génial. Le cout du test sur les bits prend à lui seul 4*10=40cycles. C'est énorme. Ce qui grève les perfs c'est le LSR en mémoire systématique même s'il n'est pas suivi d'un décalage. Un LSR sur un registre serait nettement moins couteux.
3) Dichotomie 2On pourrait donc voir à charger dans A la valeur de n, et faire un décalage en mémoire uniquement pour le MSB de la donnée. Comme on ne décale pas forcément la donnée pour chaque bit de n, on devrait avoir un gain sur la moyenne. Ca donne le code suivant
Code:
t1 ldb 3,s ; 5
lda 5,s ; 5
lsra ; 2
bcc t1_1 ; 3
lsr 2,s ; 7
rorb ; 2
t1_1 lsra ; 2
bcc t1_2 ; 3
lsr 2,s
rorb ; 2
lsr 2,s ; 7
rorb
t1_2 lsra ; 2
bcc t1_3 ; 3
lsr 2,s
rorb
lsr 2,s
rorb
lsr 2,s
rorb
t1_3 lsra ; 2
bne t1_5 ; 3
bcc t1_4 ; 3
ldb 2,s ; 5
clra ; 2
rts ; 5
t1_4 lda 2,s ; 5
rts ; 5
t1_5 ldd #0 ; 3
rts ; 5
qui coute quelque chose comme
- 0<=n<=7 ---> 43+(n&7)*9
- 8<=n<=15 ---> 45+(n&7)*9
- 16<=n ---> 38+(n&7)*9
Alors oui avec n=0, on tombe à 43 cycles, c'est mieux que les 61 de "dichotomie 1". La constante fixe est plus faible qu'avant. Par contre le cout de chaque bit à 1 dans n est plus gros (9), mais quand même plus petit que le cout de la boucle de l'algo naïf (12). Le pire cas se produit donc lorsque n=15 (tous les bits à 1) avec 108cycles. Hum... 108 c'est beaucoup quand même