Come viene implementata la "lista grigia" nei moderni garbage collector?

Question

Come viene implementata la "lista grigia" nei moderni garbage collector?

#1 da (1 voti)

1

Nell'articolo di Wikipedia per "traccia della garbage collection", viene fatta la seguente affermazione:

...most modern tracing garbage collectors implement some variant of the tri-color marking abstraction

In questa astrazione, gli oggetti sono raggruppati in tre gruppi: bianco, nero e grigio. L'algoritmo di tracciamento di base enumera tutti gli elementi del set di grigio, contrassegnando ogni oggetto grigio come nero fino a quando tutti gli oggetti non raggiungibili sono bianchi e possono essere eliminati.

L'articolo non è in come viene implementato il set di grigio , che ha implicazioni chiare per le prestazioni generali dell'algoritmo GC. La soluzione più diretta ed evidente è quella di modellare il set grigio come una struttura dati di puntatori agli oggetti (hash set, stack, code, qualunque), ma (tenete a mente che non ho dati su questo) questo sembra abbastanza costoso in termini di spazio, un puntatore per riferimento all'oggetto nello stack di chiamate.

In che modo la "lista grigia" è implementata nei moderni garbage collector per massimizzare l'efficienza in termini di tempo e spazio e quale tipo di sovraccarico comporta queste soluzioni?

garbage-collection

posta Ricky Stewart 19.02.2018 - 17:52

fonte

1 risposta

Leggi altre domande sui tag garbage-collection

Un servizio CRUD di REST che accede a un DB ha 3 versioni del suo modello Solo una applicazione nel cluster esegue un lavoro

score 1 · Answer 1

In the naive mark-and-sweep method, each object in memory has a flag (typically a single bit) reserved for garbage collection use only.

Per tricromente hai bisogno di un altro bit in ogni oggetto per un totale di 2 bit da utilizzare solo per gc.

Un'implementazione andrebbe in questo modo: ogni oggetto heap gc-able utente inizia il suo layout di memoria con un primo campo che è una specie di oggetto classe, che identifica sia il vero tipo di runtime dell'oggetto, sia detiene vtables e l'interfaccia tabelle (tabelle di test del protocollo). Questo primo campo, usato dal runtime, non viene visto dall'utente (e, l'oggetto classe è probabilmente solo un oggetto ordinario nel linguaggio di esecuzione del runtime piuttosto che un oggetto utente gc-able).

Come la maggior parte degli oggetti, questi oggetti di classe si trovano su limiti di lunghe parole allineati, e questo rende sempre i loro 2-3 bit più bassi degli indirizzi. Questi bit sempre zero possono essere presi in prestito per gli scopi sopra gc.

L'unico svantaggio è che chiunque voglia il vero oggetto di classe (ad esempio il runtime che esegue dispacciamento o cast o qualcos'altro) molto probabilmente dovrà mascherare questi bit prima dell'uso effettivo in dereferenziazione (ciò dipende dall'architettura dell'insieme di istruzioni ).