Lorsqu'un garbage collector compacte des objets dans le tas, change-t-il les références sur la pile?

18

Cela semble être une question simple, mais après beaucoup de lecture sur le sujet, je n'ai toujours pas trouvé de réponse définitive (peut-être parce que c'est si simple).

Ma question est la suivante: lorsqu'un garbage collector compacte des objets dans le tas, comment les références à ces objets dans la pile sont-elles mises à jour? Je peux penser à deux solutions possibles:

  1. Parcourez la pile (et les références dans le tas) et mettez à jour la référence pour pointer vers le nouvel emplacement de l'objet. Par analogie avec le déménagement, cela reviendrait à envoyer une lettre à toute personne possédant votre adresse et à lui demander de mettre à jour son carnet d'adresses avec votre nouvelle adresse.
  2. Fournissez une sorte de table de recherche. Ce serait comme laisser une adresse de réexpédition au bureau de poste local.

Les éboueurs utilisent-ils principalement l'une de ces deux méthodes? Une autre méthode? Tous les deux?

garbage-collection todorojo
la source
Voir stackoverflow.com/questions/3799203/… et en.wikipedia.org/wiki/…
Gort the Robot
@StevenBurnap me corrige si je me trompe, mais je pense que le fil auquel vous avez lié n'a pas de réponses définitives. Ils semblaient également spéculer sur cette question exacte. J'ai peut-être mal lu. S'ils ont fourni une réponse à la question, si cela ne vous dérange pas, je pense qu'il serait utile de résumer la réponse ici pour les futurs utilisateurs de SE (et moi-même!)
todorojo
Le terme pour la chose dont vous parlez est un "collecteur de déchets en mouvement". Franchement, je ne sais pas à quel point ils sont couramment utilisés.
Gort le robot

Réponses:

9

Je n'ai aucune expertise spécifique à ce sujet, mais je crois comprendre que la première méthode est généralement utilisée.

Le garbage collector doit quand même analyser la pile pour trouver les éléments du tas auxquels la pile fait référence. Une fois qu'il décide de déplacer quelque chose, il doit de toute façon corriger les références, et il n'y a aucune raison de faire la différence entre le tas et la pile à ce stade.

L'approche de la table de consultation pourrait en principe fonctionner. Cependant, cela obligerait tous les accès au pointeur à prendre 2 étapes. Ce serait un impact énorme sur les performances des temps d'exécution normaux. Particulièrement pour le cas d'utilisation de nombreux petits objets. (C'est un cas où les programmes GC de pointe battent généralement le comptage des références.)

btilly
la source
3
J'ajouterais que je pense que les GC essaient probablement de ne pas déplacer les choses sur le tas à moins qu'ils ne le soient. Dans le monde multiprocesseur d'aujourd'hui, cela doit être un cauchemar de synchronisation quand ils doivent mettre à jour toutes les références vers quelque chose sur le tas pendant qu'un programme qui utilise ces références est en cours d'exécution. La table de recherche simplifierait cela, mais je pense que c'est l'exception plutôt que la norme, donc la plupart des GC doivent probablement verrouiller certaines références, déplacer la mémoire, puis mettre à jour les références. +1 Question intéressante, +1 bonne réponse.
GlenPeterson
3
@GlenPeterson De nombreux GC ne déplacent en effet rien sur le tas et ne sont pas confrontés à ce problème. Mais un GC de compactage déplace par définition des objets vivants vers la mémoire de défragmentation.
btilly
@GlenPeterson c'est une bonne observation que déplacer des choses sur le tas est une énorme douleur de synchronisation, cela est souvent ignoré bien que le compactage GC ait d'énormes effets d'entraînement sur un processus en cours d'exécution à cause de cela. C'est la raison la plus importante pour laquelle les gens sont invités à faire tout leur possible pour que les objets restent aussi éphémères que possible, pour éviter les mises à jour de tas volumineuses provoquant le compactage pour contenir un long mutex. L'ignorance de la façon dont ces choses se comportent peut conduire à ce que l'on appelle affectueusement le mode GC Freakout.
Jimmy Hoffa
2
Le Macintosh d'origine et Palm OS ont tous deux utilisé une approche de table de correspondance pour sa gestion de la mémoire. Les pointeurs dans la table étaient appelés poignées. Un GC en relocalisation doit savoir où se trouve absolument positivement chaque référence à un objet qu'il se déplace; l'utilisation d'une seule table à de telles fins simplifie considérablement les choses.
supercat