Comment un collecteur d'ordures peut-il découvrir les références d'objets faites à partir de la pile ?

Question

Dans les langages avec une collecte automatique des déchets comme Haskell ou Go, comment le collecteur de déchets peut-il savoir quels sont les valeurs stockées sur la pile qui sont des pointeurs vers la mémoire et quels sont simplement des nombres? Si le collecteur de déchets scanne simplement la pile et suppose que toutes les adresses sont des références vers des objets, de nombreux objets pourraient être incorrectement marqués comme accessibles.

Évidemment, on pourrait ajouter une valeur en haut de chaque trame de pile qui décrivait combien des prochaines valeurs sont des pointeurs, mais cela ne coûterait-il pas beaucoup de performance?

Comment cela se fait-il en réalité?

Answer 1

Certains collectionneurs supposent que tout ce qui se trouve sur la pile est un pointeur potentiel (comme Boehm GC). Cela s'avère finalement être moins grave que ce que l'on pourrait penser, mais c'est clairement sous-optimal. Plus souvent dans les langages gérés, des informations de balisage supplémentaires restent avec la pile pour aider le collecteur à déterminer où se trouvent les pointeurs.

Rappelez-vous que dans la plupart des langages compilés, la structure d'une trame de pile est la même à chaque fois que vous entrez dans une fonction, il n'est donc pas si difficile de garantir que vous balisez vos données de la bonne manière.

L'approche "bitmap" est une façon de faire cela. Chaque bit du bitmap correspond à un mot sur la pile. Si le bit est égal à 1, alors l'emplacement sur la pile est un pointeur, et s'il est égal à 0, alors l'emplacement est juste un nombre du point de vue du collecteur (ou quelque chose du genre). Le runtime GHC extrêmement bien écrit et les conventions d'appel utilisent une mise en page d'un mot pour la plupart des fonctions, de telle sorte qu'il suffit de quelques bits pour indiquer la taille de la trame de pile, le reste servant de bitmap. Les trames de pile plus grandes nécessitent une structure multi-mots, mais l'idée est la même.

L'intérêt est que le surcoût est faible, car les informations de mise en page sont calculées à la compilation, puis incluses dans la pile à chaque appel de fonction.

Une approche encore plus simple est le "pointeur en premier", où tous les pointeurs sont situés au début de la pile. Vous n'avez besoin d'inclure qu'une longueur avant les pointeurs, ou un mot "fin" spécial après eux, pour indiquer quels mots sont des pointeurs selon cette disposition.

De manière intéressante, essayer de placer ces informations de gestion sur la pile pose tout un tas de problèmes liés à l'interopérabilité avec le C. Par exemple, il est sous-optimal de compiler des langages de haut niveau en C, car même si le C est portable, il est difficile d'inclure ce type d'informations. Les compilateurs d'optimisation conçus pour des langages de type C (GCC, LLVM) peuvent restructurer la trame de pile, posant des problèmes, donc le backend GHC LLVM utilise sa propre "pile" plutôt que la pile LLVM, ce qui lui fait perdre certaines optimisations. De même, la frontière entre le code C et le code "géré" doit être construite avec soin pour éviter de perturber le GC.

Pour cette raison, lorsque vous créez un nouveau thread sur la JVM, vous créez en réalité deux piles (une pour Java, une pour le C).

Answer 2

La pile Haskell utilise un seul mot de mémoire dans chaque frame de pile décrivant (avec un bitmap) quels sont les valeurs dans cette frame de pile qui sont des pointeurs et lesquelles ne le sont pas. Pour plus de détails, consultez l'article "Disposition de la pile" et l'article "Disposition du bitmap" dans le commentaire GHC.

Pour être honnête, un seul mot de mémoire n'est pas vraiment très coûteux, toutes choses considérées. Vous pouvez le considérer comme l'ajout d'une seule variable à chaque méthode; ce n'est pas si terrible.

Answer 3

Il existe des GC qui supposent que chaque motif de bits qui est l'adresse de quelque chose que le GC gère est en fait un pointeur (et donc ne libèrent pas cette chose). Cela peut fonctionner assez bien en réalité, car les pointeurs sont généralement plus grands que de petits entiers communs, et doivent généralement être alignés. Mais oui, cela peut retarder la collecte de certains objets. Le collecteur Boehm pour C fonctionne ainsi, car il est basé sur une bibliothèque et ne bénéficie donc d'aucune aide spécifique du compilateur.

Il existe aussi des GC qui sont plus étroitement couplés au langage dans lequel ils sont utilisés, et connaissent réellement la structure des objets en mémoire. Je n'ai jamais lu spécifiquement sur la gestion des trames de pile, mais vous pourriez enregistrer des informations pour aider le GC si le compilateur et le GC sont conçus pour travailler ensemble. Une astuce consisterait à regrouper toutes les références de pointeur ensemble et utiliser un mot par trame de pile pour enregistrer combien il y en a, ce qui n'est pas un surcoût important. Si vous pouvez déterminer quelle fonction correspond à chaque trame de pile sans ajouter un mot le spécifiant, vous pourriez avoir une "carte de disposition des trames de pile par fonction" compilée. Une autre option serait d'utiliser des mots étiquetés, où vous définissez le bit d'ordre inférieur des mots qui ne sont pas des pointeurs à 1, ce qui (en raison de l'alignement des adresses) n'est jamais nécessaire pour les pointeurs, donc vous pouvez les distinguer. Cela signifie que vous devez décaler les valeurs non encapsulées pour les utiliser cependant.

Answer 4

Il est important de réaliser que GHC maintient sa propre pile et n'utilise pas la pile C (autre que pour les appels FFI). Il n'y a pas de moyen portable d'accéder à l'ensemble du contenu de la pile C (par exemple, sur un SPARC une partie est cachée dans les fenêtres de registres), donc GHC maintient une pile où il a un contrôle total. Une fois que vous maintenez votre propre pile, vous pouvez choisir n'importe quel schéma pour distinguer les pointeurs des non-pointeurs sur la pile (comme utiliser une bitmap).