.NET、特にマルチスレッド用のコードを作成するすべての人にこんにちは。 スレッドセーフコレクションのないスレッドセーフコードはめったに表示されません。つまり、それらを使用できる必要があります。 最も人気のあるConcurrentDictionaryについて説明します。 驚くべきことに、多くの興味深い驚きがそこに隠されています：楽しいものとそうでないものの両方。

まず、ConcurrentDictionaryデバイスとそれを使用した操作の計算の複雑さを調べてから、メモリトラフィックとガベージコレクションに関連する便利なトリックと落とし穴について説明します。

適用領域

この記事のすべての観察結果は、発行時点で最新バージョンの.NET Framework（4.7.1）でテストされています。 おそらく.NET Coreには当てはまりますが、このステートメントを確認することは読者にとっての課題です。

デバイスについて簡単に

ConcurrentDictionaryには、内部でおなじみのハッシュテーブル実装があります。 これは、いわゆるバケットの配列に基づいており、それぞれが特定のハッシュ関数値のセットに対応しています。 各バケットには要素の単一リンクリストが含まれています。衝突が発生した場合、キーの線形検索がその中で実行されます。

スレッドロックは、 ストライプロックと呼ばれる技術によって保証されます。 通常のロックの小さな配列があり、それぞれがバケットの全範囲を担当しています（そのため、名前にストライプがあります）。 任意のバケットに何かを書き込むには、対応するロックをキャプチャする必要があります。 通常、バケットよりもはるかに少ないロックがあります。

そして、これらの概念がコンストラクターパラメーターConcurrentDictionary(int concurrencyLevel, int capacity)



とどのように関係するかを以下に示します。

• capacity
  
  
  
  -バケットの数。 デフォルトは31です。
• concurrencyLevel
  
  
  
  ロックの数。 デフォルトは4×コア数です。

実装はバケットのサイズを小さく保ち、必要に応じてその数を増やします。 展開すると、次のことが発生します。

• 容量は約2倍になります。 おおよそ、値は2、3、5、および7で割り切れないように選択されているためです（容量を単純な、または因数分解が不十分な数にすることが有用です ）。
• concurrencyLevel
  
  
  
  明示的に設定さconcurrencyLevel
  
  
  
  いない場合、ロックの数は2倍になります。 それ以外は同じです。

操作の複雑さ

N個の要素とK個のロックを含む辞書の要約プレート：

残りの操作は、これらから派生しています。

• GetOrAdd
  
  
  
  = TryGetValue
  
  
  
  + TryAdd
  
  
  
  
• AddOrUpdate
  
  
  
  = TryGetValue
  
  
  
  + TryAdd
  
  
  
  + TryUpdate
  
  
  
  
• Indexer(get)
  
  
  
  = TryGetValue
  
  
  
  
• TryAdd



Indexer(set)
  
  
  
  = TryAdd
  
  
  
  Overwrite

悪いニュース

CountプロパティとIsEmptyプロパティは、辞書のすべてのロックを暗黙のうちにキャプチャします 。 これらのプロパティを複数のスレッドから頻繁に呼び出さないようにすることをお勧めします。

キーと値のプロパティはさらに潜行性が高く、すべてのロックを取得するだけでなく、 すべてのキーと値を別のListにコピーします 。 同様のプロパティが「薄い」ラッパーを返す従来の辞書とは異なり、ここでは大きなメモリ割り当てに備える必要があります。

このような露骨な非効率性は、スナップショットのセマンティクスを提供したいという欲求によって引き起こされます。つまり、ある時点で存在した一貫した状態を返すことです。

良いニュース

そんなに悪くない。 まず、最も一般的な列挙（GetEnumeratorを使用）は非ブロッキングであり、不要なデータコピーなしで機能します。 スナップショットのセマンティクスがないため、これに費用を支払う必要があります。転送すると、並列記録操作の結果が反映される場合があります。

2番目の良いニュース：多くの場合、この動作は許容されるか、完全に望ましいものであり、これを使用できます。 たとえば、キーまたは値を効率的にリストするには：

 var keys = dictionary.Select(pair => pair.Key); var values = dictionary.Select(pair => pair.Value);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ヒントとコツ

