ConcurrentDictionary vs. Dictionary+Locking - Dennis Gao

クズども · 掲載地 2016/09/13 13:33:04

.NET 4.0以前は、マルチスレッド環境で辞書クラスを使う必要がある場合、スレッドの安全性を守るために自分たちでスレッド同期を実装せざるを得ませんでした。

多くの開発者は、まったく新しいスレッドセーフ辞書型を作成するか、辞書オブジェクトをクラスにカプセル化し、すべてのメソッドにロック機構を加える「Dictionary + Locks」という類似のスレッドセーフソリューションを実装しています。

しかし今はConcurrentDictionaryがあります。 MSDNのDictionaryクラスドキュメントのスレッドセーフ説明には、スレッドセーフ実装を使う場合はConcurrentDictionaryを使うと記載されています。

つまり、スレッドセーフな辞書クラスができたので、自分たちで実装する必要はもうありません。素晴らしいですよね?

問題の起源

実際、CocurrentDictionaryを一度だけテストでレスポンシブネスを試したことがあります。テストで良い成績を収めたので、すぐにクラスに差し替えてテストをしましたが、何か問題が起きました。

では、何がうまくいかなかったのでしょうか? スレッドセーフって言ってなかった?

さらにテストを重ねた結果、問題の根本原因が分かりました。しかしなぜか、MSDN バージョン4.0にはDelegate型パラメータを渡す必要があるGetOrAddメソッド署名の記述が含まれていません。バージョン4.5を見てみると、次のような注意書きを見つけました:

GetOrAddを異なるスレッドで同時に呼び出す場合、addValueFactoryは複数回呼び出されることがありますが、そのキー/値ペアがすべての呼び出しで辞書に追加されるわけではありません。
それが私が直面した問題です。ドキュメントに記載されていなかったため、問題を確認するためにさらにテストを行う必要がありました。もちろん、私が直面している問題は使用方法に関連しています。一般的に、私は辞書タイプを使ってデータをキャッシュしています:

このデータの作成は非常に遅いです。
このデータは一度しか作成できません。なぜなら、2回目の作成で例外が出たり、複数回作成するとリソースの漏洩などが発生する可能性があるからです。
私は2つ目の条件に問題がありました。両方のスレッドでデータが存在しないと判明した場合、一度だけ作成されますが、結果が一つだけ保存されます。もう一人はどうですか?

作成したプロセスが例外を出した場合は、tryを使えます: キャッチ(洗練されていないが問題は解決する)。しかし、資源が創造されていてリサイクルされなかったらどうでしょうか?

オブジェクトは作成され、参照されなくなった場合にガビジコレクションされると言えるかもしれません。しかし、以下に述べた状況が起きたらどうなるかを考えてみてください。

Emitで動的にコードを生成します。この手法をリモティングフレームワークで使い、すべての実装をリサイクルできないアセンブリにまとめました。もし型が二度作成された場合、二度目は一度も使われていなくても常に存在します。
直接的または間接的にスレッドを作成しましょう。例えば、非同期メッセージを処理するために独自のスレッドを使用し、受信順に依存するコンポーネントを構築する必要があります。コンポーネントがインスタンス化されると、スレッドが作成されます。このコンポーネントインスタンスが破壊されると、スレッドも終了します。しかし、コンポーネントを破棄した後にオブジェクトへの参照を削除しても、スレッドが何らかの理由で終了せず、オブジェクトへの参照を保持し続ける場合、そして、もし糸が枯れなければ、そのオブジェクトもリサイクルされません。
P/Invoke操作を実行します。受信ハンドルの閉じ時間の数が開口数と同じであることを要求します。
確かに、似たような状況はたくさんあります。例えば、辞書オブジェクトはリモートサーバー上のサービスへの接続を保持しており、そのサービスは一度だけリクエスト可能です。2回目にリクエストされると、他のサービスは何らかのエラーが発生したと判断し、ログに記録します。 (私が働いていた会社では、この状態に対する法的処罰がありました。) ）
ですので、Dictionary + Locksはドキュメント上スレッド安全と書かれていても、すぐにConcurrentDictionaryに置き換えられるわけではないことは明らかです。

問題を分析する

まだわからない?

この問題は辞書+ロックのアプローチでは生じないかもしれません。具体的な実装によりますので、この簡単な例を見てみましょう。

ログインが見えます。

