Ramasse-miettes (informatique) - Définition

Langages dotés de ramasse-miettes

• Common Lisp, Scheme, Smalltalk, Caml, Haskell, Prolog, Oz, Io
• interpréteurs de commandes et langages de scripts comme Bash, Csh, Korn shell, etc.
• Java, Lisaac, Objective-C, C#, Eiffel, D, C++/CLI
• Perl, Javascript, Ruby, ActionScript, PHP
• Python utilise un mécanisme de comptage de références doublé depuis la version 2.2 d'un ramasse-miettes Mark and Sweep pour la destruction des cycles.

Classification des ramasse-miettes

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.

Marquage et nettoyage

Ou mark and sweep en anglais. Un ramasse-miettes de ce 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 soit 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). Un avantage des ramasse-miettes copieurs est que la libération des objets blancs (morts) se fait en vrac, en libérant en une seule fois la zone ancienne, et que le coût du ramasse-miettes est proportionnel aux nombres d'objets vivants. Ceci est particulièrement utile quand il y a beaucoup d'objets alloués, dont la plupart sont temporaires et meurent rapidement.

Conservatif vs Précis

Ou conservative vs precise en anglais. Un ramasse-miettes est conservatif lorsqu'il ne libère pas certaines zones de mémoire devenues inutiles. Par exemple, le ramasse-miettes de Boehm considère tout mot mémoire comme un pointeur potentiel à suivre, y compris sur la pile d'appel, et s'utilise facilement en C. Au contraire, les ramasse-miettes précis distinguent partout les pointeurs des autres données (y compris sur la pile d'appel) et nécessitent pour ce faire la coopération du compilateur (qui va générer les descripteurs de cadre d'appels) ou du programmeur. Généralement, les ramasse-miettes conservatifs sont marqueurs et ne modifient pas l'adresse des zones utilisées.

Récupérateur à générations

Ou generational GC en anglais. Toutes les données d'un programme n'ont pas la même durée de vie. Certaines sont éliminables très peu de temps après leur création (par exemple, une structure de donnée créée uniquement pour retourner une valeur d'une fonction, et démantelée dès que les données en ont été extraites). D'autres persistent pendant toute la durée d'exécution du programme (par exemple, des tables globales créées pendant l'initialisation). Un ramasse-miettes traitant toutes ces données de la même façon n'est pas forcément des plus efficaces.

Une solution serait de demander au programmeur d'étiqueter les données créées selon leur durée de vie probable. Cependant, cette solution serait lourde à utiliser ; par exemple, il est courant que les données soient créées dans des fonctions de bibliothèque (par exemple, une fonction créant une table de hachage), il faudrait leur fournir les durées de vie en paramètre.

Une méthode moins invasive est le système des générations. Le ramasse-miettes opère alors sur une hiérarchie de plusieurs générations, étagées de la plus « jeune » à la plus « âgée ». Les données nouvellement créées sont (en général) placées dans la génération la plus jeune. On ramasse assez fréquemment les miettes dans cette génération jeune ; les données encore présentes à l'issue de la destruction des données inaccessibles de cette génération sont placées dans la génération d'âge supérieur, et ainsi de suite. L'idée est que les données de plus courte durée de vie n'atteignent, pour la plupart, pas la génération supérieure (elles peuvent l'atteindre si elles viennent d'être allouées quand le ramassage de miettes les repère dans la génération jeune, mais c'est un cas rare).

On utilise généralement 2 ou 3 générations, de tailles croissantes. Généralement, on n'utilise pas le même algorithme de ramasse-miettes pour les diverses générations. Il est ainsi courant d'utiliser un algorithme non incrémental pour la génération la plus jeune : en raison de sa faible taille, le temps de ramasse-miettes est faible et l'interruption momentanée de l'exécution de l'application n'est pas gênante, même pour une application interactive. Les générations plus anciennes sont plutôt ramassées avec des algorithmes incrémentaux.

Le réglage des paramètres d'un ramasse-miettes à génération peut être délicat. Ainsi, la taille de la génération la plus jeune peut influencer de façon importante le temps de calcul (un surcoût de 25 %, par exemple, pour une valeur mal choisie) : temps de ramasse-miettes, impact sur la localité du cache… Par ailleurs, le meilleur choix dépend de l'application, du type de processeur et d'architecture mémoire.

Comptage de références

Une solution qui vient vite à l'esprit pour la libération automatique de zones de mémoire est d'associer à chacune un compteur donnant le nombre de références qui pointent sur elle. Ces compteurs doivent être mis à jour à chaque fois qu'une référence est créée, altérée ou détruite. Lorsque le compteur associé à une zone mémoire atteint zéro, la zone peut être libérée. Cette méthode est très efficace dans la plupart des cas.

Cependant, cette technique a un inconvénient lors de l'usage de structures cycliques : si une structure A pointe sur une structure B qui pointe sur A (ou, plus généralement, s'il existe un cycle dans le graphe des références), mais qu'aucun pointeur extérieur ne pointe ni sur A ni sur B, les structures A et B ne sont jamais libérées : leurs compteurs de références sont strictement supérieurs à zéro (et comme il est impossible que le programme accède à A ou B, ces compteurs ne peuvent jamais repasser à zéro).

En raison de ces limites, certains considèrent que le comptage de références n'est pas une technique de récupération de mémoire à proprement parler ; ils restreignent le terme de récupération de mémoire à des techniques basées sur l'accessibilité.

Le comptage de références souffre de certains problèmes sérieux, comme son coût élevé en temps de calcul et aussi en espace mémoire et, comme on l'a vu, l'impossibilité de gérer les références circulaires. 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 (sockets…) autres 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 ressources, 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.