Utilizzerebbe una tabella hash nella garbage collection per risolvere il problema mondiale di mark e sweep?

L'aggiornamento dei riferimenti è non l'unica cosa che richiede una pausa. Gli algoritmi standard comunemente raggruppati in "mark-sweep" assumono tutti che l'intero grafico dell'oggetto rimane inalterato mentre viene marcato. Gestire correttamente le modifiche (i nuovi oggetti creati, i riferimenti modificati) richiede algoritmi alternativi piuttosto complicati, come l'algoritmo tricolore. Il termine generico è "Garbage Collection concorrente".

Ma sì, l'aggiornamento dei riferimenti dopo la compattazione richiede anche una pausa. E sì, l'uso di indirezione (ad esempio tramite un ID oggetto persistente e una tabella hash per i puntatori reali) può ridurre notevolmente la pausa. Potrebbe anche essere possibile rendere questo pezzo privo di blocco se lo si desidera. Sarebbe comunque difficile da ottenere come qualsiasi concorrente di memoria condivisa di basso livello, ma non vi è alcun motivo fondamentale per cui non funzioni.

Tuttavia , avrebbe gravi svantaggi. A parte prendere più spazio ( almeno due parole extra per tutti gli oggetti), rende ogni dereferenzia molto più costoso. Anche qualcosa di semplice come ottenere un attributo ora comporta una ricerca completa della tabella hash. Stimo che il risultato della performance sia peggiore rispetto a quello della traccia incrementale.

All problems in computer science can be solved by another level of indirection … except for the problem of too many layers of indirection

Il tuo approccio non risolve immediatamente il problema della garbage collection, ma lo sposta solo di un livello. E a che prezzo! Ora, ogni accesso alla memoria passa attraverso un altro dereferenziatore puntatore. Non possiamo memorizzare nella cache la posizione del risultato, perché nel frattempo potrebbe essere stato spostato, dobbiamo sempre passare attraverso l'ID dell'oggetto. Nella maggior parte dei sistemi, questa indiretta non è accettabile e si presume che l'arresto del mondo abbia un costo totale di runtime inferiore.

Ho detto che la tua proposta sposta solo il problema, non lo risolve. Il problema riguarda il riutilizzo degli ID oggetto. Gli ID oggetto ora sono il nostro equivalente di puntatori e c'è solo una quantità limitata di indirizzi. È concepibile (specialmente su un sistema a 32 bit) che durante la vita del tuo programma, siano stati creati più oggetti INT_MAX, ad es. in un ciclo come

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

Se incrementiamo solo l'ID oggetto per ogni oggetto, a un certo punto esauriremo gli ID. Pertanto, dobbiamo scoprire quali ID sono ancora in uso e quali sono gratuiti in modo che possano essere recuperati. Suona familiare? Ora siamo tornati al punto di partenza.

Non ci sono errori nella tua linea di pensiero, hai appena descritto qualcosa di molto vicino a come ha funzionato il garbage collector Java originale

The original Java virtual machine [6] and some Smalltalk virtual machines use indirect pointers, called handles in [6],to refer to objects. Handles allow easy relocation of objects during garbage collection since, with handles, there isonly one direct pointer to each object: the one in its handle. All other references to the object indirect through the han-dle. In such handle-based memory systems, while object addresses change over the lifetime of objects and therefore cannot be used for hashing, handle addresses remain constant.

Space and Time-Efficient Hashing of Garbage-Collected Objects

In Sun’s current implementation of the Java Virtual Machine, a reference to a class instance is a pointer to a handle that is itself a pair of pointers: one to a table containing the methods of the object and a pointer to the Class object that represents the type of the object, and the other to the memory allocated from the Java heap for the object data.

The Java Virtual Machine Specification (1997)

Quindi funziona, è stato provato e la sua inefficienza ha portato allo sviluppo di sistemi generazionali di mark e sweep.