Informatique

Salut, je lisais des trucs sur les garbages collectors et leur fonctionnement.

J'ai vu qu'un moyen d'identifier les objets qui ne sont plus accessibles c'était via le tri-color marking, notamment parce que ça permettait de marquer les objets de manière itérative plutôt que de parcourir tout l'arbre de références d'un coup.

Mais je comprends pas ce système itératif en fait, supposons un graph comme ça :

     A
     |
     v
B -> C -> D

Actuellement tous les nœuds sont noirs, parce que accessibles depuis les nœuds A et B à la racine.

Si je supprime le lien de B -> C, il se passe quoi ?

Ce à quoi j'avais pensé c'est que quelque part il y a une liste de tous les objets qui ont une référence vers C, donc le garbage collector marque les objets référencés par C en blanc, et les objets qui référencent C en gris (s'ils sont pas déjà blanc), le tout récursivement sur tous les objets qui ont été colorés en blanc.

Le truc c'est que ce que je dis est possible que si le garbage collector a la liste des objets référant un objet, sinon il faut parcourir tout l'arbre de références et c'est plus itératif.

La deuxième question par rapport à ça c'est que certains garbage collector vont copier des objets de temps en temps histoire de défragmenter la mémoire, mais ça veut dire que toutes les références à ces objets deviennent invalides. J'ai vu qu'une solution utilisée était de "simplement" mettre à jour toutes les références pour pointer vers l'adresse du nouvel objet, mais c'est fait comment ? Tout l'arbre de références est parcouru ou alors (encore une fois) le garbage collector connait la liste des objets référant un objet et donc peut mettre à jour ces références de manière optimale car il connaît la liste précise des objets à modifier ?
Une autre solution serait que les références pointent pas directement sur l'adresse système de l'objet, mais sur une adresse virtuelle gérée par le garbage collector et que lui ferait le lien "adresse locale au garbage collector" -> "adresse système", mais je sais pas si c'est viable de rajouter encore un niveau d'indirection supplémentaire pour accéder aux objets.

Je ne comprends pas ce que tu veux dire par itératif. Tu veux dire incrémental?

Je pense que cet algo de garbage collection est incrémental pour les operations d'addition d'arrête, mais pas pour les opérations d'éffacement d'arrête. Une fois que l'algo est stable (il n'y a plus de noeud gris), tu es garanti qu'il n'y a pas blanc qui soit atteignable depuis les racines. Mais c'est possible qu'il y ait des noeuds noirs qui ne soient plus atteignable.

J'imagine que l'algo tourne continuellement en arrière plan et une fois qu'il a fini sa passe, il recommence depuis le debut. (la deuxieme question dans le poste d'apres)

Une autre solution serait que les références pointent pas directement sur l'adresse système de l'objet, mais sur une adresse virtuelle gérée par le garbage collector et que lui ferait le lien "adresse locale au garbage collector" -> "adresse système", mais je sais pas si c'est viable de rajouter encore un niveau d'indirection supplémentaire pour accéder aux objets.

C'est ca que font les systemes qui font de l'optimisation de placement memoire. La reference est juste une entree dans une table de hashage qui pointe a l'addresse physique de l'objet. Du fait tu peux migrer les objets dans l'espace memoire sans avoir besoin de changer les references.

Si ca a l'air de couter une indirection de plus a chaque dereferenement d'objet, c'est parceque ca coute une indirection de plus a chaque dereferencement d'objet.

En pratique c'est optimisable dans plein de cas. Tu pourrais imagine qu'il y a un bit dans l'objet qui dit "je garde une addresse physique de cet objet, alors ne le deplace pas" qui peut etre utilise par les code qui ont des boucles courte. Ou alors tu peux imagine que les objets sont deplace par section. Tu prends un RWlock sur tous les objet dont la reference est de 14 modulo 10000. Et tous les autres threds peuvent travailler sur les addresse en memoire virtuelle des objets dont la reference n'est pas 14 modulo 10000.

[17:48:55] <godrik>
Je ne comprends pas ce que tu veux dire par itératif. Tu veux dire incrémental?

Ah oui, je me suis trompé de mot.

[17:54:37] <godrik>
Je pense que cet algo de garbage collection est incrémental pour les operations d'addition d'arrête, mais pas pour les opérations d'éffacement d'arrête. Une fois que l'algo est stable (il n'y a plus de noeud gris), tu es garanti qu'il n'y a pas blanc qui soit atteignable depuis les racines. Mais c'est possible qu'il y ait des noeuds noirs qui ne soient plus atteignable.

J'imagine que l'algo tourne continuellement en arrière plan et une fois qu'il a fini sa passe, il recommence depuis le debut. (la deuxieme question dans le poste d'apres)

Ah effectivement t'as raison : https://stackoverflow.com/questions/2364274/tri-color-incremental-updating-gc-does-it-need-to-scan-each-stack-twice#2365606

En fait s'il est incrémental c'est parce que la traversée peut être mise en pause et reprise plus tard. Du coup effectivement a la fin de la traversé il y aura potentiellement des objets noirs qui ne seront plus atteignables (ils l'étaient quand ils ont été colorés, mais comme d'autres objets ont été modifiés depuis ils peuvent ne plus l'être maintenant), mais tu es garanti que tous tes objets blancs sont bien inatteignables, parce qu'un objet modifié devient de nouveau gris, donc à la fin de la traversée t'as la garantie que tous les objets ont été traversés dans leur état final.

Si j'avais pas trouvé ce poste sur stackoverflow plus tôt c'est peut-être parce que je cherchais avec le mot "itératif" d'ailleurs j'imagine...

[18:02:49] <godrik>

Une autre solution serait que les références pointent pas directement sur l'adresse système de l'objet, mais sur une adresse virtuelle gérée par le garbage collector et que lui ferait le lien "adresse locale au garbage collector" -> "adresse système", mais je sais pas si c'est viable de rajouter encore un niveau d'indirection supplémentaire pour accéder aux objets.

C'est ca que font les systemes qui font de l'optimisation de placement memoire. La reference est juste une entree dans une table de hashage qui pointe a l'addresse physique de l'objet. Du fait tu peux migrer les objets dans l'espace memoire sans avoir besoin de changer les references.

Si ca a l'air de couter une indirection de plus a chaque dereferenement d'objet, c'est parceque ca coute une indirection de plus a chaque dereferencement d'objet.

En pratique c'est optimisable dans plein de cas. Tu pourrais imagine qu'il y a un bit dans l'objet qui dit "je garde une addresse physique de cet objet, alors ne le deplace pas" qui peut etre utilise par les code qui ont des boucles courte. Ou alors tu peux imagine que les objets sont deplace par section. Tu prends un RWlock sur tous les objet dont la reference est de 14 modulo 10000. Et tous les autres threds peuvent travailler sur les addresse en memoire virtuelle des objets dont la reference n'est pas 14 modulo 10000.

J'ai pas compris la dernière partie par rapport aux sections, le lock est pour quoi, pour l'adresse virtuelle des objets ?