Хэш-consing в F # и слабые хэш-таблицы в .net

Question

Hash-consing состоит в сохранении в памяти только одной копии данного объекта; то есть, если два объекта семантически равны (одно и то же содержимое), то они должны быть физически равными (одно и то же местоположение в памяти). Этот метод обычно реализуется путем сохранения глобального набора хэшей и создания новых объектов только в том случае, если они не равны объекту в хэш-наборе.

Дополнительным требованием является то, что объекты в хэш-таблице должны собираться, если на них не ссылаются ни на что иное, кроме хеш-таблицы; в противном случае хеш-таблица должна содержать слабые ссылки.

Проблема, кроме того, осложняется необходимостью иметь постоянное время, таким образом, неглубокие, хэширование и тесты на равенство; таким образом, объекты имеют уникальный идентификатор, который увеличивается при добавлении нового объекта в таблицу.

У меня есть рабочая реализация, которая использует System.Collections.Generic.Dictionary<key, node>, где key является кортежем, дающим мелкую сводку узла (подходит для теста хэширования и равенства по умолчанию) и node является объектом. Единственная проблема заключается в том, что Dictionary сохраняет сильные ссылки на узлы!

Я мог бы использовать Dictionary до WeakReference, но это не освободит ключи, указывающие на оборванные ссылки.

Некоторые защитники используют System.Runtime.CompilerServices.ConditionalWeakTable, но этот класс, похоже, делает обратное: он освобождает значение при сборке ключа, тогда как мне нужно освободить ключ при сборке значения.

Можно попробовать использовать System.Runtime.CompilerServices.ConditionalWeakTable<node, node>, но я должен был бы заказ хэширования и равенства тестов ... и ConditionalWeakTable документирована не использовать виртуальный метод GetHashCode(), вместо того, чтобы с помощью функции хэширования по умолчанию.

Таким образом, мой вопрос: есть ли какой-то эквивалент Dictionary, который будет поддерживать слабые ссылки на значения и освобождать ключи, когда ссылки становятся свисающими?

Answer 1

Вы правы, что CWT не решает проблему хеш-consing, потому что он задает вопрос - его ключи принимают ссылочное равенство. Однако, может быть, стоит отметить, что CWT не держится за ключи или ценности. Вот небольшой тест:

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 

На моей машине, test1 бежит из памяти и test2 успешно. Похоже, что это произойдет только в том случае, если CWT не будет держаться за ключи, а также за ценности.

Для хеш-consing ваша лучшая ставка может быть тем, что Артем предлагает в комментариях. Если это звучит слишком сложно, это также делает много смысла, чтобы просто дать пользователю контроль, скажем:

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 

Тогда вам не нужно вводить многопоточность, изучить, как GC Internals работу, или сделать какой-либо магии. Пользователь библиотеки может решить, где уместно очистить или просто «забыть» фабричный объект, который собирал бы всю таблицу.