Atomic AddOrUpdate für eine C# Wörterbuch

Question

folgenden Code Angenommen:

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

Dieser Code das Wörterbuch zweimal zugreift, einmal zu bestimmen, ob aKey vorhanden sind, ein anderes Mal für die Aktualisierung (falls vorhanden) oder das Hinzufügen (falls nicht vorhanden). Ich denke, die Leistung dieser Methode ist "akzeptabel", wenn dieser Code nur wenige Male ausgeführt wird. In meiner Anwendung wird jedoch ein ähnlicher Code ungefähr 500K mal ausgeführt. Ich habe meinen Code profiliert und er zeigt 80% der CPU-Zeit, die für diesen Abschnitt aufgewendet wurde (siehe folgende Abbildung). Dies motiviert zu einer Verbesserung.

Beachten Sie, dass das Wörterbuch lambdas ist.

Erste Abhilfe ist einfach:

myDictionary[aKey] = aValue; 

Wenn aKey existieren es Wert ist mit aValue ersetzt wird; Wenn nicht vorhanden, wird KeyValuePair mit aKey als Schlüssel und aValue als Wert zu myDictionary hinzugefügt. Diese Methode hat jedoch zwei Nachteile:

Zuerst, Sie wissen nicht, ob aKey existiert oder nicht, die Sie von zusätzlichen Logiken verhindert. Zum Beispiel können Sie nicht folgenden Code neu schreiben, basierend auf dieser Problemumgehung:

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

Zweiter, kann das Update nicht eine Funktion des alten Wertes sein. Zum Beispiel können Sie eine Logik ähnlich wie nicht tun:

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

Zweite Abhilfe ist ConcurrentDictionary zu verwenden. Es ist klar, dass delegates wir das zweite genannte Problem lösen können; aber mir ist immer noch nicht klar, wie wir das erste Problem behandeln können.

Nur zur Erinnerung, mein Anliegen ist es, zu beschleunigen. Da es nur einen Thread gibt, der diese Prozedur verwendet, glaube ich nicht, dass die Penetration der Parallelität (mit Sperren) für nur einen Thread die Verwendung von ConcurrentDictionary wert ist.

Fehle ich einen Punkt? Hat jemand einen besseren Vorschlag?

Answer 1

Wenn Sie wirklich wollen AddOrUpdate Methode wie in ConcurrentDictionary, aber ohne Auswirkungen auf die Leistung der Verwendung eines, müssen Sie solche Wörterbuch selbst implementieren.

Die gute Nachricht ist, dass, da CoreCLR Open Source ist, Sie tatsächliche .Net Dictionary Quelle von CoreCLR repository nehmen und Ihre eigene Modifikation anwenden können. Es scheint, es wird nicht so schwer sein, werfen Sie einen Blick auf die Insert private Methode dort.

Eine mögliche Implementierung sei (nicht getestet):

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

}