Perché la raccolta di dati inutili elimina solo l'heap?

27

Fondamentalmente, ho imparato fino ad ora che la garbage collection cancella per sempre qualsiasi struttura di dati che non viene attualmente indicata. Ma questo controlla solo l'heap per tali condizioni.

Perché non controlla anche la sezione dei dati (globali, costanti, ecc. ecc.) o lo stack? Di cosa tratta l'heap che è l'unica cosa che vogliamo essere garbage collection?

    
posta Dark Templar 07.10.2011 - 19:37
fonte

8 risposte

61

Il garbage collector fa esamina lo stack - per vedere quali cose nel mucchio vengono attualmente utilizzate (indicate da) nello stack.

Non ha senso che il garbage collector consideri la raccolta della memoria dello stack perché lo stack non è gestito in questo modo: tutto nello stack è considerato "in uso". E la memoria utilizzata dallo stack viene automaticamente recuperata quando si ritorna dalle chiamate ai metodi. La gestione della memoria dello stack space è così semplice, economica e facile che non vorrai coinvolgere la garbage collection.

(Esistono sistemi, come smalltalk, in cui i frame dello stack sono oggetti di prima classe memorizzati nell'heap e garbage collection come tutti gli altri oggetti.Ma non è l'approccio più popolare in questi giorni.La JVM di Java e il CLR di Microsoft utilizzano lo stack hardware e la memoria contigua.)

    
risposta data 07.10.2011 - 20:02
fonte
19

Trasforma la tua domanda in giro. La vera domanda motivante è in quali circostanze possiamo evitare i costi della garbage collection?

Bene, per prima cosa, quali sono i costi della raccolta dei rifiuti? Ci sono due costi principali. Innanzitutto, devi determinare cosa è vivo ; ciò richiede potenzialmente molto lavoro. In secondo luogo, devi compattare i buchi che si formano quando liberi qualcosa che è stato allocato tra due cose che sono ancora vivi. Quei buchi sono uno spreco. Ma comprimerli è anche costoso.

Come possiamo evitare questi costi?

Chiaramente se puoi trovare uno schema di utilizzo della memoria in cui mai allocare qualcosa di longevo, quindi assegnare qualcosa di breve durata, quindi assegnare qualcosa di longevo, puoi eliminare il costo dei buchi . Se puoi garantire che per alcuni sottoinsiemi dello spazio di archiviazione, ogni allocazione successiva abbia una vita più breve rispetto a quella precedente in quella memoria, quindi non ci saranno mai buchi in quella memoria.

Ma se abbiamo risolto il problema del buco, allora abbiamo risolto anche il problema della garbage collection . Hai qualcosa in quel magazzino che è ancora vivo? Sì. Tutto è stato assegnato prima che durasse più a lungo? Sì, questa supposizione è come abbiamo eliminato la possibilità di buchi. Quindi tutto ciò che devi fare è dire "è l'allocazione più recente in vita?" e tu sai che tutto è vivo in quella memoria.

Abbiamo una serie di allocazioni di memoria in cui sappiamo che ogni allocazione successiva è più breve della precedente allocazione? Sì! I fotogrammi di attivazione dei metodi vengono sempre distrutti nell'ordine opposto in cui sono stati creati perché sono sempre più brevi dell'attivazione che li ha creati.

Quindi possiamo archiviare i frame di attivazione nello stack e sapere che non hanno mai bisogno di essere raccolti. Se c'è una cornice nella pila, l'intera serie di fotogrammi sotto di essa è più longeva, quindi non è necessario che vengano raccolti. E saranno distrutti nell'ordine opposto in cui sono stati creati. Il costo della raccolta dei rifiuti è quindi eliminato per i frame di attivazione.

Ecco perché abbiamo il pool temporaneo nello stack in primo luogo: perché è un modo semplice di implementare l'attivazione del metodo senza incorrere in una penalità di gestione della memoria.

(Ovviamente il costo della raccolta dei dati inutili che raccoglie la memoria riferita a dai riferimenti sui frame di attivazione è ancora lì.)

