Mi piacerebbe imparare i concetti importanti alla base del design del garbage collector. La mia priorità è la chiarezza concettuale, non l'efficienza di runtime. In particolare, vorrei sapere:
Leggi la garbage collection wikipage poi Manuale GC . Forse anche il vecchio sondaggio GC di unisrocessore P.Wilson
Non sono sicuro che la tua domanda abbia molto senso. In pratica, un GC è strettamente correlato all'implementazione del linguaggio (o alla macchina virtuale bytecode) a cui è destinato. Il GC del mondo reale per i linguaggi compilati richiede una profonda cooperazione tra compilatore e GC.
Alcuni GC sono conservativi, suppongono che tutto ciò che assomiglia ad un puntatore possa essere un puntatore GC-ed. Un esempio tipico è Garbage collector conservatore di Boehm , ma la sua implementazione è complicata. Credo che la codifica di GC conservativi sia praticamente abbastanza complicata (devi capire profondamente come viene gestito lo spazio degli indirizzi sul tuo computer).
La maggior parte dei GC sono precisi, hanno bisogno di conoscere esattamente tutti i puntatori (ai valori GC-editi) nello stack delle chiamate. Questo è spesso linguaggio specifico. Potresti avere classi C ++ o macro C per questo, come nel mio qish GC (che è un GC di copia generazionale) .
Vorrei studiare diverse implementazioni di schemi giocattolo, di solito hanno un GC.
What data structures are used in a garbage collector?
Non sono sicuro che sia pertinente. Devi solo essere in grado di attraversare i puntatori per le variabili locali (su alcuni stack di chiamate, lo stack di chiamate della macchina o più frequentemente lo stack di chiamate dell'interprete), e devi esaminare ogni puntatore nei tuoi valori (o oggetti GC-ed) . Naturalmente, il tuo oggetto GC-edito potrebbe avere una struttura dati (specifica per una lingua). E alcuni GC hanno strutture dati complesse per motivi di efficienza (rispondendo rapidamente alle due domande principali: quali sono i puntatori locali in questo frame di chiamata? Quali sono i puntatori in questo oggetto o valore GC-ed).
How much overhead per object is acceptable?
Definisci cosa intendi per overhead. Alcuni GC-s non hanno overhead per oggetto (specialmente perché la lingua può portare il proprio overhead - cioè, metadata, puntatore di classe, vtable - che può essere parzialmente riutilizzato dal GC). Possono avere un overhead a livello di sistema (ad esempio, la copia in modalità ingenua GC utilizza solo metà della memoria).
What triggers the garbage collection process?
Dipende. Di solito l'allocatore di oggetti potrebbe attivare GC, ad es. prendi un po 'di memoria e se nessuno è disponibile, fai un GC.
How "stopping the world" is actually implemented.
"Ferma il mondo" è una proprietà dei GC (i più semplici, che completano il GC mentre il codice dell'applicazione -a.k.a. mutator- viene fermato).
Hai dimenticato diverse domande.
Che cos'è una chiusura e perché le lingue funzionali vogliono un GC? Leggi anche le continuazioni ....
Come creare un GC amichevole multi-thread?
Queste domande sono documentate.
Si noti che i GC sono concettualmente semplici (stanno solo analizzando interamente un grafico di riferimenti). Un ingannevole GC mark-and-sweep per una lingua la cui implementazione si conosce intimamente (ad es. Che stai implementando in questo momento) è molto facile da codificare (poche dozzine o centinaia di righe). Ciò che è difficile è eseguirne il debug e implementare GC efficienti.
Un GC di mark e sweep è concettualmente molto semplice:
La copia (in particolare la copia generazionale) o la compattazione del GC sono un po 'più complessi. Probabilmente dovrai capire cos'è una barriera di scrittura e dovrai implementarla.
Il debug di un GC potrebbe essere doloroso. Con un recente gdb , puoi usare watchpoint e script del debugger in Python.
Codifica un piccolo interprete (ad esempio un piccolo Lisp o una lingua con chiusure o oggetti) e codifica il GC contemporaneamente, leggendo alcuni libri GC.
Leggi altre domande sui tag design garbage-collection