原子AddOrUpdate爲C＃字典

Question

假設以下代碼：

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

該代碼訪問字典兩次，一次用於確定aKey是否存在，另一個時間更新（如果存在）或添加（如果它不存在）。我猜這個代碼只執行了幾次，這個方法的性能是「可以接受的」。但是，在我的應用程序中，類似的代碼大約執行了500K次。我對我的代碼進行了描述，它顯示了本節中花費的CPU時間的80％（請參見下圖），因此可以促進改進。

請注意，該字典是lambdas。

第一個解決辦法很簡單：

myDictionary[aKey] = aValue; 

如果aKey存在它的價值被替換aValue;如果不存在，則將KeyValuePair與aKey作爲關鍵字，並將aValue作爲值添加到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。很顯然，使用delegates我們可以解決上述問題第二;然而，仍然不清楚我們如何解決第一個問題。

只是提醒一下，我的擔心是加速。考慮到只有一個線程正在使用這個過程，我不認爲只有一個線程值得使用ConcurrentDictionary併發（帶鎖）的懲罰。

我錯過了一個觀點嗎？有沒有人有更好的建議？

Answer 1

如果你真的想AddOrUpdate方法像ConcurrentDictionary但沒有性能影響使用一個，你將不得不自己實現這樣的字典。

好消息是，由於CoreCLR是開源的，您可以從CoreCLR repository獲取實際的.Net Dictionary源代碼並應用您自己的修改。看來它不會那麼難，請看看Insert那裏的私人方法。

一種可能的實施將是（未經測試）：

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

}