Duff's Device
Par Greg le vendredi, juillet 2 2010, 23:13 - Algo - Lien permanent
En lisant vite fait un topic sur playeradvance.org je suis tombé sur une remarque de Nesgba (que je salue au passage ^^) : "tu peux utiliser le fameux duff-device en version asm pour accélérer le traitement. "
Bon, alors le fameux duff-device, je ne connaissais pas... Un petit tour sur Wikipedia plus tard, je vois qu'en fait, si, je connaissais, mais pas son nom. Il faut rendre à César ce qui est à César... C'est donc Tom Duff qui a pondu ça en 1983 
Même si la plupart doivent connaitre, je me dis que c'est une belle astuce, et que donc ça peut être intéressant de la présenter ici...
Boucle de base
Le principe est simple : parfois (ou souvent) on a besoin de copier pas mal d'octets d'un endroit à un autre. La boucle de base pourrait donc être de la forme suivante :
do {
*to++ = *from++;
} while (--count > 0);
(à noter qu'à l'origine le code de Duff utilise juste "*to" car il file ça en sortie, mais pour plus de clareté j'ai décidé de montrer la version plus "usuelle"...
Donc avec cette simple boucle, on parcourt "count" octets (ou int ou autre) et on fait une copie. Rien de particulier, en somme.
Le principe de base est que parfois, pour accélérer une boucle, il peut être utile de la déboucler... Là, après chaque "tour de boucle", on va décrémenter count et faire le test "count > 0", puis sauter au début de la boucle et recommencer. En fait ces 3 opérations ont un coup qui in fine peut être important, comparativement à la simple copie mémoire et incrémentation des pointeurs. Afin de minimiser ce coup, on pourrait faire quelque chose comme ça :
do {
*to++ = *from++;
*to++ = *from++;
count -= 2;
} while (count > 0);
Là, à chaque tour de boucle, on effectue 2 fois la copie, mais une seule fois le changement de valeur de count, une seule comparaison, et un seul saut. On devrait donc en théorie gagner un tout petit peu en performances. Et on pourrait imaginer déboucler encore plus, pour faire le traitement 3, 4, 5, 100 fois ?
Sauf que là le code présente un défaut majeur : si count est impair, on écrit 1 fois de trop, ce qui est rarement bon ^^ Et si on déboucle encore plus, ça va être pire... Du coup il faudrait en fait faire 2 boucles, une première pour faire juste n traitements et avoir un nombre d'itérations à faire multiple qui va bien, puis les itérations dans la boucle déroulée (sans risque de débordement, donc).
Boucle, version Duff...
Duff a donc trouvé une belle astuce en utilisant une spécicité des blocs switch/case en C. Je vous présente son code et on en parle :
n=(count+7)/8;
switch(count%8){
case 0: do{ *to++ = *from++;
case 7: *to++ = *from++;
case 6: *to++ = *from++;
case 5: *to++ = *from++;
case 4: *to++ = *from++;
case 3: *to++ = *from++;
case 2: *to++ = *from++;
case 1: *to++ = *from++;
}while(--n>0);
}
Il y a plusieurs choses qu'on peut trouver un peu bizarres dans ce code : le switch/case avec les valeurs de 0 à 7 (pas forcément évident qu'on gagne en perf avec ça !), mais aussi (et surtout) le "do{" en plein milieu du case 0:.... C'est pour le moins original ^^
Je pense que le mieux pour comprendre ce qui se passe est alors de voir ce que ça donne en déroulant le bout de code... On arrive avec un count qui a une valeur quelconque (qu'on va supposer non multiple de 8, car là visiblement on a 8 fois la copie donc on va chercher à faire tout ce qui pourrait mal tourner). La valeur mise dans n permet en fait de savoir combien de fois il faudrait boucler pour tout copier, si on on fait effectivement les copies 8 par 8... Jusque là, rien de fou.
La valeur passée au switch permet, quand a elle, de donner en fait combien de copie non multiples de 8 sont à faire... Si (count%8) vaut 0, alors on va juste faire les 8 à la suite (rappel : un case sans break va exécuter tout code qui suit), si ça vaut 7 alors on doit en faire 7 pour que le reste soit multiple de 8, ...
On voit de façon assez naturelle que le while de la fin permet de boucler (même si on aurait probablement préféré le mettre hors du switch ^^), en utilisant "n", donc le compteur ramené pour compter 8 à 8. Mais alors pourquoi ce do{ un peu foireux au milieu du case 0 plutôt que de l'avoir mis, de façon plus naturelle, avant le switch ? En fait, dans un do...while, le do indique juste là où on va revenir, et ne sert qu'à ça. Donc là, comme après un premier tour on sait que le nombre de copies restantes sera un multiple de 8, on n'a plus jamais besoin de tester combien copier et on peut partir dans une copie 8 à 8 !
Avec ce bout de code, on obtient donc un déroulage bien compacte, et le même code sert à "l'initialisation" (ie, la partie du début qui sert à s'assurer qu'on tombe juste). La grande question qu'on peut se poser est alors : "mais comment ça marche ?". Après tout, un switch/case est généralement utilisé dans un cadre où on pourrait avoir des if/else à gogo, donc on a souvent en tête un schéma du genre
if (count%8 == 0) ... else if (count%8 == 7) ... etc...
Sauf qu'en pratique, il faudrait voir le code assembleur, et ce n'est pas généré comme ça. Pour faire simple, on va avoir le contenu de tous les cases collés les uns à la suite des autres, et si on a un break, ça ajoute un goto menant à la fin de tous les cases. Et en fait avant cette portion de code, on aura les gotos qui permettent de sauter à la section adaptée. Pour les compilos qui optimise ne serait-ce qu'un minimum, un switch/case avec des belles valeurs de 0 à 7 comme ça va en fait être transformé en tableau contenant les sauts à faire, et donc on récupère directement dans ce tableau où sauter en fonction de count%8. Donc tout celà est extrêment rapide et efficace
Conclusion et relativisation
A noter, pour finir, que normalement la lib C standard fourni la fonction memcpy pour ce genre de traitements, et que celle-ci ne devrait (en théorie) jamais être plus lente que l'algo de Duff. Pour certains CPU elle utilise mêmes des instructions spécifiques bien optimales, bien plus rapides... Je pense néanmoins que cette technique peut être utile quand on a un traitement légèrement différent qu'une simple copie à faire, et que donc un memcpy ne peut pas faire l'affaire. Je vais voir si ça peut me servir au boulot (j'ai une routine en tête qui pourrait en profiter) et le gain que ça pourrait représenter. Pas sûr que ce soit énorme dans mon cas car on ne fait pas une simple copie mais un petit traitement au passage, mais ça reste du débouclage, donc potentiellement bénéfique. D'aileurs à l'époque où je faisais des jeux sur PocketPC et qu'on faisait tout l'affichage à la main ça aurait surement été utile pour obtenir de meilleures perfs...
Je tiens à signaler que ce billet n'est qu'une copie/réinterprétation honteuse de l'article de Wikipedia correspondant, je vous invite donc à aller le consulter ici : http://en.wikipedia.org/wiki/Duff's_device