Un ramasse-miettes, ou récupérateur de mémoire (en anglais garbage collector, abrégé en GC) en informatique est un système de gestion automatique de la mémoire. Il est responsable du recyclage de la mémoire préalablement allouée puis inutilisée.
Lorsqu'un système dispose d'un ramasse-miette, ce dernier fait généralement partie du système d'exécution associé à un langage de programmation particulier. Ce langage est dit garbage collected. Le ramassage des miettes a été inventé par John McCarthy comme faisant partie du premier système Lisp. Il est légèrement incorrect de parler d'un langage à ramasse-miettes, tout comme il est incorrect de parler d'un langage compilé. Ces caractéristiques sont propres à une implémentation du langage.
Principe de base
Le principe de base de la gestion automatique de la mémoire est simple :
- déterminer quels objets dans le programme ne peuvent être utilisés,
- récupérer le stockage utilisé par ces objets.
(objets vivants vs atteignables)
Les ramasse-miettes utilisent un critère d'atteignabilité pour déterminer si un objet sera utilisé (note : voir également sur le comptage de référence ci-dessous).
Atteignabilité d'un objet
Les principes sont :
- Un ensemble distinct d'objets qui sont supposés atteignables, ce sont les racines. Dans un système typique ces objets sont les registres machine, la pile, le pointeur d'instruction, les variables globales. En d'autres termes tout ce qu'un programme peut atteindre directement.
- Tout objet référencé depuis un objet atteignable est lui-même atteignable
Dit autrement : un objet atteignable peut être obtenu en suivant une chaîne de pointeurs ou de références.
Algorithme de base
Les ramasse-miettes effectuent des cycles de ramassage. Un cycle est démarré lorsque le récupérateur décide (ou est notifié) qu'il doit récupérer de l'espace de stockage. Un cycle est constitué des étapes suivantes :
- Créer des ensembles dit noir, gris et blanc. Initialement, l'ensemble noir est vide, l'ensemble gris contient les objets "racines" et éventuellement certains objets supplémentaires choisis en fonction de l'algorithme particulier employé, et l'ensemble blanc contient tout le reste. A tout moment dans l'exécution de l'algorithme, un objet ne peut être que dans un seul des trois ensembles. L'ensemble blanc peut être vu comme l'ensemble des objets dont nous essayons récupérer l'espace mémoire ; au cours du cycle, l'algorithme ôtera des objets de l'ensemble blanc, y laissant les objets dont il peut réclamer l'espace mémoire.
- (cette étape est répétée jusqu'il n'y ait plus d'objets dans l'ensemble gris). Choisir un objet de l'ensemble gris, déplacer cet objet vers l'ensemble noir, déplacer tous les objets blancs référencés (directement) par l'objet gris vers l'ensemble gris.
- Quand il n'y a plus d'objets dans l'ensemble gris, alors tous les objets restant dans l'ensemble blanc ne sont pas atteignables, et l'espace mémoire qu'ils utilisent peut être réclamé.
L'invariant des trois couleurs peut être traduit comme ceci :
- aucun objet noir ne pointe directement sur un objet blanc.
Observons que l'algorithme ci-dessus préserve l'invariant des trois couleurs.
La partition initiale n'a pas d'objet noir, de sorte que l'invariant est -trivialement- respecté. Par la suite, si un objet devient noir, tous ses fils directs (les objets qu'il référence) deviennent gris, ceci préservant l'invariant. Lorsque la dernière étape de l'algorithme est réalisée, parceque l'invariant est préservé, aucun des objets de l'ensemble noir ne pointe vers un objet de l'ensemble blanc (et il n'y a pas d'objet gris) ce qui signifie que les objets blancs résiduels doivent être inatteignables depuis les racines. Alors le système peut appeler leurs destructeurs et libérer leur espace mémoire.
Certaines variantes de l'algorithme ne respectent pas l'invariant des trois couleurs, mais ils utilisent un principe différent par lequel toutes les propriétés importantes sont respectées.
Variantes de l'algorithme de base
L'algorithme de base a plusieurs variantes.
- Il y a le problème des ramasse-miettes qui déplacent les objets en mémoire (qui changent leur adresse), ou pas.
- Certains récupérateurs peuvent correctement identifier toutes les références à un objet ; ils sont appelés des récupérateurs "exacts", par opposition avec des récupérateurs "conservateurs" ou "partiellement conservateurs". Les ramasse-miettes "conservateurs" doivent présumer que n'importe quel suite de bits en mémoire est un pointeur si (lorsqu'interprétée comme un pointeur) elle pointait sur un quelconque objet instancié. Ainsi, les récupérateurs conservateurs peuvent avoir des faux négatifs, où l'espace mémoire n'est pas réclamé à cause des faux pointeurs accidentels. En pratique, ce n'est pas un gros inconvénient.
- Un autre problème : le ramasse-miettes peut s'exécuter en alternance ou en parallèle avec le reste du système ; les récupérateurs les plus simples suspendent l'exécution du système lorsqu'ils exécutent un cycle ; ils ne sont pas incrémentaux ; les récupérateurs incrémentaux entrelacent leur travail avec des unités d'activité du reste du système. Certains récupérateurs incrémentaux peuvent s'exécuter complètement en parallèle dans un thread séparé ; ils peuvent en théorie s'exécuter sur un processeur différent, mais le coût de la mise en cohérence des caches rend cette approche moins pratique qu'il n'y paraît.
Mark and sweep (marquage et nettoyage)
Les récupérateurs peuvent être classés en considérant la façon dont ils implémentent les trois ensembles (d'objets blancs, gris et noirs). A ramasse-miettes de type maintient un bit (ou deux) associé à chaque objet pour indiquer s'il est blanc ou noir ; l'ensemble gris est maintenu soit comme une liste séparée ou en utilisant un autre bit. Un récupérateur copieur distingue les objets gris et noirs en les copiant vers d'autres zones mémoire (l'espace de copie) et souvent différencie les objets noirs des objets gris en bi-partitionnant l'espace de copie (dans le cas le plus simple en maintenant un unique pointeur qui indique la séparation entre les objets noirs et gris).
Generational GC (Récupérateur à générations)
Le problème est le suivant : quand effectuer un cycle et quels objets placer dans l'ensemble gris initial. Un récupérateur simple ne mettra que les racines dans l'ensemble gris initial, et tout le reste sera initialement blanc.
D'un point de vue statistique, les objets créés récemment par le système sont également ceux qui ont le plus de chances de devenir rapidement inatteignables. Un récupérateur à générations partitionne les objets en générations et ne place généralement que les objets d'un sous-ensemble de toutes les générations dans l'ensemble blanc initial (l'ensemble gris contenant "tout le reste"). Cela peut se traduire par des cycles plus rapides.
Comptage de références
Le comptage de références est généralement mentionné comme une technique de récupération mémoire, mais cet usage n'est pas formellement accepté. On pourrait argumenter que le comptage de références est une classe de récupération conservatrice. Certains puristes préfèrent réserver le terme de récupération de mémoire pour des algorithmes et des systèmes qui déterminent le caractère vivant des données sur le principe de l'atteignabilité.
Le comptage de références a de toutes façon de sérieux problèmes, comme l'incapacité à gérer les références circulaires et le coût élevé à la fois en espace mémoire et en temps de calcul. D'un autre côté, il récupère les "miettes" plutôt vite, ce qui présente des avantages s'il y a des destructeurs à exécuter pour libérer les ressources rares autres (sockets...) que le tas (mémoire).
Des systèmes hybrides utilisant le comptage de références pour obtenir la libération quasi-immédiate des resources, et appelant à l'occasion un récupérateur de type Mark and Sweep pour libérer les objets contenant des cycles de références, ont été proposés et parfois implémentés.
Cela donne le meilleur des deux mondes, mais toujours au prix d'un coût élevé en termes de performances.
Langages utilisant la récupération automatique de mémoire
Références
