1

私は現在、ロックを使用せずにKey-Valueストレージから値を取得する方法を必要とする非常にパフォーマンスが重要なコードを書いています。

ConcurrentDictionaryを使用してみましたが、この場合のニーズには十分ではありません。

したがって、ここで私が求めているのは、ConcurrentDictionaryにあるGetOrAddメソッドに似ていますが、超高速（ロックなし）であり、スレッドセーフである必要があります:)

ここで、ほとんどの場合、既存の値の取得を行い、新しい値を追加することはめったにないと想定されていることに注意してください。また、このリストはそれほど大きくなることはないと想定されています。

私はスレッディングの専門家ではないので、誰かが私が思いついたものについてコメントできればいいのですが。

public class Registry<TKey, TValue>
{
    private Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>();

    public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
    {
        TValue value;            
        if (!dictionary.TryGetValue(key, out value))
        {
            var snapshot = new Dictionary<TKey, TValue>(dictionary);
            if (!snapshot.TryGetValue(key, out value))
            {
                value = valueFactory(key);
                snapshot.Add(key, value);
                dictionary = snapshot;
            }                
        }
        return value;
    }
}

ここでの「トリック」は、実際に新しい値を追加する必要がある場合に、実際の辞書のスナップショットを作成することです。最後に、辞書変数がスナップショットを指すように参照を交換します。あちこちでアップデートを1つか2つ失っても、私は本当に気にしないことを忘れないでください。私が必要としているのは、既存の値を本当に高速に取得することです。

参照を交換するコードについては少しわかりません。

辞書=スナップショット;

参照が交換されると同時に別のスレッドがディクショナリ変数にアクセスしようとするとどうなりますか。それもここでの問題ですか？

よろしく

ベルンハルトリヒター

4

3 に答える 3

4

あなたの最初のテイクはほぼ正しいです。参照の交換は、アドレスがアトミックに更新されるという意味でスレッドセーフです。ただし、同時変更を失いたくないので、辞書を更新するときは、ロックをかける必要があります。これを達成する唯一の方法は、ある種のロックをかけることです。

そうしないと、参照が更新されていても古いバージョンの辞書を使用することがあり、スレッドは参照を古いデータを含む更新された辞書と交換します。

MS Threadingハンドブックには、辞書を更新することがめったにない場合、ConcurrentDictionaryはあまり拡張性がないことも記載されています。この場合、古典的な辞書の方が優れています。

どの問題ドメインでこれに遭遇したかはわかりませんが、作業中のデータ構造を変更すると、同時辞書アクセスを最適化するよりもさらにパフォーマンスが向上する可能性があります。辞書は非常に高速ですが、CPUデータキャッシュは使いにくいです。さらに高速にしたい場合は、辞書を削除する必要があるか、メモリ内でより線形な読み取りを行うために別のデータ構造が必要である可能性があります。これにより、キャッシュがはるかに使いやすくなります。

public class Registry<TKey, TValue>
{
    private Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>();
    private object Lock = new object();

    public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
    {
        TValue value;            
        if (!dictionary.TryGetValue(key, out value))
        {
            lock(Lock)
            {
              var snapshot = new Dictionary<TKey, TValue>(dictionary);
              if (!snapshot.TryGetValue(key, out value))
              {
                  value = valueFactory(key);
                  snapshot.Add(key, value);
                  dictionary = snapshot;
              }
            }   
        }
        return value;
    }
}
于 2012-08-02T23:11:40.783 に答える
1

これは正しくありません！辞書のコンストラクターは、スナップショットを作成する前に辞書全体を反復処理します。これにより、スナップショットの状態が正しくなくなる可能性があります。

ConcurrentDictionaryが役に立たない場合は、プレフィックスツリー（基数ツリーまたはトライ）などの不変のデータ構造を試すことができます。これらはスレッドセーフです。

于 2012-08-02T23:02:26.143 に答える
1

辞書のサイズは大きくなく、頻繁に更新しないため、ダブルバッファアプローチを使用できます。

2つの同一の辞書を作成し、最初から読みます。2番目のディクショナリに更新を適用し、参照を交換して、2番目のディクショナリから読み取れるようにします。次に、戻って同じ更新を最初の辞書に適用します。

次の更新を最初のディクショナリに適用し、参照を交換してから、2番目のディクショナリを更新します。など、更新するたびに辞書間でフリップフロップします。

于 2012-08-03T19:29:34.997 に答える