Consideriamo ora un sistema di controllo del flusso in cui i frame di attivazione sono non distrutti in un ordine prevedibile. Cosa succede se un'attivazione di breve durata può dare luogo a un'attivazione di lunga durata? Come puoi immaginare, in questo mondo non puoi più utilizzare lo stack per ottimizzare la necessità di raccogliere le attivazioni. Il set di attivazioni può contenere ancora dei buchi.

C # 2.0 ha questa caratteristica sotto forma di yield return . Un metodo che restituisce un rendimento verrà riattivato in un momento successivo - la prossima volta che viene chiamato MoveNext - e quando ciò accade non è prevedibile. Pertanto, le informazioni che normalmente si trovano nello stack per il frame di attivazione del blocco iteratore vengono invece memorizzate nell'heap, dove vengono raccolte informazioni inutili quando viene raccolto l'enumeratore.

Allo stesso modo, la funzione "async / await" disponibile nelle prossime versioni di C # e VB ti consentirà di creare metodi le cui attivazioni "cedono" e "riprendono" in punti ben definiti durante l'azione del metodo. Poiché i frame di attivazione non vengono più creati e distrutti in modo prevedibile, tutte le informazioni che prima erano memorizzate nello stack dovranno essere memorizzate nell'heap.

È solo un accidente della storia che ci è capitato di decidere per alcuni decenni che le lingue con frame di attivazione creati e distrutti in modo rigorosamente ordinato fossero di moda. Poiché le lingue moderne sono sempre più carenti di questo proprietà, aspettati di vedere sempre più lingue che reificano le continuazioni sull'heap raccolto dalla spazzatura, piuttosto che sullo stack.

    
risposta data 08.10.2011 - 00:32
fonte
13

La risposta più ovvia, e forse non la più completa, è che l'heap è la posizione dei dati di istanza. Per istanza di dati, intendiamo i dati che rappresentano le istanze di classi, ovvero oggetti, che vengono creati in fase di esecuzione. Questi dati sono intrinsecamente dinamici e il numero di questi oggetti, e quindi la quantità di memoria che occupano, è noto solo al runtime. Ci deve essere un po 'di recupero di questa memoria o programmi di lunga durata consumano tutta la memoria nel tempo.

La memoria che viene consumata dalle definizioni delle classi, dalle costanti e da altre strutture di dati statici è intrinsecamente improbabile che aumenti deselezionata. Poiché esiste una sola definizione di classe in memoria per un numero sconosciuto di istanze di runtime di quella classe, è logico che questo tipo di struttura non costituisca una minaccia per l'utilizzo della memoria.

    
risposta data 07.10.2011 - 19:44
fonte
10

Vale la pena ricordare il motivo per cui abbiamo la garbage collection: perché a volte è difficile sapere quando deallocare la memoria. Hai davvero solo questo problema con l'heap. I dati allocati nello stack verranno deallocati alla fine, quindi non c'è davvero alcun bisogno di fare garbage collection lì. Generalmente si presume che le cose nella sezione dati siano allocate per la durata del programma.

    
risposta data 07.10.2011 - 20:05
fonte
3
  1. La dimensione di questi è prevedibile (costante tranne che per lo stack e lo stack è in genere limitato a pochi MB) e in genere molto piccolo (almeno rispetto alle centinaia di MB che le grandi applicazioni possono allocare).

  2. Gli oggetti allocati dinamicamente hanno in genere un intervallo di tempo ridotto in cui sono raggiungibili. Dopodiché, non è possibile che possano essere nuovamente referenziati. Confrontalo con le voci nella sezione dati, le variabili globali e così via: spesso, c'è una parte di codice che li fa riferimento direttamente (pensa const char *foo() { return "foo"; } ). Normalmente, il codice non cambia, quindi il riferimento è lì e un altro riferimento verrà creato ogni volta che viene richiamata la funzione (che potrebbe essere in qualsiasi momento fino a che il computer lo sa - a meno che non risolvi il problema di interruzione, cioè ). Quindi non puoi liberare comunque la maggior parte di quella memoria, in quanto sarebbe sempre raggiungibile.

  3. In molti linguaggi raccolti con garbage, tutto che appartiene al programma che viene eseguito è heap-allocato. In Python, semplicemente non c'è alcuna sezione di dati e nessun valore allocato allo stack (ci sono i riferimenti che sono le variabili locali, e c'è lo stack di chiamate, ma nessuno dei due è un valore nello stesso senso di int in C) . Ogni oggetto è nell'heap.

