Hash-consing in F # e tabelle hash deboli in .net

Question

Hash-consing consiste nel tenere in memoria solo una copia di un dato oggetto; cioè, se due oggetti sono semanticamente uguali (stesso contenuto), allora dovrebbero essere fisicamente uguali (stessa posizione in memoria). La tecnica viene generalmente implementata mantenendo un set di hash globale e creando nuovi oggetti solo se non sono uguali a un oggetto nel set di hash.

Un ulteriore requisito è che gli oggetti nella tabella hash debbano essere raccolti se non sono referenziati da nulla tranne la tabella hash; diversamente detto, la tabella hash dovrebbe contenere riferimenti deboli.

Il problema è inoltre complicato dalla necessità di disporre di test costanti di tempo, quindi superficiali, di hashing e di uguaglianza; quindi gli oggetti hanno un identificatore univoco che viene incrementato quando un nuovo oggetto viene aggiunto alla tabella.

Ho un'implementazione funzionante che utilizza System.Collections.Generic.Dictionary<key, node> dove key è una tupla che fornisce un breve riepilogo del nodo (adatto per l'hashing e il test di uguaglianza predefiniti) e node è l'oggetto. L'unico problema è che lo Dictionary mantiene forti riferimenti ai nodi!

Potrei usare un Dictionary a WeakReference ma questo non libererebbe le chiavi che puntano a riferimenti ciondolanti.

Alcuni sostengono usando System.Runtime.CompilerServices.ConditionalWeakTable ma questa classe sembra fare l'opposto: libera il valore quando viene raccolta la chiave, mentre ho bisogno di liberare la chiave quando il valore viene raccolto.

Si potrebbe provare a utilizzare System.Runtime.CompilerServices.ConditionalWeakTable<node, node> ma avrei bisogno di test di hashing costume e uguaglianza ... e ConditionalWeakTable non è documentato di utilizzare il metodo virtuale GetHashCode(), invece di usare la funzione predefinita di hashing.

Quindi la mia domanda: c'è qualche equivalente di Dictionary che manterrebbe riferimenti deboli ai valori e libererebbe le chiavi quando i riferimenti diventano penzoloni?

Answer 1

Hai ragione che CWT non risolve il problema dell'hash-consing perché pone la domanda - le sue chiavi assumono l'uguaglianza di riferimento. Tuttavia, potrebbe essere utile sottolineare che CWT non mantiene le chiavi oi valori. Ecco un piccolo test:

open System.Collections.Generic 
open System.Runtime.CompilerServices 

let big() = 
    ref (Array.zeroCreate (1024 * 1024) : byte []) 

let test1() = 
    let d = Dictionary(HashIdentity.Reference) 
    for i in 1 .. 10000 do 
     stdout.WriteLine(i) 
     let big = big() 
     d.Add(big, big) 
    d 

let test2() = 
    let d = ConditionalWeakTable() 
    for i in 1 .. 10000 do 
     stdout.WriteLine(i) 
     let big = big() 
     d.Add(big, big) 
    d 

Sulla mia macchina, test1 esaurisce la memoria e test2 riesce. Sembra che ciò accada solo se CWT non ha tenuto conto delle chiavi e dei valori.

Per hash-consing, la soluzione migliore potrebbe essere ciò che Artem suggerisce nei commenti. Se questo sembra troppo complicato, ma rende anche un sacco di senso per dare solo il controllo utente, dire:

let f = MyFactory() // a dictionary with weak reference values hidden inside 
f.Create(..) : MyObject // MyObject has no constructors of its own 
f.Cleanup() // explicitly cleans up entries for collected keys 

Allora non c'è bisogno di introdurre la filettatura, studiare come GC lavoro interni, o di fare qualsiasi magia. L'utente della biblioteca può decidere dove è opportuno pulire o semplicemente "dimenticare" l'oggetto di fabbrica - che raccoglierà l'intera tabella.