上記のコードでは、キー値のクエリを始める前に辞書のロックを保持します。指定されたキー-値ペアが存在しない場合は、直接作成されます。同時に、すでにその辞書にロックを保持しているため、鍵と値のペアを直接辞書に追加することも可能です。その後、辞書ロックを解除し、結果を返します。もし2つのスレッドが同じキー値を同時にクエリしている場合、最初に辞書ロックを取得したスレッドがオブジェクトの作成を完了し、もう一方のスレッドはこの作成完了を待ち、辞書ロックを取得した後に作成されたキー値の結果を受け取ります。

いいことだろ?

本当にそうじゃない! このように並列でオブジェクトを作成し、最終的に一つだけを使う場合、私が述べた問題が起きないと思います。

私が詳しく説明しようとしている状況や問題は、必ずしも再現可能とは限りません。並列環境では、単に2つのオブジェクトを作成し、1つを破棄するだけで済みます。では、Dictionary + LocksとConcurrentDictionaryをどのように正確に比較すればよいのでしょうか?

答えは、ロックの使い方や辞書の使い方によります。

ゲーム1:同じオブジェクトを並行して作成

まず、オブジェクトが2回作成可能だと仮定しましょう。では、2つのスレッドが同時にそのオブジェクトを作成したらどうなるのでしょうか?

次に、似たような作品にどれくらいの時間をかけているのか?

オブジェクトのインスタンス化に10秒かかるという例を簡単に作ることができます。最初のスレッドが5秒後にオブジェクトを作成すると、2番目の実装はGetOrAddメソッドを呼び出してオブジェクトを取得しようとし、オブジェクトがまだ存在しないため、同時にオブジェクトの作成を開始します。

この状態では、2つのCPUが5秒間並列に動作し、最初のスレッドが動作を終えた後も、2番目のスレッドはオブジェクトの構築を完了するために5秒間動作を続ける必要があります。 2番目のスレッドがオブジェクトの構築を終えると、すでにオブジェクトが存在することが判明し、既存のオブジェクトを使い、新たに作成されたオブジェクトを直接破棄することを選択します。

もし2番目のスレッドが単に待機し、2つ目のCPUが他の作業(他のスレッドやアプリケーションの実行など)を行って電力を節約すれば、10秒ではなく5秒で目的のオブジェクトを取得できます。

この条件下では、Dictionary + Locksは小さなゲームに勝ちます。

ゲーム2:異なるオブジェクトを並行して訪れる

いいえ、あなたが言った状況は全く違います!

上記の例は少し変わっていますが、問題の本質を説明しています。ただ、この使い方がより極端なだけです。では、最初のスレッドがオブジェクトを作成していて、2番目のスレッドが別のキー-値オブジェクトにアクセスする必要があり、そのキー-値オブジェクトがすでに存在している場合、どうなるでしょうか?

ConcurrentDictionaryではロックフリー設計により、リードにロックがかからないため、読み取りが非常に高速になります。 Dictionary + Locksの場合、リード操作は全く異なるキーであっても相互排他的にロックされるため、明らかに読み取り操作が遅くなります。

このようにして、ConcurrentDictionaryはゲームを後退させました。

注:ここでは、辞書クラスでバケツ/ノード/エントリーなどの概念を理解していると考えます。もし理解していなければ、Ofir Makmalの「Understanding Generic Dictionary indepth」という記事を読むことをお勧めします。そこではこれらの概念がよく説明されています。

ゲームの第3ゲーム:もっと読むと単に書く

Dictionary + Locksで辞書のフルロックではなく、Multiple ReadersとSingle Writerを使ったらどうなりますか?

スレッドがオブジェクトを作成し、アップグレード可能なロックを保持してオブジェクトが作成された場合、そのロックが書き込みロックにアップグレードされ、読み込み操作を並列で実行できます。

また、読み取り操作を10秒間アイドル状態にすることで問題を解決することもできます。しかし、読み込み数が書き込みをはるかに上回る場合でも、ConcurrentDictionaryはロックフリーモードの読み取りを実装しているため、依然として高速であることがわかります。

辞書にReaderWriterLockSlimを使うと読み取りが悪化するため、一般的にはReaderWriterLockSlimの代わりにFull Lockを辞書に使うことが推奨されます。

こうした状況下で、ConcurrentDictionaryはまた一つのゲームに勝利しました。

