Dupliquer c'est optimiser

Après presque un an de silence, il est grand temps pour moi de tenir mes promesses et de continuer ce que j’avais commencé pour démystifier ce qu’il se passe à l’intérieur d’un compilateur qui optimise le code qu’il reçoit. Jusqu’ici, toutes les techniques que nous avons vues avaient pour but de tailler dans la masse de code pour enlever et factoriser tout ce qui est redondant ou superflu : polymorphisme et factorisation de code dans les langages de haut niveau, élimination de code inutile. Mais de manière contre-intuitive, il est souvent nécessaire de faire exactement le contraire pour que le code s’exécute plus vite sur la machine.

Le coût de l’abstraction

Pour comprendre pourquoi, il faut se rappeler une des leçons de la gestion de la mémoire : les abstractions, très utiles pour programmer à plus haut niveau, viennent toujours au prix d’une efficacité moindre. Et cette règle s’applique également au concept même de fonction, qui est une abstraction n’existant pas en assembleur. Prenons un exemple concret d’un petit programme C qui calcule la somme des \(n\) premiers nombres, où \(n\) est donné par l’utilisateur à l’exécution du programme.

int incr(int sum, int i) {
        return sum + i;
}

int main(int argc, char* argv[]) {
        int n = atoi(argv[0]);
        int sum = 0;
        for(int i=0;i<n;i++) {
                sum = incr(sum,i);
        }
        return sum;
}

Voilà comment est compilée la fonction incr en assembleur Intel par le compilateur gcc au niveau d’optimisation -O1:

0000000000400596 <incr>:
400596:	8d 04 37             	lea    (%rdi,%rsi,1),%eax
400599:	c3                   	retq

On peut se rappeler comment lire ce bout de code en lisant le post concernant l’assembleur. On voit que la fonction est extrêmement petite, et que l’addition est faite avec une seule instruction. Cependant, voilà ce que donne l’assembleur du corps de la boucle:

4005dc:	89 de                	mov    %ebx,%esi
4005de:	89 c7                	mov    %eax,%edi
4005e0:	e8 b1 ff ff ff       	callq  400596 <incr>
4005e5:	83 c3 01             	add    $0x1,%ebx
4005e8:	39 eb                	cmp    %ebp,%ebx
4005ea:	75 f0                	jne    4005dc <main+0x42>

Si les trois dernières instructions (add, cmp et jne) servent à faire la boucle for, on voit que l’appel de la fonction incr prend trois instructions à lui tout seul ! D’autant plus que les instructions call et ret en cachent en fait deux : un accès mémoire pour stocker et récupérer l’adresse de retour de la fonction et un saut vers le bon endroit dans le code. Toutes ces instructions qui apparaissent en plus du corps de la fonction incr servent en fait à implémenter la convention d’appel, expliquée dans le post à propos de la pile d’appels de fonctions. Cette convention d’appel est précisément le coût de l’abstraction du concept de fonction, et l’on voit qu’il représente jusqu’à une dizaine d’instructions assembleur exécutées à chaque appel de la fonction incr par le processeur. Notons que le nombre d’instructions liées à la convention d’appel ne dépendant pas de la taille de la fonction, mais plutôt du nombre d’arguments qu’elle utilise.

Extension inline

Les plus motivés d’entre vous auront remarqué que je vous ai menti un peu jusqu’ici : l’assembleur du corps de boucle que je vous ai montré n’est pas exactement celui généré par gcc au niveau d’optimisation -O1. Voici ce qui se passe en réalité :

4005dc:	01 c2                	add    %eax,%edx
4005de:	83 c0 01             	add    $0x1,%eax
4005e1:	39 d8                	cmp    %ebx,%eax
4005e3:	75 f7                	jne    4005dc <main+0x42>

L’appel a la fonction incr a disparu ! Mais pourquoi le compilateur a-t-il supprimé notre fonction, et par quoi l’a-t-il remplacé ? Une comparaison rapide permet de se convaincre que le compilateur a tout simplement remplacé l’appel de fonction par le corps de la fonction lui-même, l’instruction add (plus ou moins équivalente à lea).

