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


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 mieszania powinny być kolekcjonowalne, jeśli nie odwołują się do nich nic poza tabelą mieszającą; 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 wykorzystuje System.Collections.Generic.Dictionary<key, node> gdzie key jest krotką dającą płytkie podsumowanie węzła (odpowiednie dla domyślnego skrótu i ​​testu równości) i node jest obiektem. Jedynym problemem jest to, że Dictionary utrzymuje silne odniesienia do węzłów!

Mógłbym użyć a Dictionary do WeakReferenceAle to nie uwolniłoby kluczy wskazujących na wiszące referencje.

Niektórzy używają adwokata System.Runtime.CompilerServices.ConditionalWeakTable ale ta klasa wydaje się robić coś odwrotnego: uwalnia wartość, gdy klucz jest zbierany, podczas gdy ja muszę uwolnić klucz, gdy wartość jest zbierana.

Można spróbować użyć System.Runtime.CompilerServices.ConditionalWeakTable<node, node> ale potrzebowałbym niestandardowych testów mieszania i równości ... i ConditionalWeakTable jest udokumentowane nie korzystać z GetHashCode() metoda wirtualna, zamiast tego korzysta z domyślnej funkcji mieszania.

Tak więc moje pytanie: czy istnieje jakiś odpowiednik Dictionary które utrzymywałoby słabe odniesienia do wartości i uwalniało klucze, gdy referencje się zwisały?


17
2018-03-25 14:11


pochodzenie


Czy musisz zwolnić klucz natychmiast po zebraniu wartości? A może mógłbyś zwolnić to wymaganie i po prostu uwolnić klucz w jakimś późniejszym momencie? - Jack P.
Nie potrzebuję ich natychmiastowego uwolnienia - po prostu nie chcę, żeby się gromadzili i bezużytecznie zużywają dużo pamięci. Myślałem o uruchomieniu innego wątku, aby okresowo zabijać klucze z wiszącymi referencjami, ale wydaje się to być skomplikowane i podatne na błędy współbieżności. - David Monniaux
Czy mógłbyś implementować słabe hashtables w F # używając kodu OCaml jako implementację referencyjną? IIRC słabe hashset wykorzystuje słabe tablice, które mogą być zaimplementowane w / Array <WeakReference>. - fmr
Wydaje się być powiązany: Kompaktowanie słownika WeakReference - Artem Koshelev
Również, DependentHandle może pomóc: Efememory w .NET i C # - Artem Koshelev


Odpowiedzi:


Masz rację, że CWT nie rozwiązuje kłopotliwego problemu, 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 mojej maszynie test1 zabrakło pamięci i test2 się uda. 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 skomplikowanie, ma to również sens, aby dać użytkownikowi kontrolę, powiedz:

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 musisz wprowadzać wątków, sprawdzać, jak działają funkcje GC, ani wykonywać 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ę.


3
2018-03-27 16:06



Próbowałem używać CWT, ale okazało się, że dane umieszczone w tabeli zostały natychmiast zebrane (ponieważ wartość jest pobierana, gdy klucz staje się nieosiągalny). Czy próbowałeś odzyskać dane z CWT? Niemożliwe jest użycie CWT od A do A, ponieważ CWT ma nie użyj funkcji hashcode z typu danych, ale zamiast tego wywołuje domyślną funkcję skrótu, która jest nieodpowiednia dla funkcji mieszania (wymaga płytkiego mieszania z unikalnymi identyfikatorami). Jednym rozwiązaniem byłoby skopiowanie kodu źródłowego CWT i dostosowanie go. - David Monniaux
@monniaux: tak, zgadzam się, że CWT nie nadaje się do używania hasha. Słaba tabela OCaml wyraźnie wygrywa tutaj. Odzyskiwanie danych z CWT jest w porządku, ale jeśli trzymasz się kluczy - to jest to, do czego został zaprojektowany. Tak, opublikuj tutaj, jeśli znajdziesz dobre rozwiązanie lub napisz własne - dla hash-consing. - t0yv0