iset - Hash-consing en F#y tablas hash débiles en.net

iset c#

Question

Hash-consing consiste en mantener en la memoria solo una copia de un objeto dado; es decir, si dos objetos son semánticamente iguales (el mismo contenido), entonces deberían ser físicamente iguales (la misma ubicación en la memoria). La técnica generalmente se implementa manteniendo un conjunto de hash global y creando nuevos objetos solo si no son iguales a un objeto en el conjunto de hash.

Un requisito adicional es que los objetos en la tabla hash deben ser coleccionables si no están referenciados por nada excepto la tabla hash; dicho de otro modo, la tabla hash debe contener referencias débiles.

El problema se complica, además, por la necesidad de tener pruebas constantes de tiempo, por lo tanto poco profundas, hash e igualdad; por lo tanto, los objetos tienen un identificador único que se incrementa cuando se agrega un nuevo objeto a la tabla.

Tengo una implementación de trabajo que utiliza System.Collections.Generic.Dictionary<key, node> donde key es una tupla que proporciona un resumen superficial del nodo (adecuado para el hashing predeterminado y la prueba de igualdad) y node es el objeto. ¡El único problema es que el Dictionary mantiene fuertes referencias a los nodos!

Podría usar un Dictionary to WeakReference , pero esto no liberaría las claves que apuntan a referencias colgantes.

Algunos recomiendan utilizar System.Runtime.CompilerServices.ConditionalWeakTable pero esta clase parece hacer lo contrario: libera el valor cuando se recopila la clave, mientras que necesito liberar la clave cuando se recopila el valor.

Se podría intentar usar System.Runtime.CompilerServices.ConditionalWeakTable<node, node> pero necesitaría hashing personalizado y pruebas de igualdad ... y se ha documentado que ConditionalWeakTable no usa el método virtual GetHashCode() , sino que utiliza la función de hashing predeterminada.

Por lo tanto, mi pregunta: ¿hay algún equivalente de Dictionary que mantenga las referencias débiles a los valores y libere las claves cuando las referencias se vuelvan peligrosas?

Answer 1

Tiene razón en que CWT no resuelve el problema de la comprobación de hash porque plantea la pregunta: sus claves asumen la igualdad de referencia. Sin embargo, podría valer la pena señalar que CWT no se aferra a claves o valores. Aquí hay una pequeña prueba:

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

En mi máquina, test1 queda sin memoria y test2 tiene éxito. Parece que esto solo sucedería si CWT no se aferraba tanto a las claves como a los valores.

Para el control de hash, su mejor apuesta podría ser lo que Artem sugiere en los comentarios. Si esto suena demasiado complicado, también tiene mucho sentido simplemente darle control al usuario, por ejemplo:

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 

Entonces no necesita introducir hilos, estudiar cómo funcionan los componentes internos de GC o hacer magia. El usuario de la biblioteca puede decidir dónde es apropiado limpiar o simplemente "olvidar" el objeto de fábrica, que recopilaría toda la tabla.