注:YieldReaderWriterLockおよびYieldReaderWriterLockSlimクラスについては、以前の記事で取り上げました。この読み書きロックを使用することで速度が大幅に向上し(現在はSpinReaderWriterLockSlimへと進化)、複数の読み込みを並列にほとんど影響なく実行できるようになりました。この方法を使っている間は、ロックなしのConcurrentDictionaryの方が明らかに速いでしょう。

ゲーム4:複数のキー値ペアを追加する

対決はまだ終わっていない。

もし複数のキー値を加えていて、それらすべてが衝突せず、異なるバケットに割り当てられたらどうでしょうか?

最初はこの質問が不思議でしたが、当てはまらないテストをしてみました。型<int, int>の辞書を使ったところ、オブジェクトの構築工場はキーとして直接否定的な結果を返していました。

ConcurrentDictionaryが一番速いと思っていましたが、実際は一番遅いと分かりました。一方、Dictionary + Locksはより速く動作します。それはどうしてですか。

これは、ConcurrentDictionaryがノードを割り当てて異なるバケットに分けているためで、読み込み操作のロックフリー設計を満たす最適化が施されているためです。しかし、キー値項目を追加すると、ノード作成のプロセスがコストがかかります。

並列状態でも、ノードロックを割り当てるのはフルロックを使うよりも多くの時間を消費します。

つまり、Dictionary + Locksがこのゲームに勝つ。

第5ゲームをプレイする際:読み取り操作の頻度が高まる

率直に言って、もしオブジェクトを素早くインスタンス化できる代理がいれば、辞書は必要ありません。直接代表者に電話して物を取りに行ってもらえますよね?

実際、答えは状況によっても変わるということです。

キー型が文字列で、ウェブサーバー内のさまざまなページのパスマップを含み、対応する値がオブジェクトタイプで、現在ページにアクセスしているユーザーの記録とサーバー開始以降のすべてのページ訪問回数を含んでいるとします。

このようなオブジェクトを作るのはほぼ瞬時に起こります。その後は新しいオブジェクトを作成する必要はなく、保存した値を変更すればいいだけです。したがって、1つのインスタンスだけを使うまで2回ウェイの作成を許可することが可能です。しかし、ConcurrentDictionaryはノードリソースの割り当てが遅いため、Dictionary + Locksを使うと作成時間が短縮されます。

この例は非常に特別で、Dictionary + Locksはこの条件下でより良いパフォーマンスを発揮し、時間も短くなります。

ConcurrentDictionaryのノード割り当ては遅いですが、時間を試すために1億個のデータ項目を入れようとはしませんでした。なぜなら、それには明らかに多くの時間がかかるからです。

しかしほとんどの場合、データ項目が作成されると、必ず読み込まれます。データ項目の内容がどのように変わるかは別の問題です。したがって、データ項目の作成に何ミリ秒かかっても、読み取りは速く(ほんの数ミリ秒速いだけです)、読み取りはより頻繁に行われます。

つまり、ConcurrentDictionaryが勝ったのです。

ゲーム6:異なる時間を消費するオブジェクトを作成する

異なるデータ項目の作成にかかる時間が変わったらどうなりますか?

異なる時間を消費する複数のデータ項目を作成し、それらを辞書に並行して追加します。これがConcurrentDictionaryの最大の強みです。

ConcurrentDictionaryは複数の異なるロック機構を使ってデータ項目を同時に追加できますが、どのロックを使うかの決定やバケットのサイズを変更するためのロックの要求などのロジックは役に立ちません。データ項目がバケットに入力される速度は機械の高速です。 ConcurrentDictionaryが本当に勝つ理由は、並列でオブジェクトを作成できる能力です。

しかし、実際には同じことができるのです。オブジェクトを並列で作成しているか、破棄されているかを気にしなければ、ロックを追加してデータ項目が既に存在しているかを検出し、ロックを解除してデータ項目を作成し、ロックを押してロックを取得し、再度データ項目が存在するか確認し、存在しなければデータ項目を追加できます。コードは次のようなものかもしれません:

ログインが見えます。

* なお、私はタイプ<int, int>の辞書を使用しています。

上記の単純な構造では、Dictionary + Locksは並列条件でデータ項目の作成・追加においてConcurrentDictionaryとほぼ同等の性能を発揮します。しかし、同じ問題として、いくつかの値は生成されても実際には使われないこともあります。

結論

では、結論はあるのでしょうか?

現時点でも、まだ以下のものが残っています:

