Conteggio di riferimento e GC in LISP [chiuso]

Il conteggio dei riferimenti non è praticamente mai sufficiente per gestire la memoria a causa dei cicli. Se una lingua ha una mutazione, possiamo essenzialmente creare una struttura come

  -------------------
  |        |        |
  |  Head  |  Tail  |
  |        |        |
  -------------------
     |  |       |
     |  +-------+
     |
  1 <+

Ho messo troppa energia in questo pessimo schema

Ora che la testa è puntata verso la coda, il contatore dell'oggetto non scenderà mai a 0, il che significa che giacciono per sempre. Questo è un problema persistente per Perl ed è la ragione delle contorsioni con weak_prt in C ++.

Inoltre francamente un buon GC è di ordini di grandezza più veloce del conteggio dei riferimenti. Bumping questi contatori costantemente (in particolare quando è necessario garantire la sicurezza dei thread) in realtà non è libero. Le cose intelligenti con la garbage collection generazionale / parallela possono dare un codice ad alte prestazioni praticamente in pausa!

È naturale chiedersi perché non potremmo iniziare con malloc e gratis in Lisp e vedere dove ci porta. In una lingua con chiusure, tuttavia, l'uso della gestione manuale della memoria è una battaglia pericolosa e costante. Sei costantemente in grave pericolo di chiudere qualcosa con una vita leggermente diversa e avere le cose lentamente a forma di pera. Questa complessità è evidente in C ++ con le nozioni a grana fine di catturare e muoversi dentro e fuori le chiusure, anche questo distrugge la serie di trucchi di tempo in Lisp per la simulazione di oggetti e altre creature utili.

TLDR: la raccolta dei dati inutili è in realtà piuttosto veloce e il conteggio dei riferimenti è semplicemente troppo ingenuo.

Il conteggio dei riferimenti non elaborati non può gestire strutture di dati ciclici, poiché parti della struttura dei dati faranno in modo che altre parti abbiano un conteggio di riferimento superiore a zero.

Alla fine, Lisp (in generale e Common Lisp in particolare) consente di creare "liste" cicliche in lettura: #1#=(red green blue . #1#) è una lista infinita. Sono persino utili, al posto giusto.

Meno ovvio, se hai un albero genealogico con ogni persona rappresentata come un nodo con riferimenti a genitori e figli, improvvisamente hai un grafico che non può essere ripulito usando solo il conteggio dei riferimenti. È utile? In una certa misura, sì. Rende efficacemente O (1) a cercare sia i figli che i genitori da un singolo nodo invece di avere uno di essi efficacemente O (1) e l'altro essendo effettivamente O (popolazione) (o, ammettiamolo, puoi usare riferimenti deboli).

Ancora meno ovvio, l'aggiornamento del conteggio dei riferimenti deve necessariamente avvenire ogni volta che viene fatto un riferimento o disfatto e richiede un Read-Copy-Update o un blocco di acquisizione e rilascio. Con una politica periodica del GC, questo viene ammortizzato nell'intero intervallo.

I frammenti di ambiente in Lisp hanno una durata indeterminata, la maggior parte delle implementazioni LISP richiedono la garbage collection per recuperare l'archivio run-time gratuito.