Hash-Consing in F # und schwache Hash-Tabellen in .net

Question

Hash-consing besteht darin, nur eine Kopie eines gegebenen Objekts im Speicher zu behalten; Das heißt, wenn zwei Objekte semantisch gleich sind (gleicher Inhalt), dann sollten sie physikalisch gleich sein (gleicher Ort im Speicher). Die Technik wird normalerweise implementiert, indem ein globaler Hash-Satz beibehalten und neue Objekte nur dann erzeugt werden, wenn sie einem Objekt im Hash-Satz nicht gleich sind.

Eine zusätzliche Anforderung besteht darin, dass Objekte in der Hash-Tabelle erfassbar sein sollten, wenn sie nur von der Hash-Tabelle referenziert werden; ansonsten sollte die Hash-Tabelle schwache Referenzen enthalten.

Das Problem wird weiterhin durch die Notwendigkeit, konstante Zeit haben, daher flach, Hashing und Gleichheit Tests; Somit haben Objekte einen eindeutigen Bezeichner, der erhöht wird, wenn ein neues Objekt zur Tabelle hinzugefügt wird.

Ich habe eine funktionierende Implementierung, die System.Collections.Generic.Dictionary<key, node> verwendet, wobei key ein Tupel ist, das eine flache Zusammenfassung des Knotens gibt Das einzige Problem ist, dass die Dictionary starke Referenzen zu den Knoten hält!

Ich könnte eine Dictionary zu WeakReference 's verwenden, aber dies würde nicht die Schlüssel frei, die zu dangling Referenzen zeigen.

Einige Befürworter mit System.Runtime.CompilerServices.ConditionalWeakTable aber diese Klasse scheint das Gegenteil zu tun: Es befreit den Wert, wenn der Schlüssel gesammelt wird, während ich den Schlüssel freigeben muss, wenn der Wert gesammelt wird.

Man könnte versuchen System.Runtime.CompilerServices.ConditionalWeakTable<node, node> verwenden, aber ich würde ... custom Hashing und Gleichheitstests benötigt und ConditionalWeakTable dokumentiert nicht die GetHashCode() virtuelle Methode zu verwenden, anstatt die Standard-Hash-Funktion verwendet wird.

Also meine Frage: gibt es ein Äquivalent von Dictionary, die schwache Referenzen auf Werte halten und die Schlüssel freigeben würde, wenn die Referenzen baumeln?

Answer 1

Sie haben recht, dass CWT das Hash-Consing-Problem nicht löst, weil es die Frage aufwirft - seine Schlüssel nehmen Referenzgleichheit an. Es sollte jedoch darauf hingewiesen werden, dass CWT nicht an Schlüsseln oder Werten festhält. Hier ist ein kleiner 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 

Auf meinem Rechner test1 läuft aus dem Speicher und test2 erfolgreich ist. Es scheint, dass dies nur passieren würde, wenn CWT nicht an Schlüsseln und Werten festhalten würde.

Für Hash-consing könnte Ihre beste Wette sein, was Artem in den Kommentaren vorschlägt. Wenn dies zu kompliziert klingt, ist es auch sehr viel Sinn macht, nur die Benutzersteuerung zu geben, sagen:

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 

Dann brauchen Sie nicht Threading einführen, zu untersuchen, wie GC-Interna Arbeit oder über Magie tun. Der Benutzer der Bibliothek kann entscheiden, wo es angebracht ist, das Fabrikobjekt zu bereinigen oder einfach zu "vergessen" - was die gesamte Tabelle sammeln würde.