Est-ce que l'utilisation d'une table de hachage dans la collecte des ordures résoudrait le problème mondial de la marque et du balayage?

Dans l'algorithme de récupération de place mark-sweep-compact, vous devez arrêter le monde lors du déplacement d'objets, car le graphique de référence devient incohérent et vous devez remplacer les valeurs de toutes les références pointant vers l'objet.

Mais que se passe-t-il si vous avez une table de hachage avec l'ID d'objet comme clé et le pointeur comme valeur, et que les références pointent vers cet ID au lieu de l'adresse de l'objet ... est tenté d'être écrit pendant la copie ...

Y a-t-il une erreur dans ma ligne de pensée?

algorithms garbage-collection mrpyo
la source

Réponses:

La mise à jour des références n'est pas la seule chose qui nécessite une pause. Les algorithmes standard généralement regroupés sous «balayage de marque» supposent tous que le graphique d'objet entier reste inchangé pendant qu'il est marqué. La gestion correcte des modifications (nouveaux objets créés, références modifiées) nécessite des algorithmes alternatifs plutôt délicats, comme l'algorithme tricolore. Le terme générique est "collecte de déchets simultanée".

Mais oui, la mise à jour des références après compactage nécessite également une pause. Et oui, l'utilisation de l'indirection (par exemple via un ID d'objet persistant et une table de hachage vers des pointeurs réels) peut réduire considérablement la pause. Il pourrait même être possible de rendre cette pièce sans verrou si l'on le souhaite. Il serait toujours aussi délicat de réussir que n'importe quelle concurrence de mémoire partagée de bas niveau, mais il n'y a aucune raison fondamentale pour laquelle cela ne fonctionnerait pas.

Cependant , cela aurait de graves inconvénients. En plus de prendre de l'espace supplémentaire ( au moins deux mots supplémentaires pour tous les objets), cela rend chaque déréférence beaucoup plus chère. Même quelque chose d'aussi simple que d'obtenir un attribut implique désormais une recherche de table de hachage complète. J'estimerais que les performances atteintes sont bien pires que pour le suivi incrémentiel.

la source

Eh bien, nous avons beaucoup de mémoire aujourd'hui, donc nous pourrions avoir disons une table de 50 Mo et le hachage pourrait être un simple modulo, donc une seule instruction ...

mrpyo

@mrpyo récupérant la taille de la table de hachage, opération modulo, déréférence par rapport au décalage de la table de hachage pour obtenir le pointeur d'objet réel, déréférence à l'objet lui-même. De plus, certains enregistrements peuvent être mélangés. Nous nous retrouvons à 4+ instructions. De plus, ce schéma a des problèmes concernant la localisation de la mémoire: maintenant, la table de hachage et les données elles-mêmes doivent tenir dans le cache.

amon

@mrpyo Vous avez besoin d'une entrée (ID d'objet -> adresse actuelle) par objet, non? Et quel que soit le prix de la fonction de hachage, vous aurez des collisions et devrez les résoudre. Aussi ce qu'a dit amon.

@amon ce n'est qu'une question de temps avant que les processeurs aient 50 Mo ou plus de cache :)

Móż

@ Ӎσᶎ Au moment où nous pouvons mettre 50 Mio de transistors sur une puce et avoir encore une latence suffisamment faible pour qu'elle fonctionne comme cache L1 ou L2 (les caches L3 ont déjà une taille allant jusqu'à 15 Mio, mais généralement AFAIK hors puce et loin) pire latence que L1 et L2), nous aurons en conséquence des quantités massives de mémoire principale (et de données à y mettre). La table ne peut pas être de taille fixe, elle doit grandir avec le tas.

Tous les problèmes en informatique peuvent être résolus par un autre niveau d'indirection… sauf le problème de trop de couches d'indirection

Votre approche ne résout pas immédiatement le problème du ramasse-miettes, mais ne le fait monter que d'un niveau. Et à quel prix! Désormais, chaque accès à la mémoire passe par une autre déréférence de pointeur. Nous ne pouvons pas mettre en cache l'emplacement du résultat, car il pourrait avoir été déplacé entre-temps, nous devons toujours passer par l'ID d'objet. Dans la plupart des systèmes, cette indirection n'est pas acceptable et l'arrêt du monde est supposé avoir un coût d'exécution total inférieur.

J'ai dit que votre proposition ne fait que déplacer le problème, pas le résoudre. Le problème concerne la réutilisation des ID d'objet. Les ID d'objet sont maintenant notre équivalent de pointeurs, et il n'y a qu'une quantité finie d'adresses. Il est concevable (en particulier sur un système 32 bits) que pendant la durée de vie de votre programme, plus de INT_MAX objets aient été créés, par exemple dans une boucle comme

