3

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

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;
            }
        }
    }
}
4

5 に答える 5

4

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

1 つのハッシュ バケットだけをアトミックに交換できる場合があります。これにより、競合がはるかに少なくなり、再試行のコストが低くなります。(ConcurrentDictionaryは、ロックの競合を減らすために、この最適化を既に使用しています) しかし、バケットの数を増やすには、上記で概説した方法が必要です。

不変データ構造について説明している Eric Lippert のブログをご覧ください。彼はバイナリ ツリーの良い例を持っています。これは、ロックのないハッシュ テーブルを作成するために必要なテクニックを示しているはずです。

于 2011-10-16T02:58:01.117 に答える
3

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

void AddUpdateItem(string s, int k, int v)
{
    var subDict = dict.GetOrAdd(s, _ => new ConcurrentDictionary<int, int>());
    subDict[k] = v;
}
于 2011-10-16T11:16:16.387 に答える
1

コードでタスクまたはスレッドを使用していますか? いずれにしても、ConcurrentDictionaryスレッドセーフになるように設計されています。要素の追加または削除中にロ​​ックを使用する必要はありません。MSDN からのリンク 方法: ConcurrentDictionary から項目を追加および削除する では、その使用方法について説明しています。

于 2011-10-16T02:49:40.057 に答える
0

ロックレスコレクションを実装する前に、問題を解決するReadWriteLockを見てください。そうでない場合 (たとえば、書き込みの競合が激しいなどの理由で) 万能のアプローチは実際にはありません。

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

于 2011-10-16T10:53:56.543 に答える
0

サブディクショナリを投機的に作成する場合は、より簡単な解決策があります。

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;
    }
}
于 2011-10-16T10:26:58.327 に答える