risposta data 07.10.2011 - 19:50
fonte
2

Come molti altri risponditori hanno detto, lo stack fa parte del set di root, quindi viene scansionato per riferimenti ma non "raccolto" di per sé.

Voglio solo rispondere ad alcuni dei commenti che implicano che la spazzatura in pila non ha importanza; lo fa, perché potrebbe causare più spazzatura nello heap per essere considerata raggiungibile. Gli scrupolosi scrittori di macchine virtuali e compilatori annullano o escludono in altro modo le parti morte dello stack dalla scansione. IIRC, alcune macchine virtuali hanno tabelle che mappano gamme di PC a bitmap di stack-slot-liveness e altre semplicemente annullano gli slot. Non so quale tecnica sia attualmente preferita.

Un termine usato per descrivere questa particolare considerazione è safe-for-space .

    
risposta data 07.10.2011 - 22:26
fonte
1

Consentitemi di evidenziare alcuni fraintendimenti fondamentali che voi e molti altri avete sbagliato:

"Perché la Garbage Collection spazza solo l'heap?" È il contrario. Solo i più semplici, i più conservatori e i più lenti garbage collector spazzano il mucchio. Ecco perché sono così lenti.

I garbage collector veloci spazzano solo lo stack (e facoltativamente altre radici, come alcuni globali per i puntatori FFI e i registri per i puntatori live) e copiano solo i puntatori raggiungibili dagli oggetti stack. Il resto viene gettato via (cioè ignorato), non viene eseguito il controllo dell'heap.

Dato che l'heap è circa 1000 volte più grande dello stack (s), tale GC a scansione di stack è in genere molto più veloce. ~ 15ms vs 250ms su heap di dimensioni normali. Dal momento che copia (spostando) gli oggetti da uno spazio a un altro, è per lo più chiamato un raccoglitore di copie semi-spaziali, ha bisogno di 2 memorie e quindi non è utilizzabile su dispositivi molto piccoli come i telefoni con poca memoria. È una compattazione, quindi è molto lateralmente al cache, a differenza del semplice mark & scanner dell'heap di scansione.

Poiché i puntatori in movimento, FFI, identità e riferimenti sono difficili. L'identità viene solitamente risolta con ID casuali, riferimenti tramite puntatori di inoltro. FFI è difficile, dal momento che oggetti estranei non possono trattenere i puntatori nel vecchio spazio. I puntatori FFI vengono di solito tenuti in un'arena di heap separata, ad es. con un contrassegno lento e sweep, collettore statico. O malloc banale con il conto. Nota che malloc ha un enorme overhead e ne conta ancora di più.

Segna & sweep è banale da implementare ma non dovrebbe essere usato nei programmi reali, e soprattutto non deve essere insegnato come collector standard. Il più famoso collezionista di copie rapide a scansione di stack è chiamato collezionista di Cheney con due dita .

    
risposta data 17.03.2017 - 21:59
fonte
0

Cosa viene assegnato nello stack? Variabili locali e indirizzi di ritorno (in C). Quando una funzione ritorna, le sue variabili locali vengono scartate. Non è necessario, anche dannoso, spazzare la pila.

Molti linguaggi dinamici e anche Java o C # sono implementati in un linguaggio di programmazione di sistema, spesso in C. Potresti dire che Java è implementato con funzioni C e utilizza variabili locali C e quindi il garbage collector di Java non ha bisogno di spazzare il impilare.

C'è un'eccezione interessante: il garbage collector di Chicken Scheme fa sweep lo stack (in un certo senso), perché la sua implementazione usa lo stack come uno spazio di prima generazione per la raccolta dei rifiuti: vedi Progettazione di schemi di cottura Wikipedia .

    
risposta data 09.10.2011 - 21:44
fonte

Leggi altre domande sui tag