Hash-consing w F # i słabe tablice hash w .net

Question

Hash-consing polega na zachowaniu w pamięci tylko jednej kopii danego obiektu; to znaczy, jeśli dwa obiekty są semantycznie równe (ta sama treść), to powinny być fizycznie równe (ta sama lokalizacja w pamięci). Technika jest zwykle realizowana poprzez utrzymywanie globalnego zestawu skrótów i tworzenie nowych obiektów tylko wtedy, gdy nie są one równe obiektowi w zestawie mieszającym.

Dodatkowym wymogiem jest to, że obiekty w tabeli mieszającej powinny być kolekcjonerskie, jeśli nie odwołują się do nich nic poza tablicą skrótów; w przeciwnym razie, tablica asocjacyjna powinna zawierać słabe referencje.

Kwestia ta jest dodatkowo komplikowana potrzebą posiadania stałego czasu, a więc płytkich testów hashowania i równości; w ten sposób obiekty mają unikalny identyfikator, który jest zwiększany po dodaniu nowego obiektu do tabeli.

Mam działającą implementację, która używa System.Collections.Generic.Dictionary<key, node> gdzie key jest krotką, co daje płytkie podsumowanie węzła (odpowiednie dla domyślnego testu mieszania i równości) i node jest obiektem. Jedynym problemem jest to, że Dictionary utrzymuje silne odniesienia do węzłów!

Mogę użyć Dictionary do WeakReference, ale to nie uwolniłoby kluczy wskazujących na wiszące referencje.

Niektórzy adwokat używający System.Runtime.CompilerServices.ConditionalWeakTable, ale ta klasa wydaje się robić coś odwrotnego: uwalnia wartość, gdy klucz jest zbierany, a ja muszę zwolnić klucz po zebraniu wartości.

Można by spróbować użyć System.Runtime.CompilerServices.ConditionalWeakTable<node, node> ale musiałbym testy zwyczaj hashowania i równości ... i ConditionalWeakTable jest udokumentowana nie korzystać z wirtualnego metody GetHashCode(), zamiast korzystania z funkcji domyślny mieszającego.

W związku z tym moje pytanie: czy istnieje odpowiednik Dictionary, który utrzymywałby słabe odniesienia do wartości i zwalniał klucze, gdy referencje się zwisały?

Answer 1

Masz rację, że CWT nie rozwiązuje problemu haszącego, ponieważ to nasuwa pytanie - jego klucze zakładają równość odniesienia. Warto jednak zauważyć, że CWT nie obsługuje kluczy ani wartości. Oto mały 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 

Na moim komputerze, test1 zabraknie pamięci i test2 powiedzie. Wygląda na to, że stanie się tak tylko wtedy, gdy CWT nie będzie trzymało kluczy i wartości.

Jeśli chodzi o hash-consing, najlepszym rozwiązaniem może być sugestia Artema w komentarzach. Jeśli brzmi to zbyt skomplikowane, ale również sprawia, że ​​wiele sensu, aby tylko dać użytkownikowi kontrolę, powiedzieć:

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 

Wtedy nie trzeba wprowadzać wątków, badać, jak GC prace wewnętrzne kolumn lub wykonywać żadnej magii. Użytkownik biblioteki może zdecydować, gdzie należy oczyścić lub po prostu "zapomnieć" o obiekcie fabrycznym - który zbierałby całą tabelę.