Esiste un algoritmo di garbage collection che soddisfi questi requisiti?

Question

Sto scrivendo un compilatore per un linguaggio orientato agli oggetti tipicamente staticamente. Attualmente sto cercando algoritmi di raccolta dei rifiuti da usare. Mi chiedo se c'è un collezionista che sia:

• Open source e documentato, in modo che io possa implementarlo.
• acurrate
• generazionale
• globale, cioè v'è un solo collettore per processo, in contrapposizione a dire uno per thread.
• Incrementale e/o concomitante, per evitare lunghe pause dalle raccolte principali.
• Adatto a questo paradigma di programmazione. Un esempio di cosa non sarebbe un collezionista che diventa molto lento in presenza di un incarico distruttivo.

Modifica: Per chiarire, mi chiedevo se c'è un algoritmo di implementabile che fa questo, se non c'è un off-the-shelf collettore.

Answer 1

(avrei preferito lasciare questo come un commento, ma non ho abbastanza rep.)

Se siete alla ricerca di algoritmi piuttosto che codice, Mi sarebbe sicuramente dare uno sguardo su articoli accademici. Ho inciampato su Proceedings of OOPSLA 2003 e subito mi sono ricordato della tua domanda --- avevano due sessioni su Garbage Collection:

http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-1.html
http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-2.html

Il vantaggio di quei momenti "Big Bang" per iniziare la tua ricerca è possibile utilizzare Google Scholar su qualsiasi articolo che sembra promettente, e vedere se ci sono più follow up aggiornati, cercando un titolo e poi cliccando sul link "citato da", per esempio:

http://scholar.google.com/scholar?cites=11437015034573374705&as_sdt=2005&sciodt=0,5&hl=en

(Dal momento che hai così tanti requisiti, si potrebbe avere a baciare molti ranocchi prima di trovare il vostro raccoglitore on-the-fly.)

Answer 2

Probabilmente si potrebbe rubare il garbage collector da mono, che è un'implementazione open source di .Net. Di recente hanno rilasciato un nuovo motore GC che (penso) soddisfi tutti i requisiti di cui sopra.

Answer 3

Il problema con il furto di un collezionista come questo: i garbage collector spesso sono legati alla lingua per cui sono scritti. I buoni collezionisti per i linguaggi funzionali tendono ad agire diversamente dai collezionisti per quelli imperativi. L'open source pone probabilmente c'è motivo di rubare da:

• Mono
• O'Caml
• Python
• ...

Answer 4

Questo è (ovviamente) difficile rispondere senza qualche idea migliore della lingua che speri di ospitare, ma hai guardato il Parrot VM? PDD 9: Garbage Collection Subsystem discute il suo GC e sembra colpire le parole d'ordine che hai richiesto, e le lingue per le quali è stato progettato (Perl6 principalmente, con lua e una javascript-ish fortemente tipizzata chiamata winxed come secondi forti) hanno sicuramente assegnamento distruttivo e Oggetti.

È un obiettivo VM, tuttavia, non un GC indipendente. Dubito davvero che troverai un GC off-the-shelf (diverso dai collettori conservatori come Boehm) che non è associato ad alcun tipo di VM, dal momento che per essere accurato sono necessarie maggiori informazioni sullo stack frame che lo smontaggio può dare.

Answer 5

C'è un algoritmo di raccolta dei dati non tutti sperimentali che soddisfa tutti i requisiti: semplice conteggio automatico. Nel complesso, il conteggio non ha abbastanza credito come opzione praticabile, ma in realtà funziona molto bene in molte situazioni, non ci sono mai ritardi di grandi ritardi e non c'è bisogno di complicate magie.

Una preoccupazione è ancora la pulizia di riferimenti circolari, che si può almeno lasciare fare molto raramente; Gli sviluppatori di app che si preoccupano della velocità possono interrompere esplicitamente i loop quando hanno bisogno che gli oggetti vadano via.

Una caratteristica poco apprezzata del refcounting è che è molto più dcache-friendly di altre forme di garbage collection.Se stai eseguendo un ciclo che alloca alcuni piccoli oggetti temporanei ogni volta attraverso il loop, un GC (o una gestione esplicita della memoria, ovviamente) può riutilizzare la stessa memoria ogni volta, evitando inutili svuotamenti della cache. Qualsiasi altro tipo di GC libererebbe periodicamente gli oggetti, determinando un ingombro di memoria molto più grande e quindi una lentezza.

Il conteggio non è molto efficiente per i sistemi a più thread multipli, perché è necessario acquisire blocchi ogni volta che si tocca il conto. Ma se stai progettando comunque un nuovo linguaggio, c'è una cosa enorme che puoi fare per migliorare le prestazioni e l'affidabilità in tutto il tuo linguaggio: impedire che quasi tutti gli oggetti vengano condivisi tra i thread. vale a dire. rendere la condivisione esplicita. Se lo fai, saprai quali oggetti sono contro e non sono condivisi, e quindi quali devono essere bloccati quando si incrementa/decrementa il conto e quale può essere lasciato sbloccato. Quando non c'è alcun blocco, le prestazioni del conteggio possono essere davvero eccellenti.

Answer 6

L'Azul Garbage Collector è proprietaria, ma c'è abbastanza informazioni disponibili sulla loro algoritmo che si dovrebbe essere in grado di implementare qualcosa di simile: http://news.ycombinator.com/item?id=2022723

Supporta sicuramente collezione "pauseless", anche se la complessità di questa operazione è un buon segno del perché la gente di solito non lo fa.