すべての辞書クラスは非常に速いです。何百万ものデータを作ってきましたが、それでも速いです。通常、私たちは少数のデータ項目しか作成せず、読み取りの間に一定の時間間隔があるため、データ項目の読み取りにかかる時間のオーバーヘッドはあまり気になりません。
同じオブジェクトを2回作成できない場合は、ConcurrentDictionaryを使用しないでください。
パフォーマンスが本当に気になるなら、Dictionary + Locksは良い解決策かもしれません。重要な要素の一つは、追加および削除されたデータ項目の数です。しかし、多くの読み込み操作がある場合は、ConcurrentDictionaryより遅くなります。
私が導入したわけではありませんが、実際にはDictionary + Locksスキームの使い方がより自由です。例えば、一度ロックして複数のデータを追加したり、複数のデータ項目を削除したり、複数回クエリを解除したりして、ロックを解除することができます。
一般的に、読み込み回数が書き込み回数を大きく上回る場合はReaderWriterLockSlimの使用を避けてください。辞書型はすでに読み取り-書き込みロックでリードロックを得るよりもはるかに高速です。もちろん、これはロック内でオブジェクトを作成するのにかかる時間にも依存します。
ですので、挙げられた例はやや極端だと思いますが、ConcurrentDictionaryを使うことが必ずしも最良の解決策とは限らないことを示しています。

違いを感じてみてください

私はより良い解決策を探すつもりでこの記事を書きました。

すでに特定の辞書クラスの仕組みをより深く理解しようとしています(今はとても理解できた気がします)。

ConcurrentDictionaryのBucketとNodeは非常にシンプルだと言えるでしょう。私も辞書クラスを作ろうとしたときに似たようなことをしました。通常の辞書クラスは一見単純に見えますが、実際にはより複雑です。

ConcurrentDictionaryでは、各ノードは完全なクラスです。 Dictionaryクラスでは、Nodeは値型で実装され、すべてのノードは巨大な配列にまとめられ、Bucketは配列のインデックス作成に使われます。また、ノードが次のノードに単純に参照する代わりに使われます(結局のところ、構造体タイプのノードであるため、構造体のノードメンバーを含むことはできません)。

辞書を追加・削除する際、辞書クラスは単に新しいノードを作成することはできず、削除されたノードを示すインデックスがあるかどうかを確認し、再利用しなければなりません。または「カウント」は配列内の新しいノードの位置を取得するために使われます。実際、配列が満杯になると、辞書クラスはサイズ変更を強制します。

ConcurrentDictionaryでは、ノードを新しいオブジェクトと考えることができます。ノードを削除するとは、単にその参照を取り除くことです。新しいノードを追加するだけで、新しいノードインスタンスを作成できます。サイズ変更は競合を避けるためだけで、必須ではありません。

では、もしDictionaryクラスが意図的により複雑なアルゴリズムを使って処理している場合、ConcurrentDictionaryはマルチスレッド環境でどのように性能向上を保証するのでしょうか?

実際のところ、すべてのノードを1つの配列に配置することが、データ項目の場所を管理するために別の配列が必要であっても、割り当てと読み取りに最も速い方法です。つまり、同じ数のバケットを持つとメモリが増えるようですが、新しいデータ項目の再割り当ては不要で、新しいオブジェクト同期も不要で、新しいガベージコレクションも発生しません。すべてがすでに整っているからです。

しかし、ノード内のコンテンツの置き換えは原子操作ではなく、これがスレッドを不安全にする要因の一つです。ノードはすべてオブジェクトであるため、最初にノードが作成され、その後別の参照が更新されて指向します(ここでの原子操作)。したがって、リードスレッドはロックなしで辞書の内容を読み取ることができ、読み取りは古い値と新しい値のいずれかでなければならず、不完全な値を読み取る可能性はありません。

つまり、ロックが必要ないなら、Dictionaryクラスの方が読み取りが速いです。なぜならロックが読み取りを遅くするからです。

この記事は、CodeProjectのPaulo Zemekによる「Dictionary + Locking versus ConcurrentDictionary」という記事から翻訳したもので、理解の都合で一部の文が変更される予定です。

クズども · 掲載地 2016/09/13 13:33:15

ConcurrentDictionaryは新規および更新された更新をサポートしています
http://www.itsvse.com/thread-2955-1-1.html
(出典:コード農業ネットワーク)

[出典] ConcurrentDictionary vs. Dictionary+Locking - Dennis Gao

関連記事

閲覧したセクション