1

我目前正在编写一些对性能至关重要的代码，这些代码需要一种无需使用锁即可从键值存储中检索值的方法。

我曾尝试使用 ConcurrentDictionary，但在这种情况下，它的性能不足以满足我的需求。

所以我在这里追求的是类似于 ConcurrentDictionary 中的 GetOrAdd 方法，但我需要它超级快（没有锁）并且仍然是线程安全的:)

这里应该注意的是，假设我们将主要检索现有值而很少添加新值。还假设此列表不会很大。

我不是线程专家，所以如果有人可以评论我的想法，那就太好了。

public class Registry<TKey, TValue>
{
    private Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>();

    public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
    {
        TValue value;            
        if (!dictionary.TryGetValue(key, out value))
        {
            var snapshot = new Dictionary<TKey, TValue>(dictionary);
            if (!snapshot.TryGetValue(key, out value))
            {
                value = valueFactory(key);
                snapshot.Add(key, value);
                dictionary = snapshot;
            }                
        }
        return value;
    }
}

这里的“技巧”是创建实际字典的快照，如果我们确实需要向它添加新值。最后，我们交换引用，以便字典变量现在指向快照。请记住，我真的不在乎我是否在这里和那里丢失一两个更新。我需要的是真正快速检索现有值。

我对交换引用的代码有点不确定。

字典=快照；

如果另一个线程在交换引用的同时尝试访问字典变量会发生什么。这甚至是一个问题吗？

问候

伯恩哈德·里希特

4

3 回答 3

4

您的第一次拍摄几乎是正确的。交换引用是线程安全的，因为地址是原子更新的。但是当您想要更新字典时仍然需要锁定，因为您不想丢失任何并发更改。实现这一点的唯一方法是采取某种锁。

如果不这样做，您有时会使用较旧版本的字典，尽管在两者之间更新了引用，并且您的线程确实将引用与包含旧数据的更新字典交换。

MS Threading 手册还提到，当您很少更新字典时，ConcurrentDictionary 无法很好地扩展。在这种情况下，经典词典仍然更好。

我不知道您进入了哪个问题域，但可能是更改您正在处理的数据结构可能会给您带来比优化并发字典访问更多的性能。字典非常快，但 CPU 数据缓存不友好。如果您想获得更快的速度，可能需要摆脱字典，或者您需要不同的数据结构才能在内存中获得更多线性读取，这对缓存更加友好。

public class Registry<TKey, TValue>
{
    private Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>();
    private object Lock = new object();

    public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
    {
        TValue value;            
        if (!dictionary.TryGetValue(key, out value))
        {
            lock(Lock)
            {
              var snapshot = new Dictionary<TKey, TValue>(dictionary);
              if (!snapshot.TryGetValue(key, out value))
              {
                  value = valueFactory(key);
                  snapshot.Add(key, value);
                  dictionary = snapshot;
              }
            }   
        }
        return value;
    }
}
于 2012-08-02T23:11:40.783 回答
1

由于您的字典大小不大并且您不经常更新它，您可以使用双缓冲方法：

创建两个相同的字典，并从第一个开始阅读。将更新应用到第二个字典并交换引用，以便您现在从第二个字典中阅读。然后返回并将相同的更新应用于第一个字典。

将下一个更新应用到第一个字典，交换引用，然后更新第二个字典。等等，每次更新时在字典之间切换。

于 2012-08-03T19:29:34.997 回答
1

这是不正确的！字典的构造函数将在创建快照之前遍历整个字典。这可能导致不正确的快照状态。

如果 ConcurrentDictionary 对您没有帮助，您可以尝试使用不可变数据结构，例如前缀树（又名基数树或 trie）。这些是线程安全的。

于 2012-08-02T23:02:26.143 回答