Atomic AddOrUpdate for C＃Dictionary [英] Atomic AddOrUpdate for a C# Dictionary

问题描述

假设以下代码：

  if（myDictionary.ContainsKey（aKey））
 myDictionary [aKey] = aValue ; 
 else 
 myDictionary.Add（aKey，aValue）; 
  

此代码访问字典两次，一次确定是否 aKey 存在，另一次更新（如果存在）或添加（如果不存在）。我猜这个方法的性能是可接受的当这个代码执行只有几次。但是，在我的应用程序中，类似的代码执行了大约500K次。我分析了我的代码，它显示了80％的CPU时间花在这一部分（见下图），所以这样做有所改善。

请注意，字典是 lambdas 。 p>

第一个解决方法只是：

  myDictionary [aKey] = aValue; 
  

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

首先，您不知道 aKey 存在或不存在阻止你附加的逻辑。例如，您不能根据此解决方法重写以下代码：

  int addCounter = 0，updateCounter = 0; 
 if（myDictionary.ContainsKey（aKey））
 {
 myDictionary [aKey] = aValue; 
 addCounter ++; 
} 
 else 
 {
 myDictionary.Add（aKey，aValue）; 
 updateCounter ++; 
} 
  

第二个，更新不能是一个功能的旧价值。例如，你不能做类似的逻辑：

  if（myDictionary.ContainsKey（aKey））
 myDictionary [aKey] =（myDictionary [aKey] * 2）+ aValue; 
 else 
 myDictionary.Add（aKey，aValue）; 
  

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

只是提醒一下，我关心的是加快。假设只有一个线程使用这个过程，我不认为只有一个线程使用 ConcurrentDictionary 的并发（带锁）的惩罚。我没想到一点吗？有没有人有更好的建议？

解决方案

如果你真的想要 AddOrUpdate c> ConcurrentDictionary 但没有使用一个的性能影响，您将不得不自己实现这样的字典。

好消息是，由于CoreCLR是开源，您可以从 CoreCLR存储库并应用您自己的修改。看起来不会那么难，看看那里的插入私有方法。

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

  public void AddOrUpdate（TKey key，Func< TKey，TValue&加法器，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）; 
版本++; 
 return; 
} 
 
} 
 int index; 
 if（freeCount> 0）{
 index = freeList; 
 freeList = entries [index] .next; 
 freeCount--; 
} 
 else {
 if（count == entries.Length）
 {
调整大小（）; 
 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; 
版本++; 
 
} 
  

Suppose following code:

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

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.

Note that, the dictionary is lambdas.

First workaround is simply:

myDictionary[aKey] = aValue;

If aKey exist it's value is replaced with 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:

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

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.

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 ?

解决方案

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

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++;

}

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