Comment les ramasseurs de déchets évitent-ils les débordements de pile?

23

Je pensais donc au fonctionnement des ramasseurs d'ordures et j'ai pensé à un problème intéressant. Vraisemblablement, les ramasseurs d'ordures doivent traverser toutes les structures de la même manière. Ils ne peuvent pas savoir le temps qu'ils parcourent une liste chaînée ou un arbre équilibré ou autre. Ils ne peuvent pas non plus utiliser trop de mémoire dans leur recherche. Une façon possible, et la seule façon que je puisse penser de parcourir TOUTES les structures, pourrait être de les parcourir toutes de manière récursive comme vous le feriez pour un arbre binaire. Cela donnerait cependant un débordement de pile sur une liste chaînée ou même juste un arbre binaire mal équilibré. Mais toutes les langues récupérées que j'ai jamais utilisées semblent n'avoir aucun problème à gérer de tels cas.

Dans le livre des dragons, il utilise une sorte de file d'attente "Non scanné". Fondamentalement, plutôt que de parcourir la structure de manière récursive, il ajoute simplement des choses qui doivent être marquées dans une file d'attente, puis pour chaque chose non marquée à la fin, il est supprimé. Mais cette file d'attente ne deviendrait-elle pas très grande?

Alors, comment les ramasseurs de déchets traversent-ils des structures arbitraires? Comment cette technique de traversée évite-t-elle le débordement?

