Miettes mnémoniques

Nous avons jusqu’ici parlé à plusieurs reprises des registres mémoires manipulés par les programmes assembleurs et qui constituent la mémoire immédiate du processeur, accessible immédiatement. Mais puisque ces registres mémoires sont en nombre limités (une trentaine généralement), que se passe-t-il si l’on a besoin de plus de cases mémoires ? Ou si l’on a besoin de stocker un gros objet sur plusieurs cases à la fois ? Au delà de ces questions, c’est la manière dont la mémoire est conceptualisée par les différents langages de programmation qui est intéressante : l’abstraction paye ici un lourd tribut en terme de performance.

La mémoire physique

En plus des registres du processeur, il existe deux types de mémoire. La mémoire morte (disques durs, clés USB) est persistante, survit à l’arrêt du courant mais impose des délais élevés pour chaque lecture ou écriture. La mémoire vive (ou RAM) ne survit pas à la coupure de courant (une case de mémoire dynamique est un condensateur qui se décharge assez rapidement), mais est beaucoup plus rapide. Ces caractéristiques font qu’il est crucial que le programme et ses données soient chargées en mémoire vive à l’exécution, sous peine d’une latence très élevée. C’est pour cela que la quantité de RAM influe très fortement sur la capacité d’un ordinateur à supporter des programmes lourds comme les jeux vidéos.

Concentrons nous maintenant sur la mémoire vive puisque c’est là que vivent les données de notre programme. On rappelle que dans un ordinateur la mémoire consiste en bits qui peuvent prendre la valeur 0 ou 1, et qu’ils sont fréquemment regroupés en paquets de 8 appelés octets. Les instructions de l’assembleur nous permettent essentiellement de la manipuler de la manière suivante :

la mémoire vive est vue comme un grand tableau d’octets dont chaque case est référencées par une adresse comprise entre 0 et \(2^{64}\) (si l’adresse est notée sur 64 bits) ;
des instructions basiques permettent de lire 1, 2, 4, ou 8 octets situés à une adresse donnée et les transférer dans un registre, ou d’écrire depuis un registre vers la mémoire à une adresse donnée ;
une adresse est un nombre comme un autre ; on peut faire de l’arithmétique d’adresse et en particulier effectuer des opérations du type \(\mathrm{base} + (\mathrm{taille}\times\mathrm{index}) \) pour calculer l’adresse d’un élément d’un tableau.

Ainsi, lorsque qu’un programme comporte plus de variables que de registres, certaines sont transférées dans la mémoire vive. Cette mémoire est aussi utilisée pour stocker tout ce qui ne tient pas dans un registre mémoire : tableaux, objets complexes, etc. Néanmoins, ces objets complexes ne sont pas conceptuellement représentés en assembleur : l’abstraction « tableau » vient du fait que l’on a choisi de placer côte à côte en mémoire un ensemble d’éléments ayant la même taille. Mais cette abstraction est très pratique pour le développeur, et c’est pour cela que tous les langages de programmation de haut niveau l’implémentent. On voit donc ici qu’il est intéressant pour un langage d’offrir au développeur des abstractions sur la mémoire et sa gestion.

Pilotage manuel : attention aux fuites

Au fur et à mesure de l’exécution du programme, de plus en plus d’objets de différentes tailles vont être écrits en mémoire vive. Mais comment décider à quel adresse du tableau écrire un nouvel objet ? On parlera d’allouer de la mémoire lorsque l’on écrit un objet en mémoire pour la première fois. Le plus simple et de commencer par allouer au début du tableau, puis à la suite de la dernière zone de mémoire allouée à chaque fois. Ainsi, les objets ne sont jamais écrasés et on peut y accéder quand on veut. Mais que se passe-t-il lorsqu’un objet n’est plus jamais accédé ? Avec notre solution, il reste là indéfiniment et occupe de la place dans le tableau pour rien ; la RAM de notre ordinateur est vite saturée, c’est la fuite de mémoire.

On alloue les blocs les uns à la suite des autres

Pour éviter ce scénario, le langage de programmation va offrir au développeur, en plus de la possibilité d’allouer de la mémoire, celle de la libérer. Ainsi, lorsqu’il sait qu’il n’a plus besoin d’accéder à l’objet en mémoire, le développeur libère la zone de la mémoire. Mais si l’allocation de mémoire est traduite en assembleur par l’écriture de l’objet à une adresse donnée, comment traduire la libération de cette zone ? La réponse est : par rien. En effet, le programme va laisser cette zone de mémoire telle qu’elle ; par contre, il va noter par ailleurs que la zone du tableau située à cette adresse est libre, ce qui veut dire qu’elle peut être allouée de nouveau.

