Retrouvez cet article dans : Linux Magazine 91

Programmer est un art, surtout en C où d’innombrables facteurs interviennent : le processeur, l’algorithme à exécuter, le compilateur, l’environnement logiciel... Voici quelques techniques illustrées qui vous permettront de comprendre mon style de codage très particulier.

Malgré leur sophistication théorique, les bouts de code que j’écris tournent souvent autour de traitements itératifs très simples sur un petit tableau. L’impératif de vitesse oblige à utiliser des formes de codage particulières, qui permettent d’améliorer l’efficacité du code généré par le compilateur. Ces techniques vont peut-être à l’encontre du style établi, mais évitent d’avoir recours au langage assembleur, ce qui augmente la portabilité des logiciels.

1. GCC et ses petites manies

Commençons par un code d’exemple inutile (il est évident qu’il ne sert à rien en l’état), mais qui illustre très bien le propos, car de nombreux ingrédients typiques sont réunis :

int fonction_stupide(int x) {
  int table[4];
  int i, j=0;
  /* initialisation */
  for (i=0; i<4; i++) {
    table[i]=x+i+1;
  }
  do {  /* Boucle dans le vide */
    for (i=0; i<4; i++) {
      j^=table[i]; /* une opération simple quelconque */
    }
  } while (x--);
  return j;
}

La remarque la plus importante est qu’il est devenu compliqué, avec les raffinements progressifs de GCC, de lui faire générer du code inutile, car ce dernier est simplement supprimé par l’optimiseur. A part cela, le code source ne suscite aucun commentaire, sauf si on le regarde sous l’angle de l’efficacité. Voici du code généré par gcc 3.3.4 :

; Code assembleur lourd et disgrâcieux généré
; par "gcc -S exemple.c". Attention : ne pas le montrer
; à des cardiaques ou à des mineurs de moins de 25 ans
fonction_stupide:
; Prologue
	pushl	%ebp       ; sauve la trame précédente
	movl	%esp, %ebp
        ; puis alloue 40 octets pour la trame
	subl	$40, %esp

	movl	$0, -32(%ebp)  ; j=0
	movl	$0, -28(%ebp)  ; i=0
; Exemple de boucle pas du tout optimisée :
.L2:
        ; si i<3, aller à L5 sinon aller à L3
	cmpl	$3, -28(%ebp)
	jle	.L5
	jmp	.L3 ; nb: inverser la condition
                    ; aurait économisé une 
                    ; instruction et un saut
.L5:
	movl	-28(%ebp), %edx ; edx=i
	movl	-28(%ebp), %eax ; eax=i  (pourquoi dupliquer ?)
	addl	8(%ebp), %eax   ; eax+=x (paramètre sur la pile)
	incl	%eax            ; eax++
	movl	%eax, -24(%ebp,%edx,4)  ; tableau[i]=i+x+1
	leal	-28(%ebp), %eax
	incl	(%eax)       ; i++
        /* fin du corps de la boucle d’initialisation */
	jmp	.L2
.L3:
	nop        /* là, ne fait vraiment rien :-/ */
.L6:
	movl	$0, -28(%ebp)   /* i=0 */
/* Boucle à structure aussi moche que la première : */
.L9:
	cmpl	$3, -28(%ebp)
	jle	.L12
	jmp	.L8
.L12:
	movl	-28(%ebp), %eax         ; eax=i
	movl	-24(%ebp,%eax,4), %edx  ; edx=&tableau[i]
	leal	-32(%ebp), %eax  ; eax=&j
	xorl	%edx, (%eax)     ; *eac^=edx : j^=tableau[i]
	leal	-28(%ebp), %eax  ; eax=&i
	incl	(%eax)           ; i++
	jmp	.L9  ; fin du corps de la boucle,
                   ; retourne à la structure de décision
.L8:
	decl	8(%ebp)  ; x-- (dans le while)
	cmpl	$-1, 8(%ebp)
	jne	.L6      ; si x>=0, reboucle encore une fois
	movl	-32(%ebp), %eax  ; return j (dans eax)
; épilogue :
	leave      ; restaure la trame de pile précédente
	ret        ; fin de la fonction 

