« Les opérations bit à bit/Le branch-free code » : différence entre les versions

Contenu supprimé Contenu ajouté
mAucun résumé des modifications
Ligne 3 :
Le code branch-free est plus facile à écrire en assembleur que dans les langages de haut-niveau. La raison tient en l'utilisation des instructions à prédicat, qui rend très facile l'écriture des opérations suivantes. Le calcul du minimum ou maximum de deux nombres, qui sera vue plus loin, peut en effet s'écrire facilement avec des instructions CMOV. Les instructions à prédicats étant implémentées sur tous les jeux d'instruction grands public, les compilateurs peuvent, en théorie, les utiliser pour simplifier les opérations que nous allons voir. Mais le cout des opérations à prédicats est cependant assez élevé sur certaines architectures, ce qui rend les alternatives que nous allons présenter utiles, si ce n'est profitables. Ces techniques ont de plus le loisir d'être implémentables dans les langages de haut niveau. Voyons donc ces techniques dans le détail.
 
==DifférenceLa différence avec zéro==
 
Pour le premier calcul branche-free, nous allons voir le calcul de la '''différence avec zéro''', aussi appelée DOZ (difference of zero) par les anglo-saxons. Ce calcul très simple sera utilisé pour implémenter d'autres expressions branch-free, comme le calcul du minimum/maximum de deux nombres, ou la valeur absolue d'un nombre. Nous la voyons donc en premier, même si elle est de peu d'utilité pratique. Cette différence avec zéro se définit comme une soustraction qui donnerait 0 si son résultat est négatif.
Ligne 27 :
</syntaxhighlight>
 
==ValeurLa valeur absolue et son inverse==
 
Passons maintenant à la valeur absolue et à son inverse. Si je vous demande de calculer la valeur absolue d'un entier, vous allez certainement m'écrire le code suivant :
Ligne 43 :
Mais il existe des méthodes sans branchements qui donnent le même résultat.
 
===ValeurLe calcul de la valeur absolue===
 
Pour calculer la valeur absolue, il existe trois méthodes alternatives. Toutes ces méthodes nécessite d'isoler le bit de signe. Pour cela, il suffit d'utiliser un décalage logique pour déplacer ce bit et le mettre dans le bit de poids faible. Dans ce qui suit, ce bit de signe sera noté <math>y</math>. La valeur absolue d'un nombre x peut se calculer comme ceci :
Ligne 79 :
</syntaxhighlight>
 
===ValeurLe calcul de la valeur absolue inverse===
 
Pour obtenir l'inverse de la valeur absolue, il suffit de prendre l'opposée de celle-ci. En appliquant un simple - devant les expressions du dessus, on peut alors avoir diverses formules pour le calcul de l'inverse de la valeur absolue :
Ligne 89 :
: <math> \left[ ( 2 \times x ) . y \right] - x </math>.
 
==MinimumLe minimum et maximum d'un nombre==
 
Si je vous donne deux nombres et que je vous demande d'écrire un code qui renvoie le plus petit des deux, il y a de fortes chances que vous m'écriviez ceci :
Ligne 109 :
: <math>max ( x , y ) = y + doz ( x , y )</math>
 
===MinimumLe calcul du minimum de deux nombres===
 
Si on remplace le doz par l'expression vue plus haut, on trouve :
Ligne 130 :
L'idée derrière ce calcul est assez simple, bien que l'expression soit relativement compliquée. Pour la comprendre, il faut regarder ce qui se passe quand b < a et quand b >= a. Si b < a, alors la comparaison a < b renvoie un 0. Le terme complet (a ^ b) & -(a < b) donne alors 0 et l'expression se simplifie alors en b ^ 0, ce qui donne b. En clair, si b < a, alors le code renvoie b, ce qui est bien ce qu'on lui demande. Dans le cas où b >= a, alors la comparaison renvoie 1. Elle est alors inversée = le terme -(a < b) donne alors -1, ce qui est un nombre dont tous les bits sont à 1 en complément à 2. Le terme (a ^ b) & -(a < b) se simplifie donc en (a ^ b). L'expression totale est alors : b ^ (a ^ b). On sait que cela donne a. En clair, si a < b, le code renvoie a, ce qui lui est demandée.
 
===MaximumLe calcul du maximum de deux nombres===
 
On peut appliquer la même logique que précédemment, à savoir remplacer la doz par sa valeur calculée dans la première section. On trouve alors, après simplification, que le calcul du maximum est identique, si ce n'est qu'il faut inverser la comparaison. On doit alors calculer <math>b \oplus \left( (a \oplus b) . -(a > b) \right) </math>