压缩弱引用字典

Question

我有一个带有属性 Id 的类 Foo。我的目标是不存在两个 Foo 实例同时具有相同的 Id。

因此，我创建了一个工厂方法 CreateFoo，它使用缓存来为相同的 Id 返回相同的实例。

static Foo CreateFoo(int id) {
    Foo foo;
    if (!cache.TryGetValue(id, out foo)) {
        foo = new Foo(id);
        foo.Initialize(...);
        cache.Put(id, foo);
    }
    return foo;
}

缓存被实现为字典，基于@JaredPar的构建 WeakReference 哈希表：

class WeakDictionary<TKey, TValue> where TValue : class {
    private readonly Dictionary<TKey, WeakReference> items;
    public WeakDictionary() {
        this.items = new Dictionary<TKey, WeakReference>();
    }
    public void Put(TKey key, TValue value) {
        this.items[key] = new WeakReference(value);
    }
    public bool TryGetValue(TKey key, out TValue value) {
        WeakReference weakRef;
        if (!this.items.TryGetValue(key, out weakRef)) {
            value = null;
            return false;
        } else {
            value = (TValue)weakRef.Target;
            return (value != null);
        }
    }
}

问题是 WeakReference 在其目标被垃圾收集后仍保留在字典中。这意味着需要一些策略来手动“垃圾收集”无效的弱引用，正如@Pascal Cuoq在What中所解释的那样发生在WeakReference.Target GC之后的WeakReference。

---

我的问题是：压缩 WeakReference 字典的最佳策略是什么？

我看到的选项是：

1. 不要从字典中删除 WeakReferences。在我看来，这很糟糕，因为缓存在我的应用程序的整个生命周期中都会使用，并且随着时间的推移，大量死的弱引用将累积。

2. 在每个 Put 和 TryGetValue 上遍历整个字典，并删除无效的弱引用。这在某种程度上违背了字典的目的，因为这两个操作都变成了O(n)。

3. 在后台线程中定期遍历整个字典。鉴于我不知道 CreateFoo 的使用模式，什么是一个好的间隔？

4. 将每个插入的KeyValuePair追加到双端链表中。每次调用 Put 和 TryGetValue 都会检查列表的头部。如果 WeakReference 处于活动状态，则将该对移至列表末尾。如果已死亡，则从列表中删除该对，并从字典中删除 WeakReference。

5. 在于，当存储桶已满时，首先会从存储桶中删除死弱引用，然后再照常进行。

还有其他策略吗？

最好的策略可能是具有摊销时间复杂度的算法。这样的策略存在吗？

Answer 1

如果你可以将托管对象切换为字典的键，那么你可以使用.Net 4.0的ConditionalWeakTable（命名空间System.Runtime.CompilerServices）。

根据 Richter 先生的说法，ConditionalWeakTable 是通过垃圾收集器而不是使用轮询线程来通知对象收集的。

    static ConditionalWeakTable<TabItem, TIDExec> tidByTab = new ConditionalWeakTable<TabItem, TIDExec>();

    void Window_Loaded(object sender, RoutedEventArgs e)
    {
        ...
        dataGrid.SelectionChanged += (_sender, _e) =>
        {
            var cs = dataGrid.SelectedItem as ClientSession;

            this.tabControl.Items.Clear();

            foreach (var tid in cs.GetThreadIDs())
            {
                tid.tabItem = new TabItem() { Header = ... };
                tid.tabItem.AddHandler(UIElement.MouseDownEvent,
                    new MouseButtonEventHandler((__sender, __e) =>
                    {
                        tabControl_SelectionChanged(tid.tabItem);
                    }), true);
                tidByTab.Add(tid.tabItem, tid);
                this.tabControl.Items.Add(tid.tabItem);
            }
        };
    }

    void tabControl_SelectionChanged(TabItem tabItem)
    {
        this.tabControl.SelectedItem = tabItem;
        if (tidByTab.TryGetValue(tabControl.SelectedItem as TabItem, out tidExec))
        {
            tidExec.EnsureBlocksLoaded();
            ShowStmt(tidExec.CurrentStmt);
        }
        else
            throw new Exception("huh?");
    }

这里重要的是，唯一引用 TabItem 对象的是 tabControls.Items 集合，以及 ConditionalWeakTable 的键。 ConditionalWeakTable 的键不算数。因此，当我们清除 tabControl 中的所有项目时，这些 TabItem 可以被垃圾收集（因为没有任何东西再引用它们，ConditionalWeakTable 的键也不算在内）。当它们被垃圾收集时，ConditionalWeakTable 会收到通知，并且具有该键值的条目将被删除。因此，我庞大的 TIDExec 对象此时也会被垃圾收集（除了 ConditionalWeakTable 的值之外，没有任何内容引用它们）。

Answer 2