通常の辞書とは異なり、列挙中にConcurrentDictionaryから直接挿入または削除できます！ これにより、たとえば、キャッシュディクショナリから古い要素をライフタイムで簡単に削除できます。

 foreach (var pair in cache) { if (IsStale(pair.Value)) { cache.TryRemove(pair.Key, out _); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

キーだけでなく、キーと値の正確な一致によって、またアトミックに要素を削除できます！ これは、ICollectionインターフェイスの明示的な実装の背後に隠されている文書化されていない機能です。 値の更新により、競合状態でもこのようなキャッシュを安全にクリアできます。

 var collection = cache as ICollection<KeyValuePair<MyKey, MyValue>> foreach (var pair in cache) { if (IsStale(pair.Value)) { // Remove() will return false in case of race with value update var removed = collection.Remove(pair); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

誰もがすでにこれを知っていますが、私に思い出させてください：競争力のあるアクセスの条件では、GetOrAddは1つのキーのデリゲートファクトリを何度も呼び出すことができます。 これが不可能または高価な場合は、Lazyで値をラップするだけです。

 var dictionary = new ConcurrentDictionary<MyKey, Lazy<MyValue>>(); var lazyMode = LazyThreadSafetyMode.ExecutionAndPublication; var value = dictionary .GetOrAdd(key, _ => new Lazy<MyValue>(() => new MyValue(), lazyMode)) .Value;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

GCオーバーヘッド

数万の要素から始まる大きな辞書を使用する場合、通常の辞書とは異なり、各要素のConcurrentDictionaryのヒープに追加のオブジェクトが作成されることを覚えておく必要があります。 数千万の要素を持つ常駐ConcurrentDictionaryは、第2世代のガベージコレクションで2番目のブレークを簡単に提供できます。

 // Only a handful of objects in final dictionary. // Value types dominate in its internals. Dictionary<int, int> ordinary = Enumerable .Range(0, 10 * 1000 * 1000) .ToDictionary(i => i, i => i); // ~10kk objects in concurrent version (due to linked lists). var concurrent = new ConcurrentDictionary<int, int>(ordinary);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

既存の値を上書きすると、新しいオブジェクトが割り当てられ、メモリトラフィックが発生する場合があります。 これは、言語標準が値型レコードの原子性を保証しない場合に発生します。 例：

• 値がintまたは参照型の場合、そのエントリはアトミックです。 その後、新しいオブジェクトを選択せず​​に、インプレースで書き換えが行われます。
• 値がGuidまたは別の「ワイド」値タイプの場合、そのレコードはアトミックではありません。 ここで、実装は新しい内部オブジェクトの作成を強制されます。

DotNext 2017モスクワでのタスク

この記事は、2017年秋に社内ソーシャルネットワークで初めて公開しました。 そして、昨年11月にモスクワで開催されたDotNextカンファレンスに出席した同僚は、Konturスタンドで解決できる記事に基づいてタスクを実行しました。

コードのスニペットがありました：

 public void TestIteration(ConcurrentDictionary<int, int> dictionary) { Parallel.For(0, 1000, new ParallelOptions { MaxDegreeOfParallelism = 8 }, (i) => { foreach (var keyValuePair in dictionary) { dictionary.AddOrUpdate(keyValuePair.Key, (key) => i, (key, value) => i); } }); } public void TestKeysProperty(ConcurrentDictionary<int, int> dictionary) { Parallel.For(0, 1000, new ParallelOptions { MaxDegreeOfParallelism = 8 }, (i) => { foreach (var key in dictionary.Keys) { dictionary.AddOrUpdate(key, (k) => i, (k, value) => i); } }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、3つの質問-操作の数、メモリ、実行時間の観点から、TestIterationメソッドとTestKeysPropertyメソッドの有効性を比較する必要がありました。 この記事を注意深く読んだ場合、3つのケースすべてでTestIterationがより効果的であることは明らかです。

結論

並列プログラミングツールは、パフォーマンスに関しては明らかな微妙な点でいっぱいです。たとえば、ConcurrentDictionaryを不注意に使用すると、メモリ内でグローバルロックと線形コストが発生する場合があります。 このチートシートが、アプリケーションで次のキャッシュまたはインデックスを作成するときに熊手を踏まないようにするのに役立つことを願っています。

すべての優れた効率的なコード！