原子AddOrUpdate在C＃字典 [英] Atomic AddOrUpdate on C# Dictionary

问题描述

假设下面的代码：

if (myDictionary.ContainsKey(aKey))
    myDictionary[aKey] = aValue;
else
    myDictionary.Add(aKey, aValue);

这代码访问字典两次，一次确定是否的aKey 的存在，其他时间用于更新（如果存在）或增加（如果不存在）。我想这方法的性能是可以接受的时候只有几次执行该代码。然而，在我的应用程序类似的代码被执行大约50万次。我异形我的代码，它显示的花在这部分CPU时间的80％（见下图），所以这种激励的改善。

This code accesses the dictionary two times, once for determining whether aKey exist, another time for updating (if exist) or adding (if does not exist). I guess the performance of this method is "acceptable" when this code is executed for only few times. However, in my application similar code is executed roughly 500K times. I profiled my code, and it shows 80% of CPU time spent on this section (see following figure), so this motivates an improvement.

需要注意的是，该词典是 lambda表达式。

第一个解决方法很简单：

myDictionary[aKey] = aValue;

如果的aKey 存在它的价值被替换安勤;如果它不存在，一个 KeyValuePair 与的aKey 为键和安勤的值被添加到 myDictionary 。但是，这种方法有两个缺点：

If aKey exist it's value is replaced by aValue; if does not exist, a KeyValuePair with aKey as key and aValue as value is added to myDictionary. However, this method has two drawbacks:

的首页的，你不知道，如果的aKey 存在或不是阻止你额外的逻辑。举例来说，你不能重写基于此解决方法如下代码：

First, you don't know if aKey exist or not that prevents you from additional logics. For instance, you can not rewrite following code based on this workaround:

int addCounter = 0, updateCounter = 0;
if (myDictionary.ContainsKey(aKey))
{
    myDictionary[aKey] = aValue;
    addCounter++;
}
else
{
    myDictionary.Add(aKey, aValue);
    updateCounter++;
}

的二的，更新不能是一个函数旧的价值。举例来说，你不能做类似的逻辑：

Second, the update can not be a function of the old value. For instance, you can not do a logic similar to:

if (myDictionary.ContainsKey(aKey))    
    myDictionary[aKey] = (myDictionary[aKey] * 2) + aValue;    
else    
    myDictionary.Add(aKey, aValue);

第二个解决方法是使用 ConcurrentDictionary 。很明显，使用代表就可以解决的第二的上述问题;然而，它仍然是我不清楚如何才能解决的第一个的问题。

Second workaround is to use ConcurrentDictionary. It's clear that using delegates we can solve the second aforementioned issue; however, still it is not clear to me how we can address the first issue.

只是提醒，我关心的是来加速。由于只有一个使用此过程的线程，我不认为并发性（有锁）的处罚只有一个线程值得使用 ConcurrentDictionary 。

Just to remind, my concern is to speed-up. Given that there is only one thread using this procedure, I don't think the penalty of concurrency (with locks) for only one thread worth using ConcurrentDictionary.

我缺少了点？有没有人有更好的建议？

Am I missing a point ? does anyone has a better suggestion ?

推荐答案

如果你真的想 AddOrUpdate 法像 ConcurrentDictionary ，但没有使用一个性能的影响，你将不得不自己实现这样的解释。

If you really want AddOrUpdate method like in ConcurrentDictionary but without performance implications of using one, you will have to implement such Dictionary yourself.

好消息是，由于CoreCLR是开源的，你可以从的 CoreCLR库并应用自己的修改。这似乎也不会那么辛苦，看看那里的插入私有方法。

The good news is that since CoreCLR is open source, you can take actual .Net Dictionary source from CoreCLR repository and apply your own modification. It seems it will not be so hard, take a look at the Insert private method there.

一种可能的实现将是（未经测试）：

One possible implementation would be (untested):

public void AddOrUpdate(TKey key, Func<TKey, TValue> adder, Func<TKey, TValue, TValue> updater) {

    if( key == null ) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets == null) Initialize(0);
    int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
    int targetBucket = hashCode % buckets.Length;

    for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
        if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
            entries[i].value = updater(key, entries[i].value);
            version++;
            return;
        } 

    }
    int index;
    if (freeCount > 0) {
        index = freeList;
        freeList = entries[index].next;
        freeCount--;
    }
    else {
        if (count == entries.Length)
        {
            Resize();
            targetBucket = hashCode % buckets.Length;
        }
        index = count;
        count++;
    }

    entries[index].hashCode = hashCode;
    entries[index].next = buckets[targetBucket];
    entries[index].key = key;
    entries[index].value = adder(key);
    buckets[targetBucket] = index;
    version++;

}

这篇关于原子AddOrUpdate在C＃字典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！