Les instructions font appel à la pile, ce qui les alourdit (en particulier sur x86). Chaque référence à une variable sur la pile coûte le calcul d’une adresse (parfois complexe) et un accès à la mémoire. Mais surtout, la pile est pointée par le pointeur de trame (ebp) et lui-même doit être initialisé et restauré au début et à la fin de la fonction (les fameux prologues et épilogues). Pourtant, ebp n’est pas réservé uniquement à cet usage et pourrait servir à autre chose (pour les calculs, donc) si on le libérait. Et comme ebp est calculé à partir de esp (le pointeur de pile) qui n’est pas utilisé, on perd vraiment un registre !

2. Il suffit pourtant de demander gentiment

Si on utilise un nombre limité de variables locales, dans le cadre d’une boucle déroulée, le compilateur associera un registre à chaque variable, ce qui élimine d’un coup toute question d’adressage. Pour cela, il faut faire appel à des options de compilation spéciales :

gcc -Os -fomit-frame-pointer -momit-leaf-frame-pointer \
-march=pentium3 exemple.c

Le plus important est -Os qui permet l’accès à d’autres registres inutilisés auparavant (sur x86, qui concerne la majorité des lecteurs) : ebx, ecx, edi, esi. Si on ajoute eax, edx et ebp, nous pouvons maintenant faire tenir 7 variables dans le cœur du processeur et y accéder instantanément.
Dans du code déroulé, les inférences de valeurs permettent encore de réduire le nombre d’instructions exécutées. Le code généré reste habituellement plus long, mais son exécution est beaucoup plus rapide ! Voici un exemple de code C fonctionnellement identique au précédent, mais plus efficace :

 int fonction_stupide_un_peu_plus_rapide(int x) {
  int j=0,
    table1=x+1, table2=x+2, table3=x+3, table4=x+4;
  do {
    j ^= table1^table2^table3^table4;
  } while (x--);
  return j;
}

Combiné avec les options de compilation décrites plus haut, le code est non seulement plus rapide, mais paradoxalement aussi plus court, malgré le prologue et l’épilogue plus longs, ceci grâce aux nombreux calculs d’adresses économisés :

; Code assembleur assez bon, généré par
; gcc -Os -fomit-frame-pointer -momit-leaf-frame-pointer
;       -march=pentium3 -S exemple.c

fonction_stupide_un_peu_plus_rapide:
; Prologue : empile/sauve ebp, edi, esi et ebx
	pushl	%ebp
	xorl	%ecx, %ecx ; ecx=j=0
	pushl	%edi
	pushl	%esi
	pushl	%ebx
; Initialisation :
	movl	20(%esp), %edx ; edx=x
	leal	1(%edx), %ebp  ; ebp=x+1=tableau1
	leal	2(%edx), %edi  ; edi=x+2=tableau2
	leal	3(%edx), %esi  ; esi=x+3=tableau3
	leal	4(%edx), %ebx  ; ebx=x+4=tableau4
; Boucle principale :
.L20:
	movl	%ebp, %eax
	decl	%edx	; x-- (dans le while)
	xorl	%edi, %eax  ; eax=tableau1^tableau2
	xorl	%esi, %eax  ; eax^=tableau3
	xorl	%ebx, %eax  ; eax^=tableau4
	xorl	%eax, %ecx  ; j^=table1^table2^table3^table4;
	cmpl	$-1, %edx
	jne	.L20    ; reboucle si x>=0
; Epilogue : dépile tous les registres sauvés
	popl	%ebx
	movl	%ecx, %eax ; retourne j dans eax
	popl	%esi
	popl	%edi
	popl	%ebp
	ret

Le seul point qui peut être encore optimisé est l’utilisation de eax comme variable temporaire dans la boucle. Le xor peut être réalisé directement avec ecx (j) grâce à la propriété de commutativité (ce que le compilateur ignore). Une écriture différente du code source remédie à cela, ce qui libère un registre qui peut maintenant être associé à une variable supplémentaire (ici, on augmente la taille du tableau).

int autre_fonction_stupide(int x) {
  int j=0,
    table1=x+1, table2=x+2, table3=x+3,
    table4=x+4, table5=x+5;
  do {
    j^=table1;
    j^=table2;
    j^=table3;
    j^=table4;
    j^=table5;
  } while (x--);
  return j;
}

Le code final contient 7 variables (table, j et x) et tient entièrement dans les 7 registres d’un x86, ce qui le rend à la fois rapide et concis.

3. Recommandations

Nous en déduisons les conseils suivants, qui ne sont pas spécifiques aux processeurs x86 :

• Ne pas hésiter à aller fouiner dans la sortie du compilateur et dans les nombreuses ressources fournies aux développeurs. On économise parfois un ticket de cinéma pour le dernier film d’horreur, tout en améliorant la qualité du code source.
• En général, la stratégie consiste à écrire du code C qui peut être traduit directement en langage machine, en réduisant l’abstraction et en explicitant les formats ou les structures. Il faut qu’il y ait une correspondance directe entre ce qu’on demande au processeur et ses instructions. Pour que cela soit efficace, il faut bien connaître la machine cible et ce qu’elle fait le mieux. Cela se limite souvent aux quelques fonctions de base disponibles, telles que l’addition, la soustraction et quelques autres fonctions logiques, mais cela varie énormément d’une machine à l’autre !
• Le premier examen du travail de GCC sans optimisation montre à quel point la gestion des boucles peut être déficiente. Pour la plupart des boucles simples, je privilégie la structure init; do {X; inc;} while (cond) qui est équivalente à for (init;cond;inc) {X}. La gestion des variables est manuelle, ce qui réduit un peu la lisibilité, mais la traduction manuelle en code assembleur est directe, surtout si la condition de rebouclage est réduite à un test de base (variable égale à zéro ou négative).
• Si le corps de la boucle devait être sauté (condition initialement invalide), un simple if (cond) {do {X} while (cond)} suffit, évitant d’avoir à utiliser la forme while (cond) {X}, équivalente mais traduite de manière un peu plus complexe. La duplication du test dans if (cond) peut être encombrante, mais cela pose rarement un souci.
• Sur x86 et autres architectures à deux adresses, découper les expressions complexes et utiliser la syntaxe à deux adresses. Comme cette syntaxe se traduit souvent directement en une instruction, cela réduit la pression sur l’allocation des registres (lorsque c’est correctement utilisé).

a = a + b; /* syntaxe classique */
a += b;    /* syntaxe à deux adresses */

• Ne pas hésiter à forcer l’ordre des opérations. Le compilateur obéira souvent sans discuter (mais il faut le vérifier dans le code généré) et cela peut débloquer quelques situations tendues (comme nous venons de le voir).
  Le compilateur ne tentera pas d’exploiter des propriétés comme la commutativité ou la distributivité des opérateurs, car le standard du langage C exige de conserver l’ordre des opérations. C’est parfois capital pour les entiers, à cause d’éventuels dépassements de capacité sur des variables temporaires, mais c’est surtout critique pour les nombres à virgule flottante, car le résultat dépend de l’ordre des opérandes.
• Un petit tableau est réalisé à partir de variables scalaires locales pour que le compilateur puisse assigner chaque entrée à un registre et ainsi minimiser les mouvements de données et les accès à la mémoire.
• Autant que possible, utiliser des variables statiques globales (déclarées hors de la fonction). D’une part, cela réduit au minimum l’occupation de la pile, ce qui peut même éviter d’y accéder complètement dans le meilleur des cas, donc de modifier des pointeurs (avec l’option -fomit-frame-pointer de GCC). D’autre part, les modes d’adressage complexes sont plus lents à décoder (sur x86) ou longs à coder (avec les processeurs RISC). Dans un programme, le mieux est d’utiliser uniquement un registre pointeur avec éventuellement un déplacement (offset) constant. Par exemple :

int t[1337];
int *p=&t;  /* création d’un alias */
int h=t[0]  =*p;      /* OK, accès direct par pointeur */
int i=t[10] =*(p+10); /* OK, un pointeur plus un offset constant */
int j=t[i]  =*(p+i);  /* Délicat, offset non constant, donc
                      mode d’adressage un peu moins rapide */
int k=t[i*281] /* Encore pire, il faut calculer l’offset */

On comprend alors l’intérêt de mettre des variables en global (sauf si la fonction doit être récursive ou réentrante) : une variable globale a une adresse constante (donc adressée directement), alors qu’une variable sur la pile est accédée au travers du pointeur de pile (esp) ou du pointeur de trame (ebp), cette indirection peut ralentir les accès. Attention : ce n’est pas une science exacte, mais une indication de l’effort que le microprocesseur devra fournir.

• En conséquence, si une variable n’est pas accédée souvent, il faut la mettre dans une variable globale. Cela empêche le compilateur de l’associer à un registre, ce qui laisse plus de place pour les autres variables locales. Et comme l’accès est presque immédiat grâce à l’adressage direct, le surcoût est minimal.
• La boucle est déroulée autant de fois qu’il y a de registres. Cela réduit l’importance relative du comptage des itérations (libérant alors un registre qui aurait servi comme compteur de boucle) et permet de nombreuses autres simplifications par inférences de valeur entre plusieurs itérations. Dans le code d’exemple, cela revient à donner directement la valeur au lieu de la recalculer à chaque ligne.
• L’opération, même peu complexe, est codée dans une macro, qui réduit la taille du code source et les chances d’erreurs de copier-coller-modifier. Je ne le répèterai pas assez : les macros sont destinées à nous faciliter la vie, il faut en profiter ! Dans le passé, j’ai perdu un temps incroyable à vouloir tout faire à la main... Le développement est ralenti, et le débogage peut devenir absolument impossible !
• Les paramètres de la macro incluent les indices du tableau à accéder. Comme les indices sont codés en dur au moment de la compilation, le processeur ne perd plus un cycle à les calculer lors de l’exécution, ce qui est bienvenu lors d’accès circulaires par exemple.

L'optimisation du code doit se faire impérativement APRES étude du meilleur algorithme. N'utilisez pas les conseils donnés ici comme des règles de développement.

4. Ordonnancement des instructions

Il n’est pas possible d’exposer toutes les techniques d’optimisation existantes, mais je dois encore évoquer un dernier point important : l’ordre des instructions dans un programme et leur réordonnancement dynamique dans les processeurs à exécution dans le désordre (Out Of Order, ou OOO, mais rien à voir avec OpenOffice.Org). Cela concerne les Pentium2/3/4, la lignée des PowerPC ou les Alpha21264 (EV6 et plus).
Les processeurs superscalaires des générations précédentes (tels les premiers Pentium, MIPS, SPARC ou Alpha21164) demandent au compilateur de fabriquer un flux d’instructions finement calibré, capable d’utiliser au mieux les ressources cycle par cycle, avec des règles parfois complexes et contradictoires (ah ! l’optimisation pour le PentiumMMX...). Par contre, les processeurs OOO peuvent exécuter un certain nombre d’instructions sans attendre le résultat des précédentes, s’il n’y a pas de dépendances entre elles. Ces processeurs sont bien plus complexes, mais les gains de temps sont substantiels dans certaines circonstances, en particulier pour compenser la latence des accès à la mémoire.
Afin d’améliorer un programme, nous pouvons par exemple déplacer (anticiper) une opération jusqu’à 20 instructions à l’avance (selon le processeur et en fonction de la latence). Typiquement, une instruction de lecture en mémoire nécessite plusieurs cycles pour fournir un résultat, lorsque la donnée est déjà en mémoire cache, et le processeur est arrêté pendant des dizaines de cycles s’il faut chercher la donnée en mémoire dynamique externe. Il est donc désirable de reporter les opérations de lecture le plus en amont possible, en fonction des instructions indépendantes que nous pouvons intercaler :

int a, b, c, d, i, tableau[];
/* code initial : */
 a = tableau[i]+(b*c);
/* code réorganisé */

Note :
Typiquement, un processeur OOO est constitué de plusieurs parties découplées, effectuant leur travail indépendamment, afin de maximiser le parallélisme et de réduire le temps de traitement total.

• La fenêtre d’instructions est une mémoire qui communique avec toutes les autres unités du processeur. Elle a une capacité de quelques dizaines de cellules qui contiennent une version modifiée des instructions décodées. Chaque cellule est aussi marquée pour indiquer son état courant : (a) pas d’instruction, (b) instruction décodée en attente d’exécution, (c) en cours d’exécution, ou (d) exécutée.
• Les registres renommés sont une autre mémoire, contenant les valeurs temporaires (ou spéculatives) des registres normaux. En plus de la valeur courante, chaque registre renommé indique à quel registre normal sa valeur correspond, et s’il est occupé ou libre.
• Le décodeur d’instructions analyse et traduit le flux du programme. Chaque instruction est décomposée en plusieurs parties, ou champs : l’opération à effectuer (addition, multiplication, lecture de la mémoire...), le registre destination (qui contiendra le résultat de l’opération) et les registres sources (les opérandes qui doivent être lues).
  Lorsque le décodeur ajoute une instruction dans la fenêtre, il traduit les numéros des registres, ou les renomme : il alloue un nouveau registre renommé pour la destination, et cherche à quels autres registres renommés correspondent les registres sources. Il utilise une table spéciale pour effectuer ces traductions, qui servira plus tard lors de la validation de l’instruction.
• Les unités d’exécution se chargent d’effectuer les opérations telles que l’écriture ou la lecture en mémoire, les calculs sur les nombres entiers ou flottants... Chaque unité, lorsqu’elle n’est pas bloquée par des opérations en cours, scrute la fenêtre d’instructions, à la recherche d’opérations qu’elle est capable d’effectuer (par exemple, l’ALU va chercher uniquement les instructions arithmétiques ou logiques). Il faut aussi vérifier que les opérandes sont prêtes (déjà calculées et disponibles).
  Si toutes les conditions sont remplies, les opérandes sont lues dans les registres renommés, l’opération est effectuée, puis le résultat est écrit dans le registre renommé (déjà alloué lors du décodage). Toutes ces opérations nécessitent un nombre variable de cycles, que l’on appelle la latence.
  * L’unité de validation (pour les processeurs Intel, aussi appelée retrait ou commit). Certains processeurs mettent à jour directement la table de traduction des registres, lorsque le résultat est écrit dans les registres renommés. Pour les processeurs PentiumPro et leurs héritiers (Pentium 2 et 3), une unité spéciale se charge de nettoyer la fenêtre d’instructions, de synchroniser toutes les tables et d’assurer que les instructions soient validées dans l’ordre initial du programme.
  Ainsi, le résultat d’une opération peut être prêt avant qu’une instruction qui la précède ne soit terminée.

 Figure 1 : Structure typique d’un processeur à exécution dans le désordre

 a = tableau[i]; /* cette instruction prend du temps */
 d = b * c;  /* la multiplication est assez longue, aussi. */
 /* insérer ici une bonne douzaine d’instructions
 qui n’ont rien à voir, pendant que la multiplication et
 la lecture s’effectuent en parallèle. */
 a += d; /* a et d sont utilisés ici sans blocage */

5. Le bon côté du renommage des registres

Comme un processeur OOO exécute les opérations lorsque les données sont prêtes, indépendamment de leur ordre dans le programme, on peut traiter un programme par petits blocs indépendants de 3 à 10 opérations.
Les processeurs OOO apportent un certain confort lors du codage : le renommage dynamique des registres rend possible la réutilisation à outrance des variables, pour des usages simultanés et différents. C’est critique pour les processeurs x86 qui, nous l’avons vu au début de l’article, manquent cruellement de registres. Depuis le PentiumPro, cette limitation peut être outrepassée dans une certaine mesure.
Si vous avez suivi l’explication du cadre, un nouveau registre renommé est alloué pour contenir le résultat de chaque opération. En termes de code source, cela s’exprime par :

int a, b;
/* code source */
a += b;
/* ce que le processeur effectuera vraiment : */
a’ = a + b;

La variable a’ n’existe qu’à l’intérieur du processeur et n’a pas besoin d’être déclarée dans le code source. a’ deviendra a lorsque cette dernière sera lue, mais, pendant une période de quelques cycles, les deux cohabitent !
A chaque réécriture du registre, son usage change. Ainsi, si on utilise a plusieurs fois consécutivement, le processeur va effectuer chaque opération en parallèle, sur des versions différentes et simultanées de la variable. Par exemple, imaginons un morceau de code appelant memcpy() pour recopier un petit bloc de données.

