Pile ou face, un tas de problèmes

Avant de s’attaquer à la programmation fonctionnelle, il est nécessaire de faire une petite digression sur le concept de fonction, et plus particulièrement la manière dont les données interagissent au sein et entre les appels de fonction. Nous verrons que la gestion des appels de fonction est souvent effectuée grâce à une forme d’organisation de la mémoire différente que celle dont nous avons parlé dans ce précédent billet.

Convention d’appel

Premièrement, il nous faut définir ce qu’est une fonction en informatique. Une fonction est une unité de code qui prend des données en argument et retourne un résultat . Tous les langages de programmation autres que l’assembleur possèdent un concept de fonction, car c’est la façon la plus simple et la plus efficace d’éviter la duplication de code. Par exemple dans une recette de cuisine, on pourra utiliser « faire un roux avec 200 g de farine » plutôt que de détailler la recette du roux à chaque fois que l’on veut l’utiliser. Créer une fonction, c’est créer une entité cohérente avec des entrées et des sorties bien définies, que l’on peut réutiliser plusieurs fois ; une fonction est donc une abstraction.

Maintenons, intéressons-nous à la manière dont le concept de fonction est traduit en assembleur. Il est à ce point essentiel d’avoir compris les concepts de l’article sur l’assembleur pour poursuivre la lecture. Assez logiquement, une fonction est avant tout une suite d’instructions : le corps de la fonction. C’est le corps de la fonction qui va réaliser ce que la fonction est censé faire. Mais comment en assembleur faire référence aux arguments de la fonction, et comment faire pour déclarer ce que l’on retourne à la fin ? Une première méthode est d’utiliser les registres mémoire. On va donc définir une convention dite convention d’appel de la manière suivante :

• le premier argument de la fonction se trouvera dans le registre numéro 1 ;
• le deuxième argument de la fonction se trouvera dans le registre numéro 2 ;
• et ainsi de suite pour les autre arguments ;
• la valeur de retour de la fonction sera placée à la fin de l’exécution de celle-ci dans le registre numéro 0.

Ainsi dans le corps de la fonction, on suppose que la convention est respectée et on ira chercher les arguments dans les registres correspondants. À la fin de l’exécution, il faudra néanmoins faire un peu de travail en plus et placer son résultat dans le bon registre pour respecter la convention. Car cette convention d’appel n’affecte pas que le corps de la fonction, elle affecte aussi le code qui appelle la fonction ! En effet, ce code qui appelle devra placer les arguments dans les bons registres avant d’appeler la fonction, en contrepartie de quoi il saura où trouver le résultat juste après l’appel. La convention d’appel est un contrat mutuellement bénéfique qui lie l’appelant et l’appelé.

Cependant, il est facile de voir les limitations de cette convention d’appel simpliste. Que faire lorsque l’on a plus d’arguments dans la fonction que de registres ? Mais derrière cela se cache un problème beaucoup plus subtil en lien avec la problématique de gestion de la mémoire.

Pile et cadres de pile

En effet, supposons que nous sommes dans un langage à gestion manuelle de la mémoire comme C, et que notre fonction possède une variable locale, x. Où stocker x en mémoire ? On peut la mettre dans un registre, mais ils sont en nombre limités et si il y a plus de variables que de registres, le problème subsiste. Il faut donc allouer de la mémoire pour x quelque part dans le grand tableau, et libérer cette mémoire à la fin de la fonction. Or dans un langage à gestion manuelle de la mémoire, on est censé explictement libérer la mémoire lorsque l’on en a plus besoin. Néanmoins en C la fonction suivante qui ajoute 1 à son argument est valide :

int increment(int arg) {
    int x;
    x = arg + 1;
    return x;
}

On ne voit ici pas d’appels à malloc et free, qui sont pourtant les moyens d’allouer et de libérer de la mémoire en C. C’est donc que ces appels sont implicitement traduits vers l’assembleur ; en effet int x; est traduit par une allocation de mémoire pour contenir x, et lorsque le programme atteint return, cette mémoire est libérée. Il faut donc que le programme se souvienne de tous les emplacement mémoire alloués pour les variables locales de la fonction, et qu’il les libère un à un à la fin de la fonction. Or si l’on utilise une allocation de mémoire dynamique comme celle présentée dans le billet sur la gestion de la mémoire, les adresses des zones de mémoire allouées pour les variables locales vont être éparpillées un peu partout dans le grand tableau de la mémoire.

Ceci a deux désavantages. Premièrement, il faut maintenir une liste de toutes les adresses des zones de mémoire des variables locales afin de pouvoir les libérer en fin de fonction. Une fonction pouvant contenir des centaines de variables locales de petite taille, cela peut doubler l’utilisation de la mémoire par le programme. La deuxième raison est plus subtile et fera l’objet d’une explication plus détaillée par la suite. Pour se donner une idée, disons qu’il est beaucoup plus lent pour le processeur d’accéder consécutivement dans le temps à des régions du tableau de mémoire éloignées les unes des autres que deux régions contiguës. Cette façon d’accéder à la mémoire est appelée localité de la mémoire. Or les variables locales d’une même fonction sont très souvent utilisées consécutivement par le programme, et ne pas les placer les unes à côté des autres en mémoire réduit la performance d’exécution significativement.

