Ramasse-miettes

Le ramasse-miettes, ou le «Garbage Collection» en anglais, est une ressource complète dédié à la gestion automatique de la mémoire dynamique. Elle permet de réutiliser les parties de mémoires libérer par le ou les programmes afin que d'autres programmes puis l'utiliser selon leur besoin. Il s'agit en quelque sorte d'une forme de recyclage de la mémoire. Ainsi, si on utilise pas de ramasse-miettes pour gérer la mémoire, un programme à la possibilité de soit gérer manuellement l'espace de mémoire dynamique qu'il dispose ou gérer sa mémoire comme un vulgaire tableau incrémentale où chaque morceaux libéré ne sera jamais réutilisé. Cette dernière n'est pas vraiment pratique, car plus vous utiliseriez un programme plus il consommerait de la mémoire et finirait nécessairement par toute l'utiliser et un redémarrage du système serait donc nécessaire pour réutiliser cette mémoire.

Le premier système proposant un ramasse-miettes de façon standard dans son environnement fut le langage de programmation Lisp inventé en 1958 par John McCarthy et le premier programme de ramasse-miette fut écrit par son étudiant Daniel J. Edwards. Tandis que du côté francophone, la première fois que le terme ramasse-miettes fut utilisé plutôt que le terme anglophone «Garbage Collection», date de 1970 dans les communications de Claude Pair (mathématicien, informaticien et haut fonctionnaire français) pour son cours d'informatique à l'université de Nancy en France.

Les algorithmes

Algorithme à comptage de références

L'algorithme à comptage de références est l'une des méthodes les plus simples et les plus utilisées pour la gestion automatique de la mémoire dans les langages de programmation. Chaque objet en mémoire est associé à un compteur indiquant combien de références pointent vers lui. Lorsqu'une nouvelle référence est créée, ce compteur est incrémenté, et lorsqu'une référence est supprimée ou redirigée, le compteur est décrémenté. Si ce compteur atteint zéro, cela signifie que plus aucun code du programme ne peut accéder à cet objet, il est donc automatiquement libéré. Ce mécanisme permet une libération immédiate et prévisible de la mémoire, sans avoir besoin d'un balayage périodique de la mémoire de tas. Cette méthode est souvent intégrée dans les langages qui visent une gestion fine et localisée de la mémoire, comme Python ou Swift. Elle offre l'avantage de fonctionner en temps réel, sans pauses longues.

Sur le plan des structures de données, cet algorithme s'intègre naturellement dans les systèmes à base de graphes, listes chaînées, arbres, ou objets interconnectés. À chaque liaison entre deux structures, une référence est créée et comptabilisée. Lorsqu'une structure est supprimée ou perdue, toutes les références sont mises à jour automatiquement, et si certaines deviennent inaccessibles, la libération en cascade peut s'opérer. Toutefois, ce comportement est dépendant de l'exactitude du comptage, et un oubli ou une erreur peut conduire à des fuites mémoire. L'algorithme est facile à implémenter mais nécessite que toutes les modifications de pointeurs soient correctement gérées, ce qui peut ralentir légèrement les performances. Dans les systèmes embarqués ou les applications à temps réel, son usage est apprécié pour sa prévisibilité. Il fonctionne aussi bien dans un environnement orienté objet que dans des structures plus classiques.

Cependant, l'une des principales limites du comptage de références réside dans son incapacité à gérer les cycles de références. Par exemple, deux objets se référant mutuellement verront leurs compteurs rester au-dessus de zéro même s'ils ne sont plus accessibles par le programme. Ces objets deviennent donc incollectables par cet algorithme seul, ce qui conduit à des fuites de mémoire. Pour pallier ce défaut, certains environnements intègrent un second ramasse-miettes basé sur la recherche d'objets inaccessibles (comme le marquage/balayage) en complément du comptage. Ainsi, on combine la réactivité du comptage de références avec la couverture plus complète d'un collecteur cyclique. En résumé, bien que très utile et efficace dans de nombreux cas, le comptage de références doit souvent être renforcé par d'autres stratégies pour garantir une gestion mémoire complète et robuste. C'est pourquoi il constitue un bon compromis dans des systèmes de taille moyenne ou avec une gestion contrôlée des cycles.

Algorithme traversants

L'algorithme traversant, souvent associé à la technique de marquage et balayage (mark and sweep), est une méthode de gestion mémoire reposant sur l'identification des objets accessibles à partir d'un ensemble de références appelées racines. Ces racines incluent généralement les variables globales, la pile d'appels et les registres. L'algorithme explore récursivement tous les objets atteignables depuis ces racines en les marquant comme vivants. Une fois cette phase de marquage terminée, tous les objets non marqués sont considérés comme inaccessibles et donc candidats à la libération. Ce processus permet de récupérer efficacement la mémoire occupée par les objets inutilisés. Le principal avantage de cette méthode est sa capacité à gérer les cycles de références, ce que les algorithmes à comptage de références ne peuvent pas faire. Elle est donc particulièrement utile dans des structures de données complexes où des objets peuvent se référencer mutuellement.

