11 mar. 2012

Optimisation : de la prédiction des branchements

Ne me demandez pas pourquoi j'écris aujourd'hui sur un sujet qui semble si éloigné de mon domaine de prédilection, l'architecture logicielle et le code haut niveau (je vous rassure, ce n'est pas mon seul domaine de compétence). Je n'en ai pas la moindre idée. C'est peut-être le fait d'avoir ce manuel d'optimisation des processeurs Intel sur mon étagère, bien en face de mes yeux. Ou parce que c'est un sujet dont nous avons discuté récemment au travail. Ou parce que ça traînait dans ma tête depuis un petit moment déjà. Ou parce que j'ai lu récemment sur #AltDevBlogADay un post sur un sujet proche.

Quoi qu'il en soit, aujourd'hui je voulais vous parler des branchements que vous ajoutez dans votre code.

Un petit warning avant de continuer : comprendre ce billet pourra nécessiter de votre part une petite mise à niveau sur certains concepts, et notamment sur l'assembleur x86. Connaître le processus de compilation lié à votre langage sera un plus, et avoir une expérience en lien avec le code assembleur généré par le compilateur va probablement vous aider. Enfin, des connaissances sur l'architecture des processeurs (et notamment sur l'architecture des processeurs x86) va probablement simplifier un peu les détails de ce billet.

Les types de branchements

Au niveau des instruction machine (votre code compilé), il n'existe que deux types de branchements :

  • les branchements inconditionnels, qui permettent d'aller à une adresse de manière systématique. Ces instructions de branchement peuvent être plus ou moins complexes, certaines effectuant des opérations supplémentaires en plus du branchement lui-même. Par exemple, sur un processeur x86, call OPaddr enregistre sur la pile la valeur courante du pointeur d'instruction puis saute à l'adresse spécifiée. Sur un x86, l'instruction de branchement la plus simple est bien évidemment l'instruction de saut jmp OPaddr, qui change la valeur du pointeur d'instruction.
  • les branchements conditionnels, qui sont dépendant d'une information particulière. Dans la grande majorité des cas, ces informations sont récupérées dans le registre de drapeau du microprocesseur. Ce registre spécial est mis à jour par certaines instructions machine. Par exemple, l'instruction de division entière idiv modifie les drapeaux suivants :
    • Drapeau de retenue (CF, carry flag)
    • Drapeau de dépassement (OF, overflow flag)
    • Drapeau de signe (SF, sign flag)
    • Drapeau de zéro (ZF, zero flag)
    • Drapeau d'ajustement (AF, adjust flag ; utilisé en arithmétique BCD)
    • Drapeau de parité (PF, parity flag)

Il existe de nombreuses instructions (lire : en comptant les variations sur la taille des opérandes, il y en a une bonne cinquantaine, voire plus) de branchement conditionnels, et ces branchements dépendent a grande majorité d'un petit nombre de drapeau définis dans ce registre spécial. Par exemple, l'instruction jnz effectue une saut si le drapeau de zéro n'est pas mis, tandis que jge (jump if greater or equal) effectue un saut si le drapeau de signe (SF) est égal au drapeau de dépassement (OF)[1]

Implémentation en C

Le C (et le C++, par extension) offre beaucoup de possibilité pour créer des branchements conditionnels ou non.

Le premier branchement, complètement inconditionnel, est bien évidemment celui représenté par l'instruction goto que tout un chacun a appris à ne pas utiliser[2]. Utiliser goto dans votre code revient purement et simplement à générer une instruction assembleur jmp, qui va demander au processeur d'exécuter les instructions à partir de l'adresse donnée en paramètre (adresse représentée par l'étiquette donnée en paramètre à goto). Ce type de branchement systématique est tout a fait bien traité par votre microprocesseur.

Bien évidemment, c'est souvent le code d'utilisation de goto qui provoque un changement dans le comportement du compilateur. Par exemple, prenons le code suivant :

condition = some_function(argument);
if (!condition)
  goto error;