On voit ici que notre manière d’organiser la mémoire n’est pas adaptée à un programme qui consiste en une suite d’exécution de fonctions. Plus précisément, il est préférable de regrouper dans une même zone de mémoire tout ce qui a trait à l’exécution de la fonction. Cette zone de mémoire est appelée un cadre de pile. On y trouve :

• les arguments surnuméraires;
• les variables locales;
• l’adresse de retour de l’appel de fonction, c’est-à-dire l’emplacement du code où la fonction a été appelée et où il faut retourner à la fin de l’exécution de la fonction.

Grâce au cadre de pile, les deux désavantages évoqués sont résolus. La taille de ce cadre peut être calculée statiquement si l’on connaît le type des arguments et des variables locales. À la fin de l’exécution de la fonction, il suffit de libérer l’ensemble du cadre de pile au lieu d’une myriade de petites zones. De plus, toutes les données accédées par la fonction sont maintenant proches dans le tableau de mémoire. Mais pourquoi s’arrêter là ? En effet, il est utile de placer à côté en mémoire les cadres de pile de fonctions appelées consécutivement dans le temps pour maximiser la performance.

Pour résoudre ce problème, il suffit de concevoir les appels de fonction comme interagissant avec une pile :

• la fonction en cours est sur le dessus de la pile ;
• quand on retourne de la fonction en cours, on la retire de la pile et on regarde la fonction juste en dessous pour savoir où continuer l’exécution ;
• appeler une fonction revient à la mettre sur le dessus de la pile.

Le mot pile (stack en anglais) caractérise précisément cette structure où l’on n’a accès qu’à l’élément du dessus. Pendant l’exécution du programme, il suffit de disposer les cadres de pile afin de former une pile qui varie au gré des appels de fonction. Grâce à cela, on s’assure de la localité de la mémoire. Cette gestion de la mémoire en pile pour les appels de fonction est si importante que les processeurs ont des registres et instructions spéciales pour gérer les opérations sur la pile : push et pop ajoutent et enlèvent une valeur sur la pile, call crée le cadre de pile suivant et appelle une fonction, ret libère l’adresse de retour de la fonction et retourne l’exécution à l’appelant.

Mais alors, pourquoi ne pas gérer toute la mémoire comme une pile si cela donne l’avantage de la localité de la mémoire ? Il y a un gros désavantage à la pile : les variables ne sont en mémoire que pendant la durée d’exécution de la fonction qui les contient. En effet, à la fin de l’exécution de la fonction, la mémoire du cadre de pile est libérée et les données qu’il contenait sont perdues. Le seul moyen de passer les données entre fonctions dans le programme est d’utiliser les arguments et les valeurs de retour. Cela marche peut-être lorsque les données sont petites mais lorsque l’on manipule de gros objets, cela veut dire que l’on doit copier les objets à chaque appel de fonction ! Cela est terriblement inefficace, on a envie d’allouer de la mémoire une fois pour toute pour ces objets et de les y laisser là.

Pile et tas

Ainsi pour les objets vivants plus longtemps qu’un appel de fonction, il est préférable d’utiliser le mode de gestion de la mémoire que nous avons exposé précédemment et que l’on appelle le tas (heap en anglais), car il n’a pas de structure d’accès particulière. Lors de l’exécution d’un programme, on a donc deux mémoires différentes qui coexistent, la pile et le tas, chacune stockant des données différentes avec une gestion différente. La pile et le tas se partagent donc le tableau de la mémoire. Traditionnellement, le tas possède le début des adresses et croît vers le haut quand on rajoute des données, la pile possède la fin des adresses et croît vers le bas lorsque l’on appelle une fonction.

Vous pouvez désormais comprendre la mystérieuse erreur StackOverflow qui survient généralement lorsqu’on programme une boucle infinie à l’aide de fonctions récursives : les appels de fonction font grossir la pile qui finit par empiéter sur le tas ; heureusement que ceci est détecté et provoque l’exécution du programme, sinon les données du tas auraient été silencieusement corrompues par la pile.

Pour aller plus loin

• La convention d’appel est en fait une partie d’un ensemble de conventions qui définissent comment utiliser l’assembleur afin de traduire des concepts de haut niveau dans plusieurs langages, afin que ceux-ci puissent interopérer à bas niveau. Ceci est appelée interface binaire d’application (ABI en anglais), et ce document décrit par exemple l’ABI conseillée par AMD pour son architecture 64 bits. En effet, le processeur est souvent optimisé afin d’exécuter plus rapidement les morceaux d’assembleurs décrits par l’ABI.

• Ce document décrivant la manière dont Java est exécuté nous apprend que Java ne possède pas de pile à proprement parler : les cadres de pile sont alloués dans le tas sans être à côté les uns des autres.

• Les cadres de piles sont en fait des régions de mémoire contenant plusieurs objets qui sont allouées et libérées en même temps. Ce mécanisme est généralisé par la gestion par régions de la mémoire, qui peut s’utiliser en complément d’un garbage collector lorsque l’on veut contrôler un peu plus finement la durée de vie des objets en mémoire.