Est-il intéressant d'assembler une ensemble de booléens dans un entier de taille définie ?

Celui qui effectue cette optimisation a généralement deux buts à l'esprit. Le premier but est d'accélérer les performances, et le second est de réduire la taille mémoire. Dans certains cas, les deux buts sont explicitement visés et peuvent être atteints. Dans d'autres cas, seul l'un des buts nous intéresse.

Effets sur l'empreinte mémoire

Déjà, quel est le principe derrière cette idée ? C'est relativement simple : on se sert d'un type scalaire entier (char, short, int, long, long long) pour stocker un ensemble de drapeaux indépendants. Il ne s'agit donc pas de stocker des bits ayant un rapport logiques entre eux, mais bel et bien de mettre N booléens dans un même espace. On réduit d'autant l'empreinte mémoire (puisqu'on peut stocker 32 booléens sur un int[1] au lieu de stocker 32 booléens dans 32 bool différents). On peut comprendre aisément que si on doit avoir N booléen par objet et qu'on a K objet (avec K très grand : plusieurs millions), alors la solution du regroupement prend tout son sens - il ne reste plus qu'à choisir le type d'entier sur lequel on va les stocker.

Effets sur les performances

En termes de performances, le constat est moins clair. Un scalaire de type bool est généralement placée à une adresse mémoire alignée, et il ne faut qu'un instruction pour le récupérer. Une autre instruction est utilisée pour tester sa valeur, et on rajoute une instruction pour effectuer un saut en fonction du résultat du test. Typiquement, le code assembleur x86 va ressembler à :

// C++
bool b;
...
if (b) {
   ...
}

// Pseudo-assembleur x86:
    mov ebx, [adresse alignée sur la stack ou dans le tas]
    test bl,bl
    jne LABEL
    ...
LABEL:
   ... (continue)

Le compilateur va préférer aligner les accès, même s'il considère que la variable de type bool ne fait que 8 bits (d'où le test sur le sous registre bl malgré le chargement dans ebx ; selon les options de compilation sélectionnées, il est possible qu'il ne charge que bl - il n'y a pas de gain de temps (en fait, les microprocesseurs x86 et x86_64 exécute un peu plus de microcode dans ce cas, mais la différence est négligeable)).

L'accès à un drapeau spécifique dans une variable nécessite l'utilisation d'une instruction qui va remplacer l'instruction test. Généralement, c'est une instruction and qui est utilisée.

// C++
int flags;
...
if (flags & SOME_BIT) {
  ...
}

// Pseudo-assembleur x86:
    mov ebx, [adresse alignée sur la stack ou dans le tas]
    and HEX_VALUE, ebx
    jne LABEL
    ...
LABEL:
   ... (continue)

Au niveau temps d'exécution, l'accès à un booléen et l'accès à un drapeau dans un entier sont similaires, voir égaux. Dans ce cas, comment peut-on espérer gagner en performance ?

Il y a deux points à prendre en compte ici : si les booléens sont récupérés ou envoyés par un système de flux quelconque (fichier ou socket), alors il est préférable de stocker ces booléens en tant que drapeaux dans un entier - la raison est triviale : il y a ainsi moins de données à transférer.

Le second point est lié à l'utilisation qui est faite de ces booléens. Si plusieurs booléens sont utilisés sur dans une même fonction, un entier composé de drapeaux a un intérêt, car il y a de grandes chances qu'on ait besoin de le charger dans un registre une seule et unique fois - c'est encore plus important sur x86 à cause du faible nombre de registres disponibles. L'utilisation d'un nombre importants de booléens peut provoquer des chargements/déchargements de registres qui ne sont pas souhaitables du point de vue des performances.

Il y a un autre point relatif aux performances qu'il faut aussi prendre en considération : quel type de donnée sous-jacent doit-on choisir ?

Conclusion

Pour conclure ce point, on dégage une pseudo-règle d'utilisation des drapeaux contre booléens.

On utilise des entiers composés de plusieurs drapeaux :

  • dans le cas où on a besoin de stocker plusieurs booléens par objet, sur de très nombreux objets ;
  • dans le cas où on écrit ces booléens sur disque ou qu'on les envoie dans une socket de manière répétée ;
  • dans le cas où on utilise plusieurs de ces booléens dans une partie du code, et que ces booléens sont reliés sémantiquement ;

Note

[1] architecture 32 bits classique