Reference counting

In informatica, il reference counting ("contatore dei riferimenti") è una tecnica di memorizzazione del numero di riferimenti, puntatori o handle a una risorsa come un oggetto o un blocco di memoria.

È tipicamente usato come metodo per deallocare oggetti che non sono più usati in modo automatico e sicuro.

Usi nel garbage collection

Il reference counting è spesso noto come un algoritmo di garbage collection dove ciascun oggetto contiene un contatore del numeri di riferimenti tenuti da altri oggetti. Se il contatore dei riferimenti di un oggetto raggiunge lo zero, l'oggetto diviene inaccessibile e viene messo nella lista degli oggetti da distruggere.

Un semplice reference counting richiede di essere spesso aggiornato. Quando un riferimento viene distrutto o riscritto, il contatore dei riferimenti viene decrementato, mentre quando un riferimento viene creato o copiato, il contatore dei riferimenti viene incrementato.

Il reference counting è anche usato nelle operazioni sui sistemi operativi su disco o distribuiti, dove un completo garbage collection che traccia i riferimenti in un grafo o in un albero è troppo oneroso computazionalmente.

Vantaggi e svantaggi

I vantaggi del reference counting sono che è molto più veloce di qualsiasi altro algoritmo di garbage collection.

Lo svantaggio principale è che bisogna mantenere e gestire un contatore per ogni oggetto che è continuamente aggiornato.

L'algoritmo presenta il problema dei riferimenti circolari:

Si considerino due oggetti (A e B) che puntano l'uno all'altro.

Sia A che B hanno due riferimenti:

• Quello della variabile che li contiene (diretto)
• Quello dell'oggetto che punta a loro (indiretto)

Quando uno dei due oggetti esce dal suo scope, non è più accessibile tramite la sua variabile e la sua memoria non può essere liberata, dal momento che un altro oggetto la sta referenziando (rischio di dangling reference) mentre l'effetto esterno è quello di un memory leak.

La soluzione è utilizzare algoritmi di rilevamento dei cicli con adozione di riferimenti deboli. I riferimenti circolari sono esplicitamente marcati come deboli e non considerati dal reference counting.

Interpretazione in teoria dei grafi

Quando si considerano gli schemi di garbage collection, è spesso utile pensare al grafo delle referenze, che è un grafo direzionato dove i vertici sono gli oggetti e c'è una connessione da un oggetto A ad uno B se A ha un riferimento a B. Si possono anche avere vertici speciali per rappresentare le variabili locali e le referenze bloccate dal sistema runtime, e nessuna connessione può raggiungere questi nodi sebbene da questi nodi possano partire link ad altri nodi.

In questo contesto, il semplice contatore di referenze di un oggetto è il numero delle sue connessioni.

Se un oggetto non può mai essere distrutto in questo tipo di grafi viene rappresentato da un nodo con un loop, cioè da un link a se stesso.

Essendo due oggetti concatenati fra loro è necessario gestire un contatore per ogni oggetto e, nel caso uno dei due oggetti esca dal suo scope non è più accessibile tramite la sua variabile e inoltre la sua memoria non può essere liberata in quanto un altro oggetto lo sta referenziando.

Questo dà effetto ad un memory leak (consumo eccessivo di memoria), per evitare ciò e quindi liberare la memoria devo cancellare i due oggetti concatenati.