Jake
la source
1
GC traverse toutes les structures plus ou moins de la même manière, mais seulement dans un sens très abstrait (voir réponse). La façon dont ils suivent concrètement les choses est beaucoup plus sophistiquée que ne l'indiquent les présentations élémentaires que vous pouvez trouver dans les manuels. Et ils n'utilisent pas la récursivité. De plus, avec la mémoire virtuelle, les mauvaises implémentations apparaissent comme un ralentissement du GC, rarement comme un dépassement de mémoire.
babou
Vous vous inquiétez de l'espace nécessaire pour le traçage. Mais qu'en est-il de l'espace ou des structures nécessaires pour distinguer la mémoire qui a été tracée et qui est connue pour être utilisée, de la mémoire qui est potentiellement récupérable. Cela peut avoir un coût de mémoire important, éventuellement proportionnel à la taille du tas.
babou
Je pensais que ce serait fait avec un bitvector sur une taille d'objet supérieure à 16 octets environ, de sorte que la surcharge serait 1000 fois moins au minimum.
Jake
Il existe de nombreuses façons de le faire (voir réponse), et ils peuvent également être utilisés pour le traçage, qui répondrait alors à votre question (des vecteurs ou des bitmaps peuvent être utilisés pour le traçage, plutôt que la pile ou la file d'attente que vous proposez). Vous ne pouvez pas supposer que tous les objets sont gros, sauf si vous avez l'intention de gaspiller de l'espace sur de petits objets, dont il peut y en avoir beaucoup, et alors vous ne devriez pas vous soucier de l'espace. Si vous êtes dans la mémoire virtuelle, l'espace est souvent beaucoup moins un problème et les problèmes sont très différents.
babou

Réponses:

13

Notez que je ne suis pas un expert en collecte de déchets. Cette réponse ne donne que des exemples de techniques. Je ne prétends pas qu'il s'agit d'un aperçu représentatif des techniques de collecte des ordures.

Une file d'attente non analysée est un choix courant. La file d'attente peut devenir volumineuse - potentiellement aussi grande que la structure de données la plus profonde. La file d'attente est généralement stockée explicitement, pas sur la pile du thread de récupération de place.

Une fois que tous les enfants d'un nœud sauf un ont été analysés, le nœud peut être supprimé de la file d'attente non analysée. Il s'agit essentiellement d'une optimisation des appels de queue. Les récupérateurs de place peuvent inclure des heuristiques pour tenter d'analyser en dernier l'enfant le plus profond d'un nœud; par exemple doit analyser le GC pour un Lisp card'un consavant cdr.

Une façon d'éviter de conserver une file d'attente non analysée consiste à modifier les pointeurs en place, en faisant en sorte que l'enfant pointe temporairement vers le parent. Il s'agit d'une technique de traversée d'arbre à mémoire constante qui est utilisée dans des contextes autres que les récupérateurs de place. L'inconvénient de cette technique est que pendant que le GC traverse une structure de données, la structure de données n'est pas valide, donc le GC doit arrêter le monde. Ce n'est pas un casse-tête: de nombreux ramasseurs de déchets incluent une phase qui arrête le monde, en plus de phases qui ne le font pas mais peuvent manquer des déchets en conséquence.

Gilles 'SO- arrête d'être méchant'
la source
2
La technique décrite dans le dernier paragraphe est souvent appelée « inversion du pointeur ».
Wandering Logic
@WanderingLogic Oui, l' inversion du pointeur est la façon dont je l'ai appelé dans ma propre réponse. Elle est due à Deutsch, Schorr et Waite (1967). Cependant, il est incorrect de déclarer qu'il fonctionne en mémoire constante: il nécessite des bits supplémentaires pour chaque cellule avec pointeurs, bien que cela puisse être réduit en utilisant des piles de bits. La réponse acceptée à laquelle vous faites référence n'est pas tout à fait correcte ou complète non plus pour la même raison. pbûche2pp
babou
Je l' ai utilisé l' inversion de pointeur dans un GC personnalisé sans avoir besoin de ces bits supplémentaires; l'astuce était d'utiliser une représentation spéciale en mémoire des objets en mémoire. A savoir, l'objet "en-tête" était au milieu, avec des champs de pointeur avant l'en-tête et des champs sans pointeur après; de plus, tous les pointeurs étaient alignés et l'en-tête comprenait un champ avec le bit le moins significatif toujours défini. Ainsi, pendant la marche arrière de l'inversion du pointeur, atteindre le pointeur suivant et remarquer que nous avions terminé avec un objet pouvait être fait sans ambiguïté sans les bits supplémentaires. Cette disposition prend également en charge l'héritage OOP.
Thomas Pornin
@ThomasPornin Je pense que les informations doivent être quelque part. La question est où? Pouvons-nous en discuter dans le chat? Je dois partir maintenant, mais j'aimerais aller au fond des choses. Ou existe-t-il une description accessible sur le Web?
babou
1
@babou et Thomas please
Gilles 'SO- stop being evil'
11

En résumé : les récupérateurs n'utilisent pas la récursivité. Ils contrôlent simplement le traçage en conservant essentiellement deux ensembles (qui peuvent se combiner). L'ordre de traçage et de traitement des cellules est sans importance, ce qui donne une liberté d'implémentation considérable pour représenter les ensembles. Par conséquent, il existe de nombreuses solutions qui sont en fait très bon marché dans l'utilisation de la mémoire. Ceci est essentiel car le GC est appelé précisément lorsque le tas manque de mémoire. Les choses sont un peu différentes avec de grandes mémoires virtuelles, car les nouvelles pages peuvent être facilement allouées, et l'ennemi n'est pas le manque d'espace, mais le manque de localisation des données .

Je suppose que vous envisagez de rechercher les récupérateurs, et non de compter les références pour lesquelles votre question ne semble pas s'appliquer.

UV

La première chose à noter est que tous les GC de traçage suivent le même modèle abstrait, basé sur l'exploration systématique du graphe dirigé de cellules en mémoire accessible depuis le programme, où les cellules mémoire sont des sommets et des pointeurs sont les bords dirigés. Il utilise pour cela les ensembles suivants:

  • VVV=UT

  • U

  • T

  • H

VUUT

UV

UcVUcUT

UUV=TVH-VV

VUUT

Je saute également des détails sur ce qu'est une cellule, qu'elle existe en une ou plusieurs tailles, comment nous y trouvons des pointeurs, comment ils peuvent être compactés et une foule d'autres problèmes techniques que vous pouvez trouver dans des livres et des enquêtes sur la collecte des ordures. .

U

Là où les implémentations connues diffèrent, c'est dans la façon dont ces ensembles sont réellement représentés. De nombreuses techniques ont été effectivement utilisées:

  • bitmap: Un espace mémoire est conservé pour une carte qui a un bit pour chaque cellule de mémoire, qui peut être trouvé en utilisant l'adresse de la cellule. Le bit est activé lorsque la cellule correspondante est dans l'ensemble défini par la carte. Si seules des mappes de bits sont utilisées, vous n'avez besoin que de 2 bits par cellule.

  • Alternativement, vous pouvez avoir de l'espace pour un bit d'étiquette spécial (ou 2) dans chaque cellule pour le marquer.

  • bûche2pp

  • vous pouvez tester un prédicat sur le contenu de la cellule et ses pointeurs.

  • vous pouvez déplacer la cellule dans une partie libre de la mémoire destinée à toutes et uniquement aux cellules appartenant à l'ensemble représenté.

  • VTTU

  • vous pouvez réellement combiner ces techniques, même pour un seul ensemble.

Comme dit, tout ce qui précède a été utilisé par certains ramasse-miettes mis en œuvre, aussi étrange que cela puisse paraître. Tout dépend des différentes contraintes de l'implémentation. Et ils peuvent être plutôt bon marché dans l'utilisation de la mémoire, peut-être aidés par le traitement des politiques de commande qui peuvent être librement choisies à cet effet, car elles n'ont pas d'importance pour le résultat final.

Ce qui peut sembler le plus étrange, le transfert de cellules dans une nouvelle zone, est en fait très courant: il s'agit de la collection de copies. Il est principalement utilisé avec la mémoire virtuelle.

De toute évidence, il n'y a pas de récursivité et la pile d'algorithmes de mutation n'a pas à être utilisée.

Un autre point important est que de nombreux GC modernes sont implémentés pour les grandes mémoires virtuelles . Ensuite, obtenir de l'espace pour implémenter et une liste ou une pile supplémentaire n'est pas un problème car les nouvelles pages peuvent être facilement allouées. Cependant, dans les grands souvenirs virtuels, l'ennemi n'est pas le manque d'espace mais le manque de localité . Ensuite, la structure représentant les ensembles, et leur utilisation, doit être orientée vers la préservation de la localité de la structure des données et de l'exécution du GC. Le problème n'est pas l'espace mais le temps. Des implémentations inadéquates sont plus susceptibles de montrer un ralentissement inacceptable qu'un débordement de mémoire.

Je n'ai pas fait référence aux nombreux algorithmes spécifiques, résultant de diverses combinaisons de ces techniques, car cela semble assez long.

babou
la source
4

La manière standard d'éviter un débordement de pile consiste à utiliser une pile explicite (stockée en tant que structure de données dans le tas). Cela fonctionne également à ces fins. Les éboueurs ont souvent une liste de travail des éléments qui doivent être examinés / parcourus, ce qui remplit ce rôle. Par exemple, votre file d'attente "Non analysé" est un exemple exact de ce type de modèle. La file d'attente peut potentiellement devenir volumineuse, mais elle ne provoque pas de débordement de pile, car elle n'est pas stockée dans le segment de pile. Dans tous les cas, il ne dépassera jamais le nombre d'objets vivants dans le tas.

DW
la source
Lorsque le GC est appelé, le tas est généralement plein. Un autre point est qu'il arrive que la pile et le tas se développent aux deux extrémités du même espace mémoire ..
babou
4

Dans des descriptions «classiques» de la collecte des ordures (par exemple, Mark Wilson, « Uniprocessor Garbage Collection Techniques », Int'l Workshop on Memory Management , 1992, ( lien alternatif ), ou la description dans Andrew Appel's Modern Compiler Implementation (Cambridge University Press, 1998)), les collectionneurs sont classés comme «Mark and Sweep» ou «Copying».

Les collectionneurs Mark et Sweep évitent d'avoir besoin d'espace supplémentaire en utilisant l'inversion du pointeur, comme décrit dans la réponse de @ Gilles. Appel dit que Knuth attribue l'algorithme d'inversion du pointeur à Peter Deutsch, à Herbert Schorr et WM Waite.

Les récupérateurs de copie utilisent ce que l'on appelle souvent l'algorithme de Cheyney pour effectuer une traversée de file d'attente sans avoir besoin d'espace supplémentaire. Cet algorithme a été introduit dans CJ Cheyney, "A Non Recursive List Compacting Algorithm", Comm. ACM , 13 (11): 677-678, 1970.

Dans un garbage collector de copie, vous avez un bloc de mémoire que vous essayez de collecter, appelé depuis l'espace , et un bloc de mémoire que vous utilisez pour les copies appelées dans l' espace . L'espace vers est organisé comme une file d'attente avec un scanpointeur pointant vers l'enregistrement copié mais non analysé le plus ancien, et un freepointeur pointant vers la position libre suivante dans l'espace. L'image de ceci de l'article de Wilson est:

Exemple d'algorithme de Cheyney

Lorsque vous numérisez chaque élément dans l'espace, vous copiez ses enfants de l'espace vers le freepointeur dans l'espace, puis modifiez le pointeur sur l'enfant de l'espace vers la nouvelle copie de l'enfant dans l'espace. Il existe une astuce supplémentaire que vous devez utiliser lorsque vos structures de données ne sont pas des arbres (lorsqu'un enfant peut avoir plusieurs parents). Dans ce cas, lorsque vous copiez un enfant d'un espace à l'autre, vous devez remplacer l'ancienne version de l'enfant par un pointeur de transfert vers la nouvelle copie de l'enfant. Ensuite, si vous scannez un autre pointeur vers l'ancienne version de l'enfant, vous vous rendez compte qu'il a déjà été copié et ne le copiez plus.

