05 janv. 2013

Micro-optimisations : booléens contre ensemble de drapeaux

Il y a quelque temps, un utilisateur de mon blog (alpha_one_x86) a proposé quelques sujets qui avait pour lui un intérêt. Certains sujets traitant de micro-optimisations - et étant moi même intéressé par ce type d'optimisation - j'ai décide de consacrer un premier billet à quelques petites explications touchant non pas au comment, mais au pourquoi.

Si vous avez des questions liées à ce type de sujet (ou si vous souhaitez que je discute d'autres micro-optimisations), n'ayez pas peur de me le faire savoir en postant un commentaire ici ou là (voir en me contactant).

Je vais quand même insister sur un point précis : je parle ici de micro-optimisation, c'est à dire d'optimisations dont l'impact sur les performances est très souvent négligeable. Il arrive de temps en temps qu'une telle optimisation offre un réel avantage, mais ces cas sont rares. Avant de mettre en pratique un des cas présenté ci-dessous, il convient de mesurer l'impact sur votre code et de peser le pour et le contre, notamment en terme de rapport gain/maintenance et gain/temps de développement.

Ne venez pas dire que je ne vous ai pas prévenu :)

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

Commentaires

1. Le samedi, janvier 5 2013, 16:56 par alpha_one_x86

Dans mon cas j'ai 5 couches, en 32x32 de bool, el tout par map. Soit 5Ko en bool par map. Je passerai à 1Ko en groupant les bool dans 8Bits. Faut que je vois ce que ça donne (si ça diminue la mémoire sans trop diminuer les performances ça me vas).

2. Le dimanche, janvier 6 2013, 00:39 par Emmanuel Deloget

Dans ton cas, tu va avoir un autre gain dont je n'ai pas parlé. Si tes drapeaux sont stockés dans un espace contigu, et que le début de la zone mémoire correspond au début d'une page (prt % 4K = 0 sur un système 32 bits), alors tu n'auras pas de page miss lorsque tu accéderas à ton tableau. De plus, tu va pouvoir profiter de la localité des données dans le cache, ce qui aura aussi un effet bénéfique. Par contre, j'aurais tendance à conseiller d'utiliser des entiers de 32 bits, et pas des char - ces derniers ne profitent pas toujours du microcode x86 inter au processeur et optimisé pour les accès alignés. Le changement de performances peut être assez drastique si ces données sont très souvent employées.

Au final, les performances devraient être légèrement améliorées - mais bon, tu le sais, tout ça, ça se mesure :)

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet