Comment mettre en œuvre un ramasseur de déchets ?

Question

Quelqu'un pourrait-il m'indiquer une bonne source sur la façon d'implémenter le ramassage des déchets ? Je suis en train de créer un langage interprété de type lisp. Il utilise actuellement le comptage de références, mais bien sûr, cela ne permet pas de libérer les objets dépendants de manière circulaire.

J'ai lu des articles sur le marquage et le balayage, le marquage tricolore, le mouvement et le non-mouvement, l'incrémentation et l'arrêt du monde, mais... Je ne sais pas quelle est la meilleure façon de garder les objets proprement séparés en ensembles tout en gardant la surcharge mémoire par objet au minimum, ou comment faire les choses de façon incrémentale.

J'ai lu que certains langages avec comptage de référence utilisent la détection de référence circulaire, ce que je pourrais utiliser. Je suis conscient que je pourrais utiliser des collecteurs disponibles gratuitement comme Boehm, mais j'aimerais apprendre à le faire moi-même.

J'apprécierais tout matériel en ligne avec une sorte de tutoriel ou d'aide pour les personnes sans expérience sur le sujet comme moi.

Answer 1

Quelqu'un pourrait-il m'indiquer une bonne source sur la façon d'implémenter le ramassage des déchets ?

Il y a beaucoup de matériel avancé sur la collecte des déchets. Le site Manuel de collecte d'ordures est génial. Mais j'ai trouvé qu'il y avait très peu d'informations de base, alors j'ai écrit quelques articles sur le sujet. Prototypage d'un ramasseur d'ordures à balayage (mark-sweep) décrit un GC de balayage de marque minimal écrit en F#. Le site Collecteur d'ordures très concurrent décrit un collecteur concurrent plus avancé. HLVM est une machine virtuelle que j'ai écrite et qui comprend un collecteur stop-the-world qui gère le threading.

La façon la plus simple d'implémenter un ramasseur de déchets est :

1. Assurez-vous de pouvoir rassembler les racines mondiales. Ce sont les variables locales et globales qui contiennent des références dans le tas. Pour les variables locales, poussez-les sur une pile fantôme pour la durée de leur portée.

2. Assurez-vous que vous pouvez parcourir le tas, par exemple que chaque valeur du tas est un objet qui implémente une fonction Visit qui renvoie toutes les références de cet objet.

3. Conserver l'ensemble de toutes les valeurs attribuées.

4. Allouer en appelant malloc et en insérant le pointeur dans l'ensemble de toutes les valeurs allouées.

5. Lorsque la taille totale de toutes les valeurs allouées dépasse un quota, les phases de marquage puis de balayage sont lancées. Ceci parcourt récursivement le tas en accumulant l'ensemble de toutes les valeurs atteignables.

6. La différence entre l'ensemble des valeurs allouées moins les valeurs atteignables est l'ensemble des valeurs inaccessibles. Interrogez-les en appelant free et les retirer de l'ensemble des valeurs allouées.

7. Fixez le quota à deux fois la taille totale de toutes les valeurs allouées.

Answer 2

Consultez la page suivante. Elle contient de nombreux liens. http://lua-users.org/wiki/GarbageCollection

Answer 3

Comme l'a suggéré delnan, j'ai commencé par un algorithme très naïf de marque et de balayage tricolore "stop-the-world". J'ai réussi à garder les objets dans les ensembles en les transformant en noeuds de listes liées, mais cela ajoute beaucoup de données à chaque objet (le pointeur virtuel, deux pointeurs vers les noeuds, un enum pour contenir la couleur). Cela fonctionne parfaitement, aucune mémoire perdue sur valgrind :) A partir de là, je pourrais essayer d'ajouter une liste libre pour le recyclage, ou une sorte de chose qui détecte quand il est opportun d'arrêter le monde, ou une approche incrémentale, ou un allocateur spécial pour éviter la fragmentation, ou autre chose. Si vous pouvez m'indiquer où trouver des informations ou des conseils (je ne sais pas si vous pouvez commenter une question à laquelle vous avez répondu) sur la façon de faire ces choses ou sur ce qu'il faut faire, je vous en serais très reconnaissant. En attendant, je vais vérifier le GC de Lua.

Answer 4

J'ai mis en place un Collecteur d'ordures à copie de style Cheney en C dans environ 400 SLOC. Je l'ai fait pour un langage à typage statique et, à ma grande surprise, la partie la plus difficile a été de communiquer l'information sur les choses qui sont des pointeurs et celles qui ne le sont pas. Dans un langage dynamiquement typé, c'est probablement plus facile puisque vous devez déjà utiliser une forme de schéma de balisage.

Il y a aussi une nouvelle version du livre standard sur le garbage collection qui va sortir : "The Garbage Collection Handbook : L'art de la gestion automatique de la mémoire" par Jones, Hosking, Moss . (Le site Amazon UK indique le 19 août 2011).

Answer 5

Une chose que je n'ai pas encore vue mentionnée est l'utilisation de poignées de mémoire. On peut éviter d'avoir à doubler la mémoire (comme cela serait nécessaire avec l'algorithme de copie de style Cheney) si chaque référence d'objet est un pointeur vers une structure qui contient l'adresse réelle de l'objet en question. L'utilisation de handles pour les objets mémoire rendra certaines routines un peu plus lentes (il faut relire l'adresse mémoire d'un objet à chaque fois qu'il se passe quelque chose qui le déplace) mais pour les systèmes monofilaires où la collecte des déchets ne se fait qu'à des moments prévisibles, ce n'est pas un trop gros problème et cela ne nécessite pas de support spécial du compilateur (les systèmes GC multithreads auront probablement besoin de métadonnées générées par le compilateur, qu'ils utilisent des handles ou des pointeurs directs).

Si l'on utilise des handles, et que l'on utilise une liste liée pour les handles vivants (le même stockage peut être utilisé pour contenir une liste liée pour les handles morts nécessitant une réallocation), on peut, après avoir marqué la fiche de chaque handle, parcourir la liste des handles, dans l'ordre d'allocation, et copier le bloc référencé par ce handle au début du tas. Comme les handles seront copiés dans l'ordre, il ne sera pas nécessaire d'utiliser une deuxième zone de tas. De plus, les générations peuvent être supportées en gardant la trace de quelques pointeurs au sommet du tas. Lorsque vous compactez la mémoire, commencez par compacter les éléments ajoutés depuis la dernière GC. Si cela ne libère pas assez d'espace, compactez les éléments ajoutés depuis la dernière GC de niveau 1. Si cela ne libère pas assez d'espace, compactez tout. La phase de marquage devrait probablement agir sur les objets de toutes les générations, mais pas l'étape coûteuse de compactage.

En fait, en utilisant une approche basée sur les poignées, si l'on marque les objets de toutes les générations, on pourrait, si on le souhaite, calculer à chaque passage GC la quantité d'espace qui pourrait être libérée dans chaque génération. Si la moitié des objets de la génération 2 sont morts, il peut être intéressant de faire une collecte de la génération 2 afin de réduire la fréquence des collectes de la génération 1.