Lockfreeコレクションの作成方法

Question

コレクションのコレクションを作成する必要があります。コレクションは、アイテムとルックアップアイテムを追加するために複数のスレッドによって呼び出されます。追加されたアイテムは削除されません。現在、要素を追加しているうちにコレクション全体をロックする必要があります。それをロックフリーにする方法がありますか？または、私が使用できるより良いデータ構造またはパターンがありますか？ここ は、私のコードの簡易版である：

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>(); 

void AddUpdateItem(string s, int k, int v) 
{ 
    ConcurrentDictionary<int, int> subDict; 
    if (dict.TryGetValue(s, out subDict)) 
    { 
     subDict[k] = v; 
    } 
    else 
    { 
     lock (dict) 
     { 
      if (dict.TryGetValue(s, out subDict)) 
      { 
       subDict[k] = v; 
      } 
      else 
      { 
       subDict = new ConcurrentDictionary<int, int>(); 
       subDict[k] = v; 
       dict[s] = subDict; 
      } 
     } 
    } 
} 

Answer 1

メソッドConcurrentDictionary.GetOrAddは、スレッドセーフです（ただし、アトミックではありません）。返されるオブジェクトがすべてのスレッドで同じであることが保証されます。あなたのコードは次のように書き直すことができます：

void AddUpdateItem(string s, int k, int v) 
{ 
    var subDict = dict.GetOrAdd(s, _ => new ConcurrentDictionary<int, int>()); 
    subDict[k] = v; 
} 

Answer 2

あなたのコード内のタスクまたはスレッドを使用していますか？どんな場合でも、ConcurrentDictionaryはスレッドセーフであるように設計されています。要素の追加または削除中にロ​​ックを使用する必要はありません。 MSDN How to: Add and Remove Items from a ConcurrentDictionaryからのリンクは、その使い方を説明しています。

Answer 3

不変性を使用してハッシュテーブルをロックフリーにすることはできますが、競合が発生すると効率的ではありません。基本的には、アトミックにスワップできる辞書コンテンツクラスが必要です。 1つの変更を加えて現在のコンテンツのコピーを作成し、次に比較とスワップのプリミティブを使用して既存のバージョンと交換します。比較とスワップに失敗した場合は、コピーステップからやり直してください。

アトミックに1つのハッシュバケットをスワップするだけで、競合を少なくすることができ、安価に再試行することができます。 （ロックの競合を減らすために、ConcurrentDictionaryはすでにこの最適化を使用していますが）バケットの数を増やすには、上記の方法が必要です。

Eric Lippertのブログでは、不変のデータ構造を扱っています。彼はa nice example of a binary treeを持っています。これは、ロックレスのハッシュテーブルを作るのに必要なテクニックを示すはずです。

Answer 4

あなたは投機サブディクショナリを作成する場合は、簡単な解決策がある：

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>(); 

void AddUpdateItem(string s, int k, int v) 
{ 
    ConcurrentDictionary<int, int> subDict; 

    while (true) 
    { 
     if (dict.TryGetValue(s, out subDict)) 
     { 
      subDict[ k ] = v; 
      break; 
     } 

     // speculatively create new sub-dictionary 
     subDict = new ConcurrentDictionary<int, int>(); 
     subDict[ k ] = v; 

     // this can only succeed for one thread 
     if (dict.TryAdd(s, subDict)) break; 
    } 
} 

Answer 5

あなたがロックレス収集を実現するための道を行く前には、あなたの問題を解決ReadWriteLockを見ています。そうでない場合（たとえば、書き込み競合が重いため）、実際には1つのサイズにすべてのアプローチはありません。

過去に私が使用していた手法の1つは、コレクションを管理する専用のスレッドを持ち、Interlocked.Exchangeを使用して新しいオブジェクトをそのスレッドと不変なコレクションにマーシャリングすることです。このアプローチでは、ライタースレッドは、ライターが作成または破棄されるたびにロックする必要がある別のリストで管理されるため、まれなイベントの場合にのみ動作します。