while (true) {
    Object garbage = new Object();
}

Si nous incrémentons simplement l'ID d'objet pour chaque objet, nous manquerons d'ID à un moment donné. Par conséquent, nous devons savoir quels identifiants sont encore utilisés et lesquels sont gratuits pour pouvoir être récupérés. Semble familier? Nous sommes maintenant de retour à la case départ.

amon
la source

On peut probablement utiliser des identifiants qui sont juste «assez grands», par exemple des bignums de 256 bits? Je ne dis pas que cette idée est bonne dans l'ensemble, mais vous pouvez presque certainement contourner la réutilisation des IDS.

Vality

@Vality réaliste oui - pour autant que nous puissions voir cela contournerait le problème de la réutilisation des identifiants. Mais ce n'est qu'un autre argument "640K devrait être suffisant pour n'importe qui", et ne résout pas réellement le problème. Un aspect plus catastrophique est que la taille de tous les objets (et la table de hachage) devrait augmenter pour accueillir ces pseudo-pointeurs surdimensionnés, et que pendant l'accès de hachage, nous devons comparer ce bigint à d'autres ID qui monopoliseront probablement plusieurs registres et prenez plusieurs instructions pour terminer (sur 64 bits: 8 × charge, 4 × comparer, 3 × et ce qui représente une augmentation de 5 × par rapport aux nombres natifs).

amon

Ouais, vous seriez à court d'ID après un certain temps et devrez tous les changer, ce qui nécessiterait une pause. Mais ce serait peut-être un événement rare ...

mrpyo

@amon Tout à fait d'accord, tous de très bons points là-bas, il vaut mieux avoir un système véritablement durable, je suis d'accord. Cela va être insupportablement lent, quoi que vous fassiez, ce n'est de toute façon intéressant qu'en théorie. Personnellement, je ne suis pas un grand fan des ramasseurs de déchets de toute façon: P

Vality

@amon: il y a plus de code dans le monde que cela pourrait mal tourner une fois que vous avez encapsulé un ID 64 bits (584 ans de nanosecondes, et vous pouvez probablement faire en sorte que l'allocation de mémoire prenne 1ns, surtout si vous ne partagez pas le compteur global qui crache les identifiants!). Mais bien sûr, si vous n'avez pas besoin de vous y fier, vous ne le faites pas.

Steve Jessop du

Il n'y a pas d'erreur dans votre ligne de pensée, vous venez de décrire quelque chose de très proche du fonctionnement du garbage collector Java d'origine

La machine virtuelle Java d'origine [6] et certaines machines virtuelles Smalltalk utilisent des pointeurs indirects, appelés poignées dans [6], pour faire référence aux objets. Les poignées permettent de déplacer facilement les objets pendant le ramassage des ordures car, avec les poignées, il n'y a qu'un seul pointeur direct vers chaque objet: celui dans sa poignée. Toutes les autres références à l'objet indirectes à travers la poignée. Dans de tels systèmes de mémoire basés sur des descripteurs, alors que les adresses des objets changent au cours de la durée de vie des objets et ne peuvent donc pas être utilisées pour le hachage, les adresses des descripteurs restent constantes.

Hachage efficace en termes d'espace et de temps des objets récupérés

Dans l'implémentation actuelle de Sun de la machine virtuelle Java, une référence à une instance de classe est un pointeur vers un handle qui est lui-même une paire de pointeurs: un vers une table contenant les méthodes de l'objet et un pointeur vers l'objet Class qui représente le type de l'objet, et l'autre à la mémoire allouée à partir du tas Java pour les données d'objet.

La spécification de la machine virtuelle Java (1997)

Donc ça marche, ça a été essayé, et son inefficacité a conduit au développement de systèmes générationnels de marquage et de balayage.

Pete Kirkham
la source

Vraisemblablement, ces poignées n'étaient pas des clés dans une table de hachage (comme dans la question), cependant? Il n'y a pas besoin, juste une structure contenant un pointeur. Ensuite, les poignées sont toutes de la même taille afin qu'elles puissent être allouées à partir d'un allocateur de tas. Qui, par nature, n'a pas besoin de compactage interne car il ne se fragmente pas. Vous pourriez pleurer l'incapacité des gros blocs utilisés par cet allocateur à être eux-mêmes déplacés. Ce qui peut être résolu par un autre niveau d'indirection ;-)

Steve Jessop

@SteveJessop oui, il n'y avait pas de table de hachage dans l'implémentation de gc, bien que la valeur du handle soit également la valeur renvoyée parObject.getHashCode()

Pete Kirkham