Logique errante
la source
En fait, comme expliqué dans ma réponse, Mark + Sweep et Copy collection sont le même algorithme de graphe abstrait. Les collections MS et Copy ne diffèrent que par la façon dont les ensembles utilisés par l'algorithme abstrait sont implémentés, et les deux familles sont incluses, avec de nombreuses variantes, dans une combinaison des techniques d'implémentation des ensembles que je décris dans ma réponse. Certaines variantes de GC mélangent en fait MS et Copy dans le même GC. La séparation de MS et de Copy est considérée par certains comme un moyen pratique de structurer les livres, mais c'est une vision arbitraire, et je pense dépassée.
babou
@babou: Si l'on utilise un algorithme de copie dans lequel tout ce qui est visité sera copié (lent, mais peut être utile sur de petites plates-formes où le jeu de travail n'est jamais si grand), certains algorithmes peuvent être quelque peu simplifiés car on peut utiliser la mémoire autrefois occupée par un objet déplacé comme un bloc-notes. On peut également gagner une capacité limitée pour que d'autres threads effectuent des accès en lecture seule aux objets pendant la collecte à condition de vérifier la validité de l'objet avant et après chaque lecture, et de suivre le pointeur de transfert si un objet a été déplacé.
supercat
@supercat Je ne sais pas trop ce que vous essayez de dire, quelle est votre intention. Certaines de vos déclarations semblent correctes. Mais je ne comprends pas comment vous pouvez utiliser depuis l'espace avant la fin du cycle GC (il contient des pointeurs de transfert). Et ce serait un bloc-notes pour quoi? Simplifiez l'algorithme comment? En ce qui concerne plusieurs threads de mutation exécutés pendant que GC est en cours, il s'agit en grande partie d'un problème orthogonal, bien qu'il puisse avoir un impact sévère sur la mise en œuvre. Je n'essaierais pas de répondre à cela dans les commentaires. Cela devrait poser moins de problèmes d'accès en lecture seule, mais le diable est dans les détails.
babou