Y a-t-il encore de bons coders 68k dans la salle ?
Ou alors quelques uns qui veulent améliorer leur niveau ?
Ou alors quelques uns qui veulent améliorer leur niveau ?
Petit jeu remue-méninge aujourd'hui que je vous propose : la routine _VectorNormalize dans Quake pèse 164 octets (40 instructions) compilée avec gcc 2.95.3. La sous-routine _DPSqrt n'a aucune importance :
Qui arrivera à l'optimiser pour un résultat final de seulement 66 octets (19 instructions) ?
(Le résultat final doit être dans d0)
(Le résultat final doit être dans d0)
A vous de jouer : à gagner mon inestimable considération éternelle pour vous !
Si vous trouvez, vous êtes très très fort !
RépondreSupprimerOn parle d'optimier en nb d'instructions et pas en cycles ?
RépondreSupprimerOk, voici ma solution qui calcule:
w = 1/sqrt(x*x + y*y + z*z)
x *= w
y *= w
Z *= w
(pseudo C) en 17 instructions et 58 octets. Je crois que
c'est encore plus court que celle que tu as imaginé ;)
-8<--------------------------------------------------------
_VectorNormalize
move.l 4(sp),a0 ; pointeur sur vecteur
fmove.s (a0)+,fp0
fmul fp0,fp0
bsr.b .add
bsr.b .add
fsqrt fp0,fp1 ; fp1=sqrt(fp0)
fdiv fp0,fp1 ; fp1=sqrt(fp0)/fp0=1/sqrt(f0)
bsr.b .mul
bsr.b .mul
.mul ; Semantique: -(a0) *= fp1
fmove.s -(a0),fp0
fmul fp1,fp0
fmove.s fp0,(a0)
rts
.add ; sémantique fp0 += ((a0)+)^2
fmove.s (a0)+,fp1
fmul fp1,fp1
fadd fp1,fp0
rts
-8<--------------------------------------------------------
Quelques remarques:
1) J'ai viré le
fcmp fp1,fp1
fbne .whatthat?
car il est toujours vrai sauf si fp1 est un NaN chose
qui ne se produit pas dans quake.
2) Le fbeq.w qui suit peut aussi être éliminé, il évite
une division par zero dont on se fiche car contrairement
aux entiers en IEEE ca ne provoque pas de TRAP mais un
INF parfaitement défini et utilisable.
3) pour le calcul de 1/sqrt(w) j'utilise sqrt(w)/w ce qui
fait gagner pleins d'octets.
3) j'ai factorisé les oppérations de l'addition du carré
dans la routine locale ".add". C'est pas optimal en cycles
cpu, mais puisque le but est de réduire le nb d'instructions
c'est bien :)
4) idem, j'ai factorisé les multiplications successives
fmove.s -(a0),fp0
fmul fp1,fp0
fmove.s fp0,(a0)
dans ".mul". On gagne des instructions ainsi et surtout
on élimine un
bsr.s .mul
rts
en plaçant ".mul" au bon endroit. Re bien :)
5) l'optim en instructions n'est pas forcément intéressante.
Il y a dans le code de base 2 instructions plutot courtes
mais couteuses en cycles sur 68882: le fdiv et le fsqrt.
Il vaut mieux les éliminer.
Je sais le faire, mais je te laisse y réfléchir Cosmos avant
de donner ma solution avec la même routine carburant un max
sur 68882 et plus. :)
sam (PULS/6809e)
Je préfère toujours gagner en nombre d'instructions, c'est mieux je trouve... Choix perso, il y a souvent plusieurs possibilités qui se valent plus ou moins.
SupprimerPar contre, le résultat final doit être dans d0, donc ta routine n'est pas tout à fait conforme à l'orignal !!
Ma solution utilisait plutôt les loops, et pèse donc 2 instructions de plus que la tienne : l'avantage c'est que les boucles coûtent moins de cycles que les bsr/rts (7 cycles pour le rts sur un 060 et le bsr utilise un write PC sur la pile). Après laquelle de la tienne est plus rapide que la mienne, ça se vaut : 58 octets avec bsr/rts (mais return d0 manquant) vs 66 avec loops.
Voici ma routine (la belle astuce est dans d1) :
_VectorNormalize_66bytes
move.l 0+4*1(sp),a0 ; arg1
moveq #%1011,d1
fmove.b #$00,fp0
.loop_1
fmove.s (a0)+,fp1
fmul.x fp1,fp1
fadd.x fp1,fp0
lsr.b #1,d1
bcs.b .loop_1
fsqrt.x fp0
fmove.s fp0,d0 ; return in d0
fbeq.w .end
fmove.b d1,fp1
fdiv.x fp0,fp1
.loop_2
fmove.s -(a0),fp0
fmul.x fp1,fp0
subq.b #1,d1
fmove.s fp0,(a0)
bls.b .loop_2
.end
rts
Sinon, pour éliminer le fdiv et le fsqrt, je ne vois pas trop...
Attention : fbeq est indispensable. Lorsque je la supprime, j'ai bien la démo qui fonctionne au lancement du jeu mais ensuite écran noir quand je veux jouer...
Supprimer_VectorNormalize est importante : appelée 20 fois dans Quake 1 et 88 fois dans Quake 2...
Ah une boucle! C'est bien aussi.
RépondreSupprimerJe vois comment gagner 2 octets sur ta version. Le fmove.b #0,fp1 peut être replacé par fmove.s d1,fp0, ce qui donne un résultat voisin. En effet la valeur de d1 en ce point est un flottant dénormalisé en IEEE754, cad une valeur infinitesimalement proche de 0. Cette valeur passe à 0 sitôt qu'on y ajoute un flottant normal, cad au prochain fadd. Avec cette astuce, bingo! Tu passes à 64 octets (gain: 2 octets). :)
Sinon dans mes souvenirs, la valeur retournée par cette routine n'est pas
utilisée dans le code C d'origine, donc on peu ignorer la recopie dans
d0. Cependant, si on y tient quand même il faut ajouter fmove.s fp1,d0
juste après le fsqrt dans le code. Il augmente alors de 4 octets, soit
un total de 62 octets. Ca reste encore le plus court que ta version même optimisée avec le float dénormalisé. :)
Dans tous les cas il reste le fsqrt et le fdiv qui sont quand même super couteux en cycles. Si on veut une version plus rapide, on peut sacrifier
quelques octets pour calculer 1/sqrt(w) super super rapidement.
Oui, les boucles peuvent être mieux que les bsr/rts : imagine que _VectorNormalize soit dans une boucle externe importante, et bien tes 4 bsr/rts vont être assez coûteux... bsr/rts a utiliser avec précaution, au cas par cas. Prudence avec eux.
SupprimerHum, d1 au tout début est à environ 1.54 quand même une fois dans le fp0...
fdiv et fsqrt prennent beaucoup de cycles oui... S'il était possible de les réduire, ça serait super...
Sacrifier quelques octets pour fdiv et fsqrt ?
SupprimerIl faudrait déjà lancer le profiler de gcc pour voir la fréquence d'utilisation de _VectorNormalize.
Pour d1, attends Barfly ne donne pas l'exposant...
SupprimerSelon https://www.h-schmidt.net/FloatConverter/IEEE754.html, %1011 interprété en float32 (move.s d1,fp0) donne le flottant: 1.5E-44, autant dire 0. il n'y a pas de soucis avec l'optim que j'indique. :)
RépondreSupprimerAprès sur les cpu "moderne" les équivalents de jsr/rts n'ecrivent pas vraiment en mémoire et peuvent maintenir un cache des derniers appels. Du coup ils coutent beaucoup moins cher qu'avant. Mais bon si on target le 060, on y a pas droit, c'est sur.
Pour le fsqrt, je donnerais la soluce quand je serais chez moi. A moins que tu ne trouves d'ici là. C'est une vieille technique. C'est tout ce que je peux dire. Enfin vieille... pas plus vieille que nos amiga :)
Je valide l'astuce d1 du début : et testé, ça marche. Bravo à toi !
SupprimerNous sommes arrivé à une routine exceptionnelle là, avec 64 octets seulement !
Pour le fdiv/fsqrt, ça serait le hack de Quake 3 avec la constante ?
Il est peut-être possible de gagner encore un peu en remplaçant le fbeq.w par tst.l d0 et beq.b : même nombre d'octets, mais partie integer possiblement plus rapide...
SupprimerDommage que le fmove.s fp0,d0 ne touche pas le SR...
Héhé oui, quake 3.
RépondreSupprimerCa marche super bien. Je l'utilise via une macro dans mon monkey:
* fp0 = 1/fsqrt(fp0) (\1=fp0, \2=d1 (trashed), \3=fp1 (trashed))
rsqrt macro
fmove.s \1,\2
lsr.l #1,\2
sub.l #$5f3759df,\2
fmul.s #0.5,\1
neg.l \2
fmul.s \2,\1
fneg.s \2,\3
fmul.s \2,\1
fsub.s #1.5,\1
fmul.x \3,\1
endm
xdef _normalize3
xdef @normalize3
_normalize3
ifeq REGPARM
move.l 4(sp),a0
endc
@normalize3
move.l (sp)+,a1
fmovem fp2-fp5,-(sp)
fmove.s (a0)+,fp3
fmove.s (a0)+,fp4
fmove.s (a0),fp5
fmove fp3,fp0
fmove fp4,fp1
fmove fp5,fp2
fmul fp0,fp0
fmul fp1,fp1
fmul fp2,fp2
fadd fp1,fp0
fadd fp2,fp0
* fp0=1/sqrt(fp0)
rsqrt fp0,d1,fp1
fmul fp0,fp5
fmul fp0,fp4
fmul fp0,fp3
fmove.s fp5,-(a0)
fmove.s fp4,-(a0)
fmove.s fp3,(a0)
fmovem (sp)+,fp2-fp5
jmp (a1)
J'en avais entendu parlé mais jamais testé...
SupprimerIls parlent d'approximation aussi...
Ensuite, il faut tester dans le jeu réel et faire un bench voir si c'est vraiment plus rapide ou pas...
L'approximation ci-dessus est bonne à 0.1% ce qui est largement suffisant pour le quotidien. On parle de quake, pas d'un prog qui trouve la 10000000000000000e décimale de pi. C'est l'algo +/- inventé ou réutilisé par Carmack. Si c'est bon pour lui, c'est aussi bon pour nous.
RépondreSupprimer