Un compilateur un peu idiot générerait un code ressemblant à celui-ci (bien évidemment, c'est du pseudo-assembleur) :

  push argument
  call some_function
     ; eax contient la valeur de retour de la fonction
  or earx, eax ; va permettre d'initialiser le registre de flags
     ; en en particulier le bit ZERO qui dit si le résultat d'une
     ; opération arithmétique est un registre vide ou non.
  jnz __label_apres_if
  jmp error
__label_apres_if:
     ; on continue...

Pourquoi un peu idiot ? Tout simplement parce qu'on trouve dans le code deux instructions de branchement consécutives, qui peuvent être remplacées par une seule en inversant le test. Les compilateurs n'étant pas idiot, ils vont générer un code assembleur plus simple avec un seul saut conditionnel.

Ce qui nous amène tout naturellement à considérer les instructions permettant d'implémenter en C des branchements conditionnels.

Il y en a peu - et vous les connaissez toutes :

  • if (expression) instr-list [ else instr-list ] ;
  • do instruction-list while (expression) ;
  • while (expression) instruction-list
  • for ( expression ; expression ; expression ) instruction-list ;
  • switch (expression) switch-body;

Je ne vais pas vous faire l'insulte de vous décrire par le menu ces constructions. Elles servent comme vous le savez à contrôler le flux d'un programme. Je n'ai pas inclus l'opérateur ternaire (expression ? expression : expression) parce que son implémentation ne nécessite pas nécessairement de branchement conditionnel sur les nouvelles générations de processeur x86 (on utilise l'instruction cmov - conditional move - ou setcc - set byte on condition). Attention toutefois : dans certains cas, le compilateur peut avoir besoin d'écrire l'opérateur ternaire sous la forme d'un pseudo-bloc if. Dans ce cas, il est équivalent à l'instruction if.

Le code produit par le compilateur.

Prenons l'implémentation d'une boucle en C, et regardons le code réel généré.

char string = "boucle simple";
int len = strlen(string);
for (int i=0; i<len; ++i) {
  printf("%02x ", (int)stringi);
}

Le code assembleur généré par Visual Studio 2010 en mode Release est le suivant (seule la partie concernant la boucle est montré, pour plus de simplicité):

for (int i=0; i<len; ++i) {
0019104D  xor         esi,esi  
0019104F  test        edi,edi  
00191051  jle         main+76h (191076h)  
00191053  push        ebx  
00191054  mov         ebx,dword ptr __imp__printf (1920A0h)  
0019105A  lea         ebx,ebx  
  printf("%02x ", (int)stringi);
00191060  movsx       ecx,byte ptr ebp+esi-14h  
00191065  push        ecx  
00191066  push        offset string "%02x " (192104h)  
0019106B  call        ebx  
0019106D  inc         esi  
0019106E  add         esp,8  
00191071  cmp         esi,edi  
00191073  jl          main+60h (191060h)  
00191075  pop         ebx  
}

Si on devrait réécrire ce code en pseudo-C, on obtiendrait :

if (i >= len)
  goto __end_of_loop;
__begining_of_loop:
printf("%02x ", (int)stringi);
++i;
if (i < len)
  goto __begining_of_loop;
__end_of_loop:
...

Il y a deux instructions de branchement conditionnel utilisées dans cette boucle : jl (jump if lower) et jgl (jump if lower or equal)). En fait, étant donné que les comparaisons sont toujours entre deux grandeurs dont il faut déterminer l'ordre ou l'égalité, on finira presque toujours par utiliser l'une des instructions suivantes :

  • jz ou jnz (jump is zero ou jump if not zero)
  • jle ou jl
  • jge ou jg

Dans de très rares cas, d'autres instructions vont être utilisées.

Pour une analyse plus fine du code produit par le compilateur, je vous suggère de lire l'article de Alex Darby, C / C++ Low Level Curriculum Part 6: Conditionals.

Revenons à nos moutons. Fait étrange, alors que nous ne présentons en fait dans le code source qu'une seule possibilité de branchement, on voit que le compilateur en ajoute une autre. Il aurait pu se satisfaire d'un seul test - le premier, puisqu'il est nécessaire afin d'éviter de rentrer dans la boucle si la condition est fausse dès le départ. Autrement dit, le compilateur aurait pu écrire quelque chose ressemblant à :

__begining_of_loop:
if (i >= len)
  goto __end_of_loop;
printf("%02x ", (int)stringi);
++i;
goto __begining_of_loop;
__end_of_loop:
...

Pourquoi diable a-t-il rajouté cette seconde instruction de branchement conditionnel ? La seule raison plausible, c'est qu'il a tenté d'optimiser quelque chose. OK, mais alors : quoi et pourquoi ? Pour répondre à cette question, il va falloir descendre d'un niveau supplémentaire.

Ce qui se passe au niveau du silicon

Le microprocesseur, lorsqu'il exécute le code machine correspondant, va commencer par charger son cache code (une mémoire cache particulière où il stocke le code à déchiffrer). Il va ensuite lire une instruction à partir de ce cache code, et la décoder - ce qui va lui donner le chemin à suivre au niveau de ses portes logiques pour exécuter cette instruction. Pendant qu'il la décode, il va en lire une autre, puis va décoder cette dernière. La première instruction lue aura été décodée à ce moment, et l'exécution pourra commencer. Ce comportement est possible car les microprocesseurs actuels ont ce qu'on appelle un pipeline à plusieurs étages. Lorsqu'une instruction entre dans le pipeline, d'autres instructions ont déjà été décodées et certaines, encore présentes dans le pipeline, sont en cours d'exécution. Selon la rapidité d'exécution d'une instruction, on peut ainsi se retrouver avec un nombre conséquent d'instruction qui sont déjà en cours de traitement par le microprocesseur.

Supposons que l'instruction qui vient d'entrer dans le pipeline soit une instruction de saut, et que l'instruction en cours d'exécution soit relativement longue à s'exécuter. Dans ce cas, on va décoder l'instruction de saut conditionnel, s’apercevoir qu'il s'agit d'une instruction de saut conditionnel, mais impossible de savoir quel code va s'exécuter ensuite tant qu'on a pas encore exécuter l'instruction. Dès lors, comment savoir quelle est l'instruction qui doit être lue par la suite ?

Il y a deux solutions pour régler le problème. La première est de ne rien faire. Lorsqu'on commence à exécuter l'instruction, on vide le pipeline - histoire de le nettoyer - et on recommence à le remplir une fois qu'on connait l'adresse de la prochaine instruction à exécuter. Le problème évident avec cette méthode, c'est qu'on perd une bonne partie de l'intérêt du pipeline dès qu'on doit traiter une instruction de saut.

La seconde manière de procéder est de considérer qu'un des deux chemins possibles (le moins coûteux pour le processeur) est le bon. Dans le cas où on se serait trompé, on retombe sur la première solution : on vide le pipeline, et on ne recommence à le remplir que lorsqu'on connait l'adresse de l'instruction suivante. C'est bien évidemment la solution préférée sur les architectures x86 actuelle, pour une simple raison : elle ne coûte pas plus cher à implémenter dans le silicone que la première méthode, et offre des résultats spectaculaires dès lors que le pipeline est suffisamment long (ce qui est bien évidemment le cas depuis bien, bien longtemps sur la famille x86). On appelle cette manière de procéder de la prédiction de branchement.

Algorithme de prédiction de branchement

Comme toute prédiction, il arrive qu'on se trompe. C'est d'autant plus fréquent dans ce cas précis qu'il nous faut composer avec des règles strictes. Une prédiction intelligente est possible, mais elle complexifie de manière notable le silicone des microprocesseurs, et la complexité est ennemie de la vitesse. Il y a un juste milieu à trouver pour réduire les coûts de production, avoir un silicone simple, et offrir une prédiction qui marche suffisamment bien pour être utilisable.

L'approche utilisée par Intel est la plus simple possible : la prédiction suit un ensemble de règles statiques. C'est au programmeur (ou, lorsque c'est possible, au programmeur) d'adapter son code pour qu'il tire partie de ces règles.

  • on prédit que les branchements inconditionnels seront pris.
  • on prédit que les branchements conditionnels vers l'arrière seront pris.
  • on prédit que les branchements conditionnels vers l'avant ne seront PAS pris.

Pour simplifier, si le saut se fait de manière inconditionnelle ou vers l'arrière, on va les prédire correctement. S'ils se font vers l'avant, on ne vas pas les prédire correctement - c'est ce qu'on appelle un branch misprediction.

Ces règles sont raisonnable, dans le sens où elle permettent au processeur de s'assurer que dans la grande majorité des cas, il n'aura pas besoin de modifier son cache code - le code vers l'arrière a de bonnes chances d'être encore présent, tandis que le code vers l'avant a des chances de ne pas l'être encore. C'est un petit gain supplémentaire, mais il n'est pas inintéressant.

L'algorithme a été complexifié un peu pour prédire correctement les branchements qui ont déjà été pris récemment - la mauvaise prédiction est garanti n'arriver qu'une seule fois si le code séparant deux exécutions est relativement proche (et dans le cas contraire, il y a de bonnes chances que ce code soit peu critique).

Le coût d'une mauvaise prédiction de branche est prohibitif. Dans le cas de code critique, ce coût doit être pris en compte par le programmeur, sans quoi il risque d'observer un comportement qui ne lui plaira pas du tout.

Prenons par exemple le code suivant :

for (i=0; i<100000; ++i) {
  if (i & 1) {
   // impair : 
   do_something_specific();
  }
  // tous
  generic_handling();
}

Le test à l'intérieur de la boucle ne peut pas être prédit correctement - jamais. Le saut qui sera généré par le compilateur est nécessairement un saut conditionnel vers l'avant - donc à la première exécution, il ne sera pas prédit correctement : le processeur aura voulu le faire aller vers impair alors qu'il lui fait prendre le saut. A la seconde exécution, il sera prédit comme devant aller vers tous, mais il faut en fait ne pas prendre le saut, et aller vers impair. A la troisième exécution, il aura compris qu'il fait allers vers impair, mais encore une fois, on voudra le faire sauter vers tous.

En fait, c'est là le pire cas que l'algorithme de prédiction de branchement peut trouver : un cas ou cet algorithme se trompera systématiquement. Le résultat est que cette boucle est très coûteuse, et qu'elle est peut-être un bon candidat pour la réécriture si elle est critique (dans ce cas précis, il est préférable de séparer la boucle en deux : une boucle qui traite les nombres impairs, et une boucle qui traite ensuite tous les nombres).

Le compilateur travaille

Revenons à notre boucle de la section précédente. Nous avons vu que là où nous pensions n'avoir qu'un seul saut conditionnel, nous en avons en fait deux. Le premier est un saut conditionnel vers l'avant, qui sera prédit comme n'étant pas pris. C'est vrai dans l'immense majorité des cas - lorsqu'on commence une boucle, il y a de grandes chances pour que la boucle soit exécutée au moins une fois. Le second branchement conditionnel est vers l'arrière. On prédit qu'il sera pris, ce qui est vrai jusqu'à la dernière itération. Quel que soit le nombre d'itération, le compilateur a généré un code qui minimise au mieux les mauvaises prédictions de branchement : dans ce cas précis, il y en une seule, quel que soit le cas considéré.

De manière générale, un compilateur va toujours essayer d'écrire du code qui collera le mieux possible aux manuels proposés par le fondeur de microprocesseur. C'est d'autant plus vrai avec Intel, lorsque ceux ci proposent un accès gratuit au manuel d'optimisation de leurs processeurs (manuels qui fait aux alentours de 500 pages, voire plus, et qui regorge d'informations destinées spécifiquement aux vendeurs de compilateurs).

Le compilateur travaille, et il le fait bien. Dans l'immense majorité des cas, il fera un meilleur travail de micro-optimisation que vous - c'est normal : la micro-optimisation, c'est une grande partie de son boulot.

Cependant, il y a des cas où le compilateur ne sait pas faire. Prenons un cas simple et très courant :

int my_function(my_type_t *p)
{
   if (!p) return -1;
   ...
}

Deux solutions : soit p est souvent NULL, soit p est rarement NULL. Dans les deux cas, le compilateur a tout intérêt à faire en sorte que le saut conditionnel vers l'avant soit réservé au cas qui se produit le moins souvent. Mais comment savoir lequel est le plus fréquent ?

Les compilateurs Microsoft n'offrent pas de solutions pratiques à ce problème. Il est toutefois possible de faire ce qu'on appelle une passe d'optimisation guidée, un processus complexe qui consiste à :

  • exécuter un code instrumentalisé et non optimisé
  • en fonction des rapports obtenus, ajuster les informations destinées à l'optimiseur
  • générer le code optimisé

Ce processus est relativement coûteux au cours du développement, et est en principe réservé aux itérations finale du développement. Du coup, il est difficile d'en prévoir le résultat. On sait qu'on va gagner quelque chose, mais impossible de savoir à l'avance ce qui sera optimisé.

La solution la plus pragmatique consiste pour le programmeur à prendre cette problématique en compte. Selon ce que le programmeur sait du contexte autour de sont propre code, il sera à même de décider quel est le chemin le plus probable, et en fonction de cette connaissance, écrire le code de manière à diriger au mieux le processus de compilation. Pour simplifier : il faut écrire les tests sous une forme préférentielle - celle où le résultat est !0 avec la plus grande probabilité.

Il y a un problème avec cette approche, car elle mène souvent le programmeur à écrire un code qui n'est pas naturel à la lecture. Malheureusement, les outils de MIcrosoft ne proposent aucune solution à ce problème particulier. Mais les outils MS ne sont pas les seuls du marché, loin de là.

Le compilateur libre gcc propose une fonction intrinsèque __builtin_expect(cond, expect) qui, correctement utilisée, change le comportement du compilateur vis à vis de la génération du code lié aux branchements conditionnels[3]. De manière simplifiée, la fonction dis au compilateur "il y a de grandes chances que le test soit vrai" ou "il y a de grandes chances que le test soit faux". Cette information permet au compilateur de choisir de réorganiser le code de manière a maximiser les chances de bonne prédiction sur ces branchements.

Cette fonction intrinsèque est très régulièrement employée dans le code du kernel linux, cachée par deux #define au nom évocateur : likely() et unlikely().

Conclusion

Une remarque pour terminer cet article : les outils présentés ici doivent être utilisés en connaissance de cause. Dans un premier temps, il est important d'écrire le code de manière à ce qu'il fonctionne correctement. L'utilisation, si nécessaire, d'outils spécifiques dont le but est d'assurer une meilleur prédiction des branchements conditionnels et du second ordre (et même d'un ordre encore plus lointain, tant on s'approche là d'une problématique de micro-optimisation). En fait, les cas où un contrôle de l'algorithme de prédiction du CPU a un intérêt sont peu nombreux, et cela pour deux raisons :

  • le première, parce que le compilateur essaie déjà de faire au mieux, en fonction de ce qu'il sait.
  • la seconde, parce que le gain, même s'il est tangible sur des fonctions importantes, n'est pas nécessairement visible : il va aussi dépendre de tout ce qui est fait à coté.

Mais dans les cas où ce contrôle a un intérêt, il peut faire gagner de très précieux cycles d'autant plus gratuits qu'il ne s'agit dans la plupart des cas que de réorganiser le code, sans pour autant changer l'algorithme - et dans le cas d'une utilisation de gcc, c'est même complètement gratuit à ce niveau grâce à __buitint_expect().

Notes

[1] pour plus d'informations, lire les manuels Intel correspondants ; l'explication de ce comportement y est donnée.

[2] enfin, tous, sauf moi, visiblement. Un grep sur mon code récent en montre une bonne dizaine. Mais bon : j'ai mes raisons...

[3] pour plus d'information, voir l'aide officielle de GNU CC

Ajouter un commentaire

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

Fil des commentaires de ce billet