您的选项 3（线程）有一个很大的缺点，即所有 Put/TryGetvalue 操作都必须进行同步。如果您确实使用此功能，则间隔不是以毫秒为单位，而是每 N 个 TryGet 操作。

选项 2，扫描字典，会产生严重的开销。您可以通过仅扫描千分之一的操作和/或观察 GC 运行的频率来进行改进。

但我会认真考虑选项 1：什么也不做。您可能有“很多”死条目，但另一方面它们非常小（并且会被回收）。可能不是服务器应用程序的选项，但对于客户端应用程序，我会尝试测量我们正在讨论的每小时有多少条目（千字节）。

经过一番讨论：

这样的[n摊销]策略吗
存在吗？

我猜不会。你的问题是一个缩小版的GC。您必须时不时地扫描整个内容。因此只有选项 2) 和 3) 提供了真正的解决方案。它们都很昂贵，但可以通过一些启发式方法进行（大量）优化。不过，选项 2) 偶尔仍然会出现最坏的情况。

Answer 3

方法 #5 很有趣，但有一个缺点，即可能很难知道哈希表利用率的真实水平，因此很难知道何时应该扩展哈希表。如果每当“看起来”应该扩展哈希表时，首先进行全表扫描以删除死条目，那么这个困难就可以克服。如果表中超过一半的条目已失效，则不必费心扩展它。这种方法应该产生摊销的 O(1) 行为，因为在添加回与已删除的条目一样多的条目之前不会执行全表扫描。

一种更简单的方法，每个最近活动的元素也会产生 O(1) 摊销时间和 O(1) 空间，即记录上次清除表后有多少项处于活动状态，以及有多少元素从那时起已添加。每当后一个计数超过第一个计数时，就进行全表扫描和清除。扫描和清除所需的时间将与清除之间添加的元素数量成正比，从而保留摊销的 O(1) 时间，并且集合中的总元素数量不会超过最近观察到的元素数量的两倍为存活，因此死亡元素的数量不能超过最近存活元素数量的两倍。

Answer 4

我遇到了同样的问题，并像这样解决了它（WeakDictionary 是我试图清理的类）：

internal class CleanerRef
{
    ~CleanerRef()
    {
        if (handle.IsAllocated)
            handle.Free();
    }

    public CleanerRef(WeakDictionaryCleaner cleaner, WeakDictionary dictionary)
    {
        handle = GCHandle.Alloc(cleaner, GCHandleType.WeakTrackResurrection);
        Dictionary = dictionary;
    }

    public bool IsAlive
    {
        get {return handle.IsAllocated && handle.Target != null;}
    }

    public object Target
    {
        get {return IsAlive ? handle.Target : null;}
    }

    GCHandle handle;
    public WeakDictionary Dictionary;
}


internal class WeakDictionaryCleaner
{
    public WeakDictionaryCleaner(WeakDictionary dict)
    {
        refs.Add(new CleanerRef(this, dict));
    }

    ~WeakDictionaryCleaner()
    {
        foreach(var cleanerRef in refs)
        {
            if (cleanerRef.Target == this)
            {
                cleanerRef.Dictionary.ClearGcedEntries();
                refs.Remove(cleanerRef);
                break;
            }
        }
    }
    private static readonly List<CleanerRef> refs = new List<CleanerRef>();
}

这两个类试图实现的是“挂钩”GC。您可以通过在构造弱集合期间创建 WeakDictionaryCleaner 的实例来激活此机制：

new WeakDictionaryCleaner(weakDictionary);

请注意，我没有创建对新实例的任何引用，以便 GC 会在下一个周期中处理它。在 ClearGcedEntries() 方法中，我再次创建一个新实例，以便每个 GC 周期都会有一个清理器来完成，进而执行集合压缩。
您可以将 CleanerRef.Dictionary 设为弱引用，这样它就不会在内存中保存字典。

希望这有帮助

Answer 5

我想这是放置它的正确位置，尽管它可能看起来像死灵术。以防万一有人像我一样偶然发现这个问题。 .net 中缺乏专用的身份映射有点令人惊讶，我觉得它最自然的工作方式是最后一个选项中描述的：当表已满并且即将使其容量加倍时，它会检查是否有足够多的死条目可以回收以供进一步使用，因此不需要增长。

static IdentityMap<int, Entity> Cache = new IdentityMap<int, Entity>(e => e.ID);
...
var entity = Cache.Get(id, () => LoadEntity(id));

该类仅公开一个带有 key 和可选 value 参数的公共方法 Get，该方法会延迟加载并缓存实体（如果实体不在缓存中）。

