Comment mettre en œuvre un garbage collector?
Quelqu'un pourrait-il m'indiquer une bonne source d'information sur la façon de mettre en œuvre la collecte des ordures? Je fais un lisp comme langage interprété. Il utilise actuellement le comptage de référence, bien sûr mais qui ne parvient pas à libérer de façon circulaire les objets dépendants.
J'ai lu de la marque et de balayage, tricolore marquage, le déplacement et ne bouge pas, incrémentale et cessez-le-monde, mais... je ne sais pas quelle est la meilleure façon de garder les objets soigneusement séparés dans les jeux tout en gardant par-objet de surcharge de mémoire au minimum, ou comment faire les choses progressivement.
J'ai lu plusieurs langues avec de comptage de référence utilisation de la circulaire de référence de détection, que je pourrais utiliser. Je suis conscient que je pourrais utiliser librement disponible collectionneurs comme Boehm, mais je voudrais apprendre à le faire moi-même.
Je vous serais reconnaissant de tout matériel en ligne avec une sorte de tutoriel ou de l'aide pour les personnes n'ayant aucune expérience sur le sujet comme moi.
- secure.wikimedia.org/wikipedia/en/wiki/...
- Il ne faut pas commencer avec quelque chose de plus complexe qu'un proche-braindead cessez-le-monde marque et de balayage collector. Oubliez les jeux différentiels, des collections et des trucs du genre pour l'instant. Obtenir les racines, obtenir une liste de tous les objets vivants, etc. sera un défi suffisant pour votre premier essai.
- Et plus précisément, les "stratégies de mise en œuvre de la section": secure.wikimedia.org/wikipedia/en/wiki/...
- double possible de l'Apprentissage de la collecte des ordures de la théorie
- Je ne suis pas d'accord que c'est un doublon. Que l'on est sur de la théorie, c'est sur la mise en œuvre et des tutoriels.
- Vous voulez apprendre à faire de la collecte des ordures, à droite? Parce que sinon, il vous suffit d'utiliser Boehm-Demers-Weiser excellent conservateur garbage collector au moins jusqu'à ce que la langue est bien établie et a des applications réelles, à la mettre en valeur, parce que, jusqu'alors, il y a des choses plus urgentes que le petit morceau de performance que l'on peut extraire d'un gc.
Vous devez vous connecter pour publier un commentaire.
Il y a beaucoup de matériaux avancés à propos de la collecte des ordures là-bas. Le La Collecte Des Ordures Manuel est grande. Mais j'ai trouvé qu'il y avait très peu de base de l'information d'introduction j'ai donc écrit quelques articles à ce sujet. Le prototype d'un mark-sweep garbage collector décrit un minimum de mark-sweep GC écrit en F#. Le Très Simultanées Garbage Collector décrit un plus avancées simultanées collector. HLVM est une machine virtuelle que j'ai écrit qui comprend un cessez-le-monde collecteur qui gère le filetage.
La façon la plus simple à mettre en œuvre un garbage collector est:
Assurez-vous que vous pouvez rassembler les racines globales. Ce sont des variables locales et globales qui contiennent des références dans le tas. Pour les variables locales, les pousser à l'ombre de la pile pour la durée de leur champ d'application.
Assurez-vous que vous pouvez traverser le tas, par exemple, chaque valeur dans le tas est un objet qui implémente un
Visit
méthode qui retourne toutes les références de cet objet.Garder l'ensemble de toutes les valeurs qui lui sont attribués.
Allouer en appelant
malloc
et en insérant le pointeur dans l'ensemble de toutes les valeurs qui lui sont attribués.Lorsque la taille totale de toutes les valeurs attribuées dépasse un quota, le coup d'envoi de la marque, puis de balayage phases. De cette manière récursive traverse le tas d'accumulation de l'ensemble de tous accessibles valeurs.
La différence entre les valeurs attribuées moins accessibles valeurs est l'ensemble des inaccessible valeurs. Itérer sur eux d'appeler
free
et de les enlever de l'ensemble de valeurs qui lui sont attribués.Définir le quota de deux fois la taille totale de toutes les valeurs qui lui sont attribués.
Découvrez la page suivante. Il a de nombreux liens. http://lua-users.org/wiki/GarbageCollection
Comme suggéré par delnan, j'ai commencé avec un très naïf cessez-le-monde tri-couleur de la marque et de balayage de l'algorithme. J'ai réussi à garder les objets dans les décors en les rendant lié liste de nœuds, mais il ajoute beaucoup de données pour chaque objet (le virtuel pointeur, deux pointeurs vers les nœuds, un enum pour tenir la couleur). Il fonctionne parfaitement, sans aucun souvenir perdu sur valgrind 🙂 De là, je pourrais essayer d'ajouter une liste d'espace libre pour le recyclage, ou une sorte de chose qui détecte le moment où il convient d'arrêter le monde, ou une approche progressive, ou un allocateur pour éviter la fragmentation, ou quelque chose d'autre. Si vous pouvez m'indiquer où trouver des infos ou des conseils (je ne sais pas si vous pouvez faire un commentaire sur une répondu à la question) sur la façon de faire ces choses ou quoi faire, je lui en serais très reconnaissant. Je vais vérifier Lua du GC dans le temps.
J'ai mis en place un Cheney style de la copie de garbage collector dans C à environ 400 SLOC. Je l'ai fait pour un statiquement typé langue et, à ma grande surprise, la partie la plus difficile est en fait la communication des informations dont les choses sont des pointeurs et des choses qui ne le sont pas. Dans un typées dynamiquement la langue c'est probablement plus facile puisque vous devez déjà utiliser une certaine forme de système d'identification.
Il y a également une nouvelle version de la norme livre sur la collecte des ordures coming out: "La Collecte des Ordures Manuel: l'Art de La Gestion Automatique de la Mémoire" par Jones, Hosking, de la Mousse. (L'Amazon UK lieu dit le 19 Août 2011.)
Une chose que je n'ai pas encore vu mentionné, c'est l'utilisation de poignées de mémoire. On peut éviter le besoin de double-up sur la mémoire (comme cela serait nécessaire avec l'Cheney style de la copie de l'algorithme) 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'aide des poignées pour les objets de la mémoire va rendre certaines routines un peu plus lent (il faut relire l'adresse mémoire d'un objet à tout moment, quelque chose s'est produit qui aurait le déplacer), mais pour single-threaded les systèmes où la collecte des ordures ne se fait à des moments prévisibles, ce n'est pas trop un problème et de ne pas nécessiter la prise en charge du compilateur (multi-threaded GC systèmes sont susceptibles d'exiger généré par le compilateur de métadonnées qu'ils utilisent des poignées ou diriger des pointeurs).
Si l'on utilise des poignées, et utilise une liste chaînée pour vivre poignées (le même système de stockage peut être utilisé pour tenir une liste chaînée pour mort poignées besoin de réaffectation), on peut, après marquage de la fiche pour chaque manche, passez par la liste des poignées, dans l'ordre d'allocation, et de copier le bloc visé par cette poignée pour le début de la tas. Parce que les poignées seront copiés dans l'ordre, il n'y aura pas besoin d'utiliser un deuxième segment de la zone. En outre, les générations peuvent être pris en charge en gardant la trace de certains haut-de-tas de pointeurs. Lorsque compactifying de la mémoire, tout d'abord commencer par compactifying éléments ajoutés depuis la dernière GC. Si cela ne suffit pas à libérer suffisamment d'espace, compactify éléments ajoutés depuis la dernière niveau 1 GC. Si cela ne suffit pas à libérer suffisamment d'espace, compactify tout. La phase de marquage serait probablement à agir sur les objets de toutes les générations, mais le cher compactifying stade ne serait pas.
En fait, à l'aide d'une poignée de base de l'approche, si l'on est de marquage des choses de toutes les générations, on peut, si désiré, de calcul sur chaque GC passer la quantité d'espace qui pourrait être libéré dans chaque génération. Si la moitié des objets dans Gen2 sont morts, il peut être utile de faire un Gen2 collection de manière à réduire la fréquence des Gen1 collections.
De collecte des ordures de la mise en œuvre en Lisp
Bâtiment LISP | http://www.lwh.jp/lisp/
Arcadia | https://github.com/kimtg/arcadia
Lire Gestion de la mémoire: Algorithmes et Implémentations en C/C++. C'est un bon endroit pour commencer.
Je suis en train de faire un travail similaire pour mon interpréteur postscript. plus d'infos via ma question. Je suis d'accord avec Delnan commentaire qu'une simple marque de balayage de l'algorithme est un bon endroit pour commencer. Vous aurez besoin des fonctions pour définir la marque de coche, clair-marque, et les itérateurs pour tous vos récipients. Une simple optimisation est clairement une marque à chaque fois que l'allocation d'un nouvel objet, et clair-marque pendant le balayage; sinon, vous aurez besoin d'un ensemble de passer à des marques claires avant de commencer à les fixer.