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

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

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

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

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

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

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

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

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

Ответ 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 или делать какую-либо магию. Пользователь библиотеки может решить, где убрать или просто "забыть" объект factory, который собирал бы всю таблицу.