压缩WeakReference词典

Question

我有一个带有属性Id的Foo类.我的目标是同时没有两个具有相同Id的Foo实例.

所以我创建了一个工厂方法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;
}

缓存实现为Dictionary <TKey,WeakReference>,基于@JaredPar的Building a WeakReference Hashtable:

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);
        }
    }
}

问题是WeakReferences在其目标被垃圾收集后仍保留在字典中.这意味着对于一些战略的必要性如何手动"垃圾收集"死在WeakReferences,通过解释@Pascal Cuoq在发生WeakReference.Target的GC后WeakReference的什么.

---

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

我看到的选项是:

1. 不要从字典中删除WeakReferences.IMO这很糟糕,因为缓存是在我的应用程序的整个生命周期中使用的,并且随着时间的推移会积累很多死的WeakReferences.

2. 在每个Put和TryGetValue上遍历整个字典,并删除死WeakReferences.这有点违背字典的目的,因为两个操作都变为O(n).

3. 在后台线程中定期遍历整个字典.考虑到我不知道CreateFoo的使用模式,什么是好间隔？

4. 将每个插入的KeyValuePair附加到双端链表.每次调用Put和TryGetValue都会检查列表的头部.如果WeakReference处于活动状态,请将该对移动到列表的末尾.如果它已死,请从列表中删除该对,并从Dictionary中删除WeakReference.

5. 实现一个自定义哈希表,其差别在于,当存储桶已满时,首先从存储桶中删除死WeakReferences,然后照常继续操作.

还有其他策略吗？

最佳策略可能是具有摊销时间复杂度的算法.这样的策略是否存在？

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中的所有项目时,那些TabItems可以被垃圾收集(因为没有任何时间再引用它们,同样ConditionalWeakTable的键也不计算).收集garabage时,将通知ConditionalWeakTable,并删除具有该键值的条目.所以我的庞大的TIDExec对象也在那时被垃圾收集(除了ConditionalWeakTable的值之外没有任何引用它们).

Answer 2

您的选项3(线程)的缺点是必须在所有Put/TryGetvalue操作上进行同步.如果您使用此方法,则您的间隔不是以毫秒为单位,而是每个N TryGet操作.

选项2,扫描字典,会产生严重的开销.您可以通过仅扫描1000个操作中的1个和/或通过观察GC运行的频率来改进.

但我会认真考虑选项1:什么都不做.您可能有"很多"死信条件,但另一方面它们非常小(并且可以回收).可能不是服务器应用程序的选项,但对于客户端应用程序,我会尝试测量我们所讨论的每小时条目数(kByte).

经过一番讨论后:

是否存在这种[摊销]策略？

我猜不会.您的问题是GC的缩小版.您将不得不偶尔扫描整个事物.因此,只有选项2)和3)提供了真正的解决方案.它们既昂贵又可以通过一些启发式方法进行(大量)优化.选项2)仍然会给你偶尔的最坏情况.