Lors de la traversée, l'algorithme visite les objets à partir des racines et suit chaque champ qui contient une référence vers un autre objet. Il fonctionne sur le principe de la reconnaissance de graphe orienté, où chaque noud (objet) est exploré de façon récursive ou itérative. La structure de données utilisée est souvent une pile ou une file pour gérer les objets à visiter. À chaque visite, l'objet est marqué pour éviter les répétitions et garantir qu'il ne sera pas libéré à tort. La complexité temporelle dépend de la taille du graphe d'objets vivants, mais elle est généralement acceptable pour des programmes bien structurés. Les structures comme les listes chaînées, les arbres et les graphes se prêtent bien à cette approche, car elles peuvent être parcourues sans ambiguïté à partir des racines. Ce mode de fonctionnement est plus global que le comptage de références, car il traite la mémoire de manière cohérente en un seul passage périodique.

L'inconvénient majeur de l'algorithme traversant est qu'il nécessite un arrêt du programme pendant la phase de collecte, ce qu'on appelle le stop-the-world. Cela peut provoquer des latences visibles dans les applications temps réel ou interactives, où la fluidité est cruciale. Pour pallier cela, des variantes modernes comme les collecteurs incrémentaux ou concurrentiels ont été développées. Malgré cette limitation, l'approche traversante reste très fiable et permet une gestion mémoire sans fuite, même dans des graphes d'objets très complexes. Elle est largement utilisée dans des environnements comme Java ou .NET, où la mémoire est abondante mais doit être contrôlée de façon sûre. En combinant simplicité conceptuelle et robustesse, l'algorithme traversant est une solution adaptée pour les systèmes à structures de données riches et fortement interconnectées. Il offre une base solide pour des améliorations plus sophistiquées en gestion automatique de la mémoire.

Algorithmes à générations

L'algorithme à générations est une stratégie de ramasse-miettes fondée sur une observation clef du comportement des programmes : la majorité des objets alloués en mémoire ont une durée de vie courte. Pour optimiser la gestion de la mémoire, cet algorithme divise l'espace mémoire en plusieurs zones appelées générations, généralement au nombre de trois?: la jeune génération, la génération intermédiaire (ou adulte), et la génération ancienne. Les objets nouvellement créés sont d'abord placés dans la jeune génération, qui fait l'objet de collectes fréquentes mais rapides. En cas de survie à plusieurs cycles de collecte, ces objets sont promus vers des générations plus âgées. Cela permet de concentrer l'effort du ramasse-miettes sur les zones où le taux de libération est élevé, tout en évitant de revisiter inutilement les objets durables.

La collecte dans les générations est déclenchée de manière différenciée. La jeune génération est nettoyée souvent, car elle contient surtout des objets temporaires, ce qui permet une collecte efficace et rapide. En revanche, les générations adultes et anciennes sont nettoyées moins fréquemment, car elles sont supposées contenir des objets vivants sur le long terme. Cette hiérarchisation permet d'éviter les performances dégradées d'une collecte intégrale à chaque allocation. Le processus de promotion des objets se fait en fonction d'un âge logique, calculé en fonction du nombre de cycles de collecte qu'un objet a traversé sans être supprimé. Lorsqu'un objet atteint un seuil d'âge, il est déplacé vers la génération suivante, où la fréquence de collecte est plus basse.

L'utilisation d'un algorithme à générations améliore significativement les performances du ramasse-miettes, notamment dans les langages à gestion automatique de mémoire comme Java, .NET ou certains moteurs PHP. Il diminue la latence globale des programmes en réduisant la fréquence des collectes complètes, et en rendant plus prévisibles les pauses dues au nettoyage mémoire. En revanche, cette méthode introduit une complexité supplémentaire dans la gestion des objets intergénérationnels, notamment les pointeurs d'objets jeunes depuis les objets anciens, qu'il faut surveiller par des write barriers (barrières d'écriture). Malgré ces défis techniques, les algorithmes à générations sont devenus une norme dans la conception moderne des collecteurs de mémoire. Ils permettent de concilier efficacité, robustesse et bon usage des ressources dans des applications de grande envergure.

Ramasse-miettes par langage de programmation

Voici un tableau récapitulatif des algorithmes de ramasse-miettes (ou de gestion mémoire) utilisés dans différents langages de programmation populaires. Ce tableau mentionne les algorithmes principaux, mais garde à l'esprit que certains langages ou environnements peuvent combiner plusieurs stratégies ou en proposer plusieurs options selon les versions ou les implémentations.

Bibliothèque de ramasse-miette

Voici un tableau répertoriant quelques bibliothèques de ramasse-miettes (garbage collection) pour différents langages de programmation :