Ainsi, au fur et à mesure des allocations et libérations, le tableau de la mémoire vive va ressembler à la bouche d’un enfant en pleine chute de ses dents de lait (et pousse de ses dents définitives) : des zones allouées et libres de tailles différentes mélangées aléatoirement. Dès lors, un immense espace d’optimisation s’ouvre lorsque l’on veut compacter la mémoire, c’est à dire allouer la mémoire en bouchant les trous libérés lorsque c’est possible, afin de garder en permanence de grands espaces libres en prévision d’une hypothétique allocation d’un grand espace, qui peut survenir n’importe quand.

Après plusieurs allocations et libérations, il n'y a plus de grand espace contigu libre

Avec cette gestion, la mémoire physique a été abstraite et son caractère linéaire est caché au développeur : les objets ont l’air de vivre telles des billes dans un grand sac, que l’on peut retirer ou ajouter à sa guise. Ce gestion manuelle de la mémoire est cependant exigeante pour le développeur qui ne doit pas oublier de libérer sa mémoire à chaque fois. La gestion manuelle expose au développeur le concept d’une durée de vie bien définie d’un objet, qui l’oblige à constamment se préocuper de sa mémoire. Il faut séparer les objets vivants des objets morts pour pouvoir réutiliser la mémoire. Afin de se libérer de ce fardeau, d’autres langages ont une autre approche.

Ramassage de miettes

On s’impose maintenant la contrainte suivante : le développeur ne déclare plus la libération de ses objets. Comment éviter le scénario de la fuite de mémoire ? Nous avons perdu l’information qui nous permettait de distinguer un objet vivant d’un mort ; il nous faut la retrouver.

Pour cela, à intervalles réguliers, on stoppe l’exécution du programme et on regarde la mémoire. Quels sont les objets vivants ? Premièrement, tous les objets contenus dans les registres mémoires, la mémoire immédiate, peuvent être considérés comme vivants sans se tromper de trop. Ensuite, tous les objets dans la mémoire qui correspondent à des variables locales des fonctions actives. Est-ce tout ? Dans un certain sens, oui, car le programme ne peut pas accéder directement à d’autres variables que celles-ci (on suppose qu’il ne peut pas sortir des adresses valides de son chapeau). Néanmoins, ces variables et objets vivants peuvent contenir des adresses d’autre objets. Qui, du même coup, deviennent vivants, ainsi que ceux qu’ils référencent. On procède alors au parcours cette toile d’objets interconnectés (un graphe), afin de recenser tous les objets vivants. Une fois ceci fait, que reste-t-il ? Les miettes de mémoires, objets morts que l’on peut libérer sans craintes car inaccessibles par le programme.

Cet algorithme dit « marquant et nettoyant » est un des quelques algorithmes classiques permettant ce qu’on appelle le ramassage de miettes, c’est à dire la libération des objets dont on a pu prouvé qu’ils étaient morts. Il existe d’autres algorithmes remplissant le même but, chacun ayant ses avantages et inconvénients. Le ramasseur de miettes est abrégé en GC (garbage collector en anglais) et est une caractéristique clivante d’un langage de programmation.

Graphe des objets, ici d n'est plus accessible, il peut être libéré

En effet, si le GC permet au développeur de ne plus se soucier de la gestion de la mémoire, cela se fait au détriment de la performance, tant au niveau du temps d’exécution que de la compacité de la mémoire obtenue. Rappelons que le GC tente de reconstituer une information non donnée par le développeur ; l’analyse qu’il effectue est donc conservative, ce qui veut dire qu’il va considérer par précaution comme vivants des objets qui ne seront en réalité plus jamais accédés par le programme dans le futur. Ceci impacte la compacité de la mémoire en comparaison avec une gestion manuelle ou le développeur sait exactement à quel moment les objets sont utilisés pour la dernière fois. Enfin, l’exécution du programme doit s’arrêter à chaque fois que le GC opère sa magie, et parcourir le graphe prend d’autant plus de temps que la quantité de mémoire utilisée est grande.

Le prix de l’abstraction

Un langage avec GC s’affranchit donc totalement de la notion de mémoire, et le développeur a l’impression de manipuler des objets sans contrainte aucune. Néanmoins, cette abstraction provoque une perte de performance d’un bon ordre de grandeur à l’exécution. De manière intermédiaire, la gestion manuelle à base d’allocation et de libération offre une abstraction moins pratique à utiliser mais à un coût très faible par rapport à la performance d’un programme écrit directement en assembleur. On voit ici apparaître un compromis très fort entre ergonomie du langage et performance. Concernant la mémoire, il n’est pas possible d’avoir le beurre et l’argent du beurre, et la décision de doter un langage d’un GC ou non détermine directement ses applications ; un programme performant est toujours plus difficile à écrire !

Pour aller plus loin

Ce post de Lin Clark, et tous les autres abondamment illustrés qui expliquent comment la mémoire est gérée dans un navigateur internet. Ce billet est d’ailleurs largement inspiré de ce contenu.
Une visualisation du fonctionnement de différents algorithmes de GC.
Une explication du fonctionnement du GC de Python, plus simple que le parcours de graphe expliqué ici.
Ce post Reddit dont les réponses font le tour des méthodes de gestion de mémoire.