using System;
class IdentityMap<TKey, TValue>
    where TKey : IEquatable<TKey>
    where TValue : class
{
    Func<TValue, TKey> key_selector;
    WeakReference<TValue>[] references;
    int[] buckets;
    int[] bucket_indexes;
    int tail_index;
    int entries_count;
    int capacity;

    public IdentityMap(Func<TValue, TKey> key_selector, int capacity = 10) {
        this.key_selector = key_selector;
        Init(capacity);
    }
    void Init(int capacity) {
        this.bucket_indexes = new int[capacity];
        this.buckets = new int[capacity];
        this.references = new WeakReference<TValue>[capacity];
        for (int i = 0; i < capacity; i++) {
            bucket_indexes[i] = -1;
            buckets[i] = i - 1;
        }
        this.tail_index = capacity - 1;
        this.entries_count = 0;
        this.capacity = capacity;
    }

    public TValue Get(TKey key, Func<TValue> value = null) {
        int bucket_index = Math.Abs(key.GetHashCode() % this.capacity);
        var ret = WalkBucket(bucket_index, true, key);
        if (ret == null && value != null) Add(bucket_index, ret = value());
        return ret;
    }

    void Add(int bucket_index, TValue value) {
        if (this.entries_count == this.capacity) {
            for (int i = 0; i < capacity; i++) WalkBucket(i, false, default(TKey));
            if (this.entries_count * 2 > this.capacity) {
                var old_references = references;
                Init(this.capacity * 2);
                foreach (var old_reference in old_references) {
                    TValue old_value;
                    if (old_reference.TryGetTarget(out old_value)) {
                        int hash = key_selector(value).GetHashCode();
                        Add(Math.Abs(hash % this.capacity), old_value);
                    }
                }
            }
        }
        int new_index = this.tail_index;
        this.tail_index = buckets[this.tail_index];
        this.entries_count += 1;
        buckets[new_index] = bucket_indexes[bucket_index];
        if (references[new_index] != null) references[new_index].SetTarget(value);
        else references[new_index] = new WeakReference<TValue>(value);
        bucket_indexes[bucket_index] = new_index;
    }

    TValue WalkBucket(int bucket_index, bool is_searching, TKey key) {
        int curr_index = bucket_indexes[bucket_index];
        int prev_index = -1;
        while (curr_index != -1) {
            TValue value;
            int next_index = buckets[curr_index];
            if (references[curr_index].TryGetTarget(out value)) {
                if (is_searching && key_selector(value).Equals(key)) return value;
                prev_index = curr_index;
            } else {
                if (prev_index != -1) buckets[prev_index] = next_index;
                else bucket_indexes[bucket_index] = next_index;

                buckets[curr_index] = this.tail_index;
                this.tail_index = curr_index;
                this.entries_count -= 1;
            }
            curr_index = next_index;
        }
        return null;
    }
}

Answer 6

您可以删除 TryGetValue 中的“无效”WeakReference：

[Edit] 我的错误，这些解决方案实际上没有做任何比您建议的更多的事情，因为Put 方法无论如何都会将旧对象与新对象交换。忽略它即可。

public bool TryGetValue(TKey key, out TValue value) {
    WeakReference weakRef;
    if (!this.items.TryGetValue(key, out weakRef)) {
        value = null;
        return false;
    } else {
        value = (TValue)weakRef.Target;
        if (value == null)
            this.items.Remove(key);
        return (value != null);
    }
}

或者，您可以在需要时立即在字典中创建一个新实例：

public TValue GetOrCreate(TKey key, Func<Tkey, TValue> ctor) {

    WeakReference weakRef;
    if (!this.items.TryGetValue(key, out weakRef) {
        Tvalue result = ctor(key);
        this.Put(key, result);
        return result;
    } 

    value = (TValue)weakRef.Target;
    if (value == null)
    {
        Tvalue result = ctor(key);
        this.Put(key, result);
        return result;
    }

    return value;
}

然后您可以像这样使用它：

static Foo CreateFoo(int id)
{
    return cache.GetOrCreate(id, id => new Foo(id));
}

[Edit]

根据windbg，单独的WeakReference实例占用16字节。对于十万件收集的物品来说，这并不算什么严重的负担，所以你可以轻松地让它们活下去。

如果这是一个服务器应用程序，并且您认为可以从收集中受益，我会考虑使用后台线程，但也会实现一个简单的算法，以便在收集相对少量的对象时增加等待时间 。

Answer 7

一点专业化：当目标类知道弱字典引用及其 TKey 值时，您可以从 Finalyzer 调用中删除其条目。

public class Entry<TKey>
{
    TKey key;
    Dictionary<TKey, WeakReference> weakDictionary;

    public Entry(Dictionary<TKey, WeakReference> weakDictionary, TKey key)
    {
        this.key = key;
        this.weakDictionary = weakDictionary;
    }

    ~Entry()
    {
        weakDictionary.Remove(key);
    }
}

当缓存对象是 Entry 的子类时，不会发生空 WeakReference 泄漏
因为 Finalyzer 在其实例被垃圾收集后被调用。