Les opérations bit à bit/Le branch-free code

De nombreuses opérations se calculent en faisant intervenir des branchements. Par exemple, si je vous demande de calculer la valeur absolue d'un entier, vous allez certainement m'écrire un code qui utilise des branchements. De nombreux calculs simples du même genre existent. Le calcul du minimum de deux nombres ou de leur maximum est l'un d'eux. Mais certains de ces calculs peuvent se faire sans utiliser de branchements ! Pour cela, il faut utiliser des techniques de manipulation de bit ou des opérations logiques. On obtient alors du branch-free code, du code sans branchements. Un tel code est très utile pour éliminer les branchements et gagner en performances. Il élimine les problèmes liés au branchements : mauvaises prédictions de branchement, meilleure utilisation du parallélisme d'instruction, etc. Le compilateur profite aussi de ces techniques, celui-ci se débrouillant mieux avec des blocs de code de grande taille. Certaines optimisations fonctionnent en effet nettement mieux quand il n'y a pas de branchements pour les gêner.

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.

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

$doz(x,y)=\left\{{\begin{array}{r c l}x-y,x>y\\0,x\leq y\\\end{array}}\right.$

Ce calcul s'implémente avec l'expression suivante, qui fonctionne avec des opérandes signées et non-signées :

$(x-y).-(x\geq y)$

int doz (int x, int y)
{
    return ( x - y ) && - ( x >= y ) ;
}

La 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 :

int abs (int a)
{
    if (a > 0)
        return a ;
    else
        return - a ;
}

Mais il existe des méthodes sans branchements qui donnent le même résultat.

Le 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é $y$. La valeur absolue d'un nombre x peut se calculer comme ceci :

$(x\oplus y)-y$ ;

$(x+y)\oplus y$ ;

$x-\left[(2\times x).y\right]$.

Les codes correspondant à chaque ligne est le suivant pour des entiers de 32 bits :

int abs (int x)
{
    int y = x >> 31 ;
    return (x ^ y) - y ;
}

int abs (int x)
{
    int y = x >> 31 ;
    return x - ( (x << 1) & y ) ;
}

int abs (int x)
{
    int y = x >> 31 ;
    return (x + y) ^ y ;
}

Le 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 :

$y-(x\oplus y)$ ;

$(y-x)\oplus y$ ;

$\left[(2\times x).y\right]-x$.

Le 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 :

int min (int a , int b)
{
    if (a > b)
        return b ;
    else
        return a ;
}

Une autre manière est d'utiliser la différence avec zéro. En effet, on sait que :

$min(x,y)=x-doz(x,y)$

$max(x,y)=y+doz(x,y)$

Le calcul du minimum de deux nombres

Si on remplace le doz par l'expression vue plus haut, on trouve :

$min(a,b)=a-(a-b).-(a\geq b)$

Divers simplifications algébriques et booléennes donnent ensuite :

$min(a,b)=b\oplus \left((a\oplus b).-(a<b)\right)$

Voici le code qui correspond :

int min (int a , int b)
{
    return b ^ ( (a ^ b) & -(a < b) ) ;
}

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.

Le 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 $b\oplus \left((a\oplus b).-(a>b)\right)$

int max (int a , int b)
{
    return b ^ ( (a ^ b) & -(a > b) ) ;
}

Appliquer un masque différemment suivant le résultat d'une condition

Appliquer un masque sur un nombre permet de mettre à 1 les bits choisit, ou alors de les mettre à zéro. On peut vouloir faire l'un ou l'autre selon si une condition bien précise est remplie : on met à 1 les bits si la condition est remplie, à 0 sinon. Le code qui correspondrait serait celui-ci :

bool condition_result;         // Résultat de la condition
unsigned int mask ; // Le masque
unsigned int word ; // Nombre à maquer

if (condition_result)
{
    word |= mask ; // mettre à 1 les bits voulus
}
else
{
    word &= ~mask ; // mettre à 0 les bits voulus
}

Il existe deux solutions sans branchements. La première est celle-ci :

bool condition_result ;         // Résultat de la condition
unsigned int mask ; // Le masque
unsigned int word; // Nombre à maquer

word ^= ( - condition_result ^ word) & mask ;

Une solution équivalente serait la suivante :

bool f;         // Résultat de la condition
unsigned int m; // Le masque
unsigned int w; // Nombre à maquer

word = (word & ~mask) | ( - condition_result & mask );