mardi 20 mars 2018

Petit jeu

Y a-t-il encore de bons coders 68k dans la salle ?

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)


A vous de jouer : à gagner mon inestimable considération éternelle pour vous !
    

14 commentaires:

  1. Si vous trouvez, vous êtes très très fort !

    RépondreSupprimer
  2. On parle d'optimier en nb d'instructions et pas en cycles ?
    Ok, 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)

    RépondreSupprimer
    Réponses
    1. 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.

      Par 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...

      Supprimer
    2. 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...

      _VectorNormalize est importante : appelée 20 fois dans Quake 1 et 88 fois dans Quake 2...

      Supprimer
  3. Ah une boucle! C'est bien aussi.

    Je 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.

    RépondreSupprimer
    Réponses
    1. 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.

      Hum, 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...

      Supprimer
    2. Sacrifier quelques octets pour fdiv et fsqrt ?

      Il faudrait déjà lancer le profiler de gcc pour voir la fréquence d'utilisation de _VectorNormalize.

      Supprimer
    3. Pour d1, attends Barfly ne donne pas l'exposant...

      Supprimer
  4. Selon 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. :)

    Aprè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 :)

    RépondreSupprimer
    Réponses
    1. Je valide l'astuce d1 du début : et testé, ça marche. Bravo à toi !

      Nous sommes arrivé à une routine exceptionnelle là, avec 64 octets seulement !

      Pour le fdiv/fsqrt, ça serait le hack de Quake 3 avec la constante ?

      Supprimer
    2. 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...

      Dommage que le fmove.s fp0,d0 ne touche pas le SR...

      Supprimer
  5. Samuel DEVULDER22 mars 2018 à 14:55

    Héhé oui, quake 3.

    Ca 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)

    RépondreSupprimer
    Réponses
    1. J'en avais entendu parlé mais jamais testé...

      Ils 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...

      Supprimer
  6. Samuel DEVULDER22 mars 2018 à 19:23

    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

Posté vos remarques :