Tipi di dati non ricorsivi = Nessuna necessità di garbage collection?

Il conteggio dei riferimenti richiede di essere più consapevoli delle durate degli oggetti. Quando si crea un grafico in un ambiente di conteggio di riferimento, si crea un oggetto padre che possiede tutti i nodi nel grafico. Se i nodi del grafico hanno un concetto di direzione, i riferimenti dall'alto verso il basso possono anche essere riferimenti forti. Tuttavia, le connessioni non dirette oi backlink devono essere refs deboli che non incrementano il conteggio dei riferimenti. Questo va bene, dal momento che l'oggetto proprietario del grafico assicura che tutti i nodi vivano abbastanza a lungo. Questo non ha nemmeno bisogno del conteggio dei riferimenti: C ++ - o gestione della durata in stile ruggine è sufficiente.

Ciò impedisce perdite di memoria nel senso che tutti i nodi gestiti attraverso questo grafico vengono infine deallocati (quando l'intero grafico viene deallocato). Tuttavia, se un nodo particolare nel grafico non viene referenziato da altri nodi, rimarrà comunque attivo. Naturalmente, ciò potrebbe essere intenzionale (non tutti i grafici sono grafici collegati). Non è possibile rimuovere un nodo da questo grafico, a meno che non si spazzino tutti i nodi per assicurarsi che non sia referenziato. Ciò significa che stai essenzialmente ri-implementando il tuo GC.

(È necessaria una corretta gestione della memoria per garantire sicurezza della memoria : non è possibile referenziare i dati se sono stati deallocati.)

Anche al di fuori dei grafici matematici, tali collezioni proprietarie sono in realtà abbastanza comuni in molti problemi pratici. Per esempio. con il modello di repository , il repository sarebbe proprietario di tutte le entità che gestisce. Altro codice prende solo i riferimenti a ciascuna entità. Le relazioni tra entità non hanno bisogno di usare riferimenti forti.

Quindi, mentre il conteggio dei riferimenti è una soluzione accettabile per quasi tutti i problemi di gestione della memoria (le eccezioni sono le relazioni con proprietà poco chiare o la necessità di rimuovere nodi non referenziati), la tecnica ha una serie di svantaggi significativi:

• Il conteggio dei riferimenti richiede più memoria, dal momento che devi depositare il conto da qualche parte. Questo diventa notevole quando le cose che contate sono molto piccole.
• I conteggi dei riferimenti devono essere aggiornati atomicamente. Ciò significa che non è possibile condividere oggetti tra i thread o utilizzare aggiornamenti relativamente costosi thread-safe.
• Il conteggio dei riferimenti genera inutilmente molte scritture. Ciò rende più difficile la memorizzazione nella cache.
• Mentre il conteggio dei riferimenti può essere deterministico, impone un overhead continuo. Un algoritmo GC pausa-the-world avrà bisogno di meno tempo totale = migliore prestazione ammortizzata.
• Un GC di compattazione può migliorare ulteriormente le prestazioni rendendo tutte le allocazioni molto economiche.

In realtà, le uniche ragioni per utilizzare il conteggio dei riferimenti anziché GC sono:

• I pregiudizi come "GC è troppo {lento, complicato}"
• Consapevolezza della ricerca su GC
• Insufficienza della gestione della durata in fase di compilazione come in C ++, Rust.
• Sistemi in tempo reale in cui le pause GC sono inaccettabili
• Sistemi con vincoli di memoria (GC è più costoso quando deve essere eseguito più spesso)
• Il conteggio dei riferimenti abilita la distruzione deterministica / RAII (ad es. Perl)

Dovrai comunque tenere traccia di quali nodi del tuo grafico sono raggiungibili. Questo potrebbe essere fatto con una sequenza di collezioni "live node" ordinate da "generazione", dove come parte della costruzione di nuovi nodi si memorizza ciò che è raggiungibile da quel nodo, e quindi quando si rilascia una generazione il conteggio dei riferimenti li raccoglierà.

Questo è comunque fondamentalmente la re-implementazione di un GC generazionale "con valutazione stimolante", in cui fa funzionare la raccolta man mano che le cose vengono allocate, piuttosto che prima che vengano distrutte.

Una volta che hai il tuo grafico immutabile, hai anche la tua lista immutabile (come caso limitato).

If all data types are made non-recursive using tricks like a table of node IDs linking to data and data uses only other node IDs to form a graph, then can all memory be managed using just Reference Counting?

Lo spostamento da puntatori come riferimenti a riferimenti basati su ID non modifica il problema. In effetti può peggiorare la situazione!

Le proprietà dei dati immutabili sono piuttosto forti e anche con tipi di dati ricorsivi , i dati immutabili sopprimono i cicli di riferimento del puntatore, poiché un oggetto / dati vecchio non poteva conoscere un riferimento oggetto creato in futuro quando è stato creato (quindi non può fare riferimento a oggetti futuri) e inoltre non può più essere modificato per fare riferimento a un nuovo oggetto. Pertanto, i dati immutabili sono sempre diretti e aciclici in relazione ai riferimenti basati su puntatori.

Tuttavia, usando ID o nomi come meccanismo di riferimento, può essere creato un oggetto immutabile che fa riferimento a un oggetto immutabile futuro, che fa riferimento al vecchio oggetto immutabile, e quindi, usando nomi per riferimenti invece di puntatori, possiamo creare cicli con immutabile i dati.

Furthermore is it possible to express a immutable list with the standard set of Haskell-like functions for the list in a language like C++ and guarantee no memory leaks using only reference counting?

Un elenco collegato singolarmente, sì. Tuttavia, per una lista doppiamente collegata: una lista doppiamente collegata è un tipo di dati ricorsivo che crea anche cicli con riferimenti basati su puntatori.

Il conteggio dei riferimenti semplice o ingenuo non riuscirebbe a rilasciare alcun nodo della lista, se l'elenco nel suo complesso non fosse referenziato. L'unico modo per raccogliere gli elementi sarebbe eliminarli tutti dalla lista.

Il conteggio dei riferimenti intelligenti sarebbe necessario per gestirli, il che significa che i vari riferimenti devono essere differenziati, come @amon descrive, ad esempio, come strong o debole. I forti contano e quelli deboli no. Alcuni sistemi tentano una differenziazione strong vs debole a runtime, dinamicamente e automaticamente; altri sistemi etichettano i riferimenti in fase di compilazione tramite il sistema di tipi; alcuni mescolano i due.

Dai un'occhiata a Objective C e Swift, usano Conteggio dei riferimenti automatici (automatico come assistenza fornita dal compilatore) per la loro gestione della memoria. Nota anche le aree problematiche per ARC, in particolare intorno alle chiusure .

E tuttavia ancora, nei linguaggi raccolti con garbage collection, come Java e C #, abbiamo facilmente e comunemente "perso" memoria. Tutto ciò di cui hai bisogno è una collezione di dati o una struttura di dati di lunga durata che cresce nel tempo ma non viene adeguatamente ridotta nel tempo. Questa è una nozione leggermente diversa di perdita di memoria, ma ha lo stesso effetto in quanto se il programma viene eseguito abbastanza a lungo, esaurirà la memoria. Questo può accadere anche in linguaggi funzionali che applicano dati immutabili, come ad esempio Erlang .