int *a, *b, t;
/* code initial */
memcpy(b,a,32);
/* code déroulé manuellement */
t=a[0]; b[0]=t;
t=a[1]; b[1]=t;
t=a[2]; b[2]=t;
t=a[3]; b[3]=t;
t=a[4]; b[4]=t;
t=a[5]; b[5]=t;
t=a[6]; b[6]=t;
t=a[7]; b[7]=t;

Le code déroulé n’utilise que trois registres, mais t pourra exister en huit versions simultanées différentes. Un processeur RISC classique (sans renommage) nécessiterait par contre l’allocation de 4 ou 8 registres différents pour exécuter ce code sans peine.
Mais ce code est assez brutal : il va saturer l’unité d’accès à la mémoire et n’apporte rien par rapport au memcpy() initial. Cette fonction, même inlinée, est bloquante, car elle ne permet pas à d’autres instructions de s’exécuter en même temps.
Par contre, dans la version déroulée, nous pouvons entrelacer des instructions indépendantes, ou commencer à effectuer des calculs avec certaines valeurs de la table recopiée, dès que celles-ci sont lues et disponibles dans t. Ainsi peut s’opérer la magie : l’unité d’accès à la mémoire tout comme les unités de calcul peuvent tourner à plein régime en même temps, ce qui réduit le temps d’exécution du morceau de code.

int a[], b[], m, n, o, t, u;
/* code de recopie, "saupoudré" d’opérations */
t=a[0]; b[0]=t;
u=a[1]; b[1]=u;
m=t;
m+=u;
t=a[2]; b[2]=t;
u=a[3]; b[3]=u;
n=t;
n+=u;
m+=n;
t=a[4]; b[4]=t;
u=a[5]; b[5]=u;
o=t;
o+=u;
t=a[6]; b[6]=t;
u=a[7]; b[7]=u;
n=t;
n+=u;
n+=o;
m+=n;

Le code ci-dessus n’est probablement pas le meilleur code possible, mais il illustre bien l’avantage d’un cœur à exécution dans le désordre. La somme de toutes les données est effectuée au moyen d’un arbre binaire, en utilisant juste 5 variables alors que 15 valeurs différentes sont traitées. De plus, si une lecture prend plus de temps que les autres (à cause d’un cache miss), toutes les autres sommes intermédiaires peuvent être calculées sans blocage.
Du point de vue du programmeur de haut niveau, il est intéressant de noter que la granularité du saupoudrage ou l’entrelacement n’est pas critique. On peut entrelacer des blocs d’une, deux, trois ou quatre opérations, puisque le cœur va les réorganiser lui-même. On peut ainsi coder par petits blocs logiques, sans se creuser la tête pour tout bien répartir. Au contraire, les processeurs superscalaires classiques nécessitent une compréhension fine du fonctionnement des pipelines et le code a souvent tendance à devenir absolument incompréhensible.

Conclusion

Je n’ai abordé ici que quelques aspects, qui sont spécifiques aux morceaux de code que je publie dans ce magazine. Comme les sources doivent être portables et fonctionner au mieux sur une grande variété de processeurs, je me cantonne à des techniques de haut niveau, avec un minimum d’hypothèses sur la plate-forme et en considérant le cas le plus défavorable (ce qui revient à viser les x86).
Il faut aussi remarquer que ces techniques s’appliquent surtout à des fonctions terminales (ou leaf en anglais), qui n’appellent pas d’autre fonction. On peut ainsi utiliser des variables globales réservées, puisqu’elles ne seront pas surécrites par une autre instance de la même fonction, en plein milieu de leur exécution. Mais dans le cadre d’un programme multithread, ce manque de réentrance peut devenir catastrophique.

Enfin, n’oubliez pas de toujours mesurer l’effet d’un changement dans votre code : une modification anodine réserve souvent des mauvaises surprises et une optimisation sophistiquée n’est pas une garantie d’accélération.

Lien

• D’autres techniques ont été exposées dans l’article " Hacks en C " de Nicolas Boulay (GLMF n°32).

   Retrouvez cet article dans : Linux Magazine 91