La première conséquence de ce remplacement est la diminution du nombre d’instructions du programme assembleur que la machine va exécuter ; on peut donc s’attendre à ce que l’éxecution soit maintenant plus rapide ! Et en effet, avec \(n=4\cdot10^9\), le programme original (sans remplacement) s’exécute en 0,55 s tandis que le programme avec remplacement s’exécute en 0,16 s. Cette optimisation nous a apporté un gain en performance de 340 % !

À plus haut niveau, la fonction incr peut être utilisée à plusieurs endroits, justifiant l’existence de cette fonction en tant qu’élément logique. Cependant, cette abstraction qui rend le code plus lisible est nuisible à la performance du programme compilé. Afin d’aller au delà de cet apparent paradoxe et permettre de concilier performance et abstraction, presque tous les compilateurs décident automatiquement de remplacer les appels de fonction par le corps de la fonction. Cette optimisation s’appelle l’inlining (ou extension inline en français) et est généralement l’une des optimisations ayant le meilleur rapport complexité/gain en performance.

L’inlining permet également d’augmenter les effets des autres optimisations du compilateur. En effet, les optimisations telles que l’analyse du code inutile reposent sur la capacité à analyser le code pour en déterminer des propriétés sur l’utilisation de telle ou telle variable, la structure des boucles, etc. Or, ces analyes de code sont obligées de s’arrêter à la porte des appels de fonctions. L’inlining a l’avantage de rendre le corps des fonctions visibles aux autres optimisations, leur permettant de repérer des structures auparavant cachées par l’appel de fonction.

Cependant, appliquer l’extension inline à toutes les fonctions n’est pas forcément une bonne idée. En effet, pour de très longues fonctions, l’inlining a plutôt pour effet d’augmenter énormément la taille du code assembleur généré pour des gains en performances négligeables. Pire, un code assembleur trop long dans un corps de boucle peut conduire à une perte de performance considérable. Cela est dû à des phénomènes de cache mémoire, que je détaillerai dans un futur billet. Ainsi, les compilateurs décident d’inliner ou pas selon un ensemble d’heuristiques guidées par de nombreux benchmarks, et au sein desquelles la taille du corps de la fonction joue un rôle principal.

Déroulement de boucles et prédiction de branches

Passons à un cas plus compliqué : comment faire pour inliner la fonction suivante ?

int fibo(int n) {
    if (n == 0)
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

Il est possible de remplacer fibo(n - 1) et fibo(n - 2) par le corps de la fonction, mais celui-ci contient aussi des appels à fibo… Cette fonction est récursive, et il n’est pas possible d’y inliner complètement les appels de fonction. Par contre, on peut répéter la procédure d’inlining une, deux ou trois fois : quel est l’avantage de faire cela ?

Une situation similaire est celle des corps de boucles : on peut également choisir de répéter le corps des boucles deux fois ou plus en substituant la variable i par i+1, i+2 par exemple. Cette répétition ou unrolling en anglais a plusieurs avantages. D’abord, si le nombre d’itérations est connu à la compilation, cela permet de supprimer des instructions jump qui sont pénalisantes d’un point de vue de la performance à cause de la prédiction de branches (que je détaillerai peut-être dans un prochain post). D’autre part et pour la même raison de l’inlining, l’unrolling en faisant apparaître clairement le code exécuté séquentiellement permet aux analyses de code de potentiellement reconnaître de nouvelles structures à optimiser. Par exemple, les processeurs possèdent des instructions spéciales pour exécuter la même opération sur plusieurs zones de la mémoire en même temps (SIMD) ; l’unrolling est nécessaire pour que le compilateur puisse s’apercevoir qu’il peut traduire le code vers ces instructions spéciales.

Néanmoins et comme pour l’inlining, l’unrolling appliqué abusivement peut avoir des conséquences néfastes sur la performance. Aussi les compilateurs ont aussi leurs heuristiques d’unrolling, voire des heuristiques couplées inlining/unrolling pour gérer les appels de fonctions dans des corps de boucles !

Pour aller plus loin

• L’utilité des fonctions en informatique est apparue très tôt ; à ce propos on peut lire ce papier de 1952 au style désuet mais qui contient déjà toutes les idées importantes sur le sujet.

• Il est possible de consulter les heuristiques d’inlining de LLVM ; articulées autour d’une notion de « coût », elles reposent d’abord sur une approche très empirique symbolisée par ce commentaire au dessus de constantes : « Various magic constants used to adjust heuristics ».