1

私は最近、スキップリストデータ構造を使用して同時優先度キューを実装することに挑戦しました-この質問のために、スキップリストが何であるかわからない場合は、リンクリストを描くだけで十分だと思います答える。最小限のロックを試みました（つまり、複数のエンキューとデキューを同時に許可し、必要に応じてノードまたはそのフォワードポインターのみをロックし、できるだけ早くロックを解放し、Interlockedを使用してリストをトラバースするなど）。

結果に満足しました。ただし、同期ルートロックで囲まれた追加と削除を使用して通常のスキップリストを作成する（つまり、一度に1つの操作のみを許可する）と、実際には2倍の速度でした。

実装にバグがあるはずだと思いました。ただし、MicrosoftWebサイトにリストされている「ConcurrentPriorityQueue」でさえ、実際には一度に1つの操作しか許可されていません（つまり、エンキューとデキューの周りのsyncrootロック）

http://code.msdn.microsoft.com/Samples-for-Parallel-b4b76364/sourcecode?fileId=44488&pathId=1696822056

原則として（そしてこの質問が一般的すぎる場合はご容赦ください）、よりきめ細かいロックが実際にパフォーマンスの向上につながるのはどの時点ですか？私の場合、Interlocked.Exchange（より良い方法はありますか？）や複数のテストアンドテストアンドセットなどを使用して大きなリストを実際にトラバースする必要があるため、エンキューとデキューが遅くなると思います。

さらに、時間の大部分がどこで費やされているかを判断するのに役立つツールはありますか？ありがとう。

4

2 に答える 2

3

ロックされた領域が現在解放されているかどうかを常に確認し、ロックを設定してから、離れるときに解放するというオーバーヘッドがあります。実際には、有益な理由なしにそのオーバーヘッドを実行したばかりのクリティカルセクションへのアクセスについて、実際に他の誰かと競合することはめったにありません。一方、データ構造を使用しようとしているスレッドがたくさんある場合は、アクションを並行して実行することでパフォーマンスが向上し（コアCPUが多い場合）、ロック管理のオーバーヘッドを超える場合があります。

これらのタイプのデータ構造では、通常は相互に待機する必要のない操作を実行しながら、数十のスレッドがすべて同時にデータ構造を使用しようとすることはかなりまれなケースです。つまり、スレッドを追加し、スレッドがすべて実行していることを適切に管理することで、ロックケースのパフォーマンスを向上させるテストケースを生成できる可能性があります。現在のテストが実際にデータ構造をどのように使用するかを合理的に表したものである場合、明らかに、より複雑なロックスキームの恩恵を受けることはありません。

于 2012-10-19T14:18:50.187 に答える
1

同期すればするほど、アプリケーションのパフォーマンスが低下します。syncrootを使用すると問題が発生する可能性がありますが、複雑な状況では解決できません。

秘訣は、同期の適切なバランスを見つけることです。たとえば、競合状態がなくても、信頼性を確保するのに十分です。

System.Collections.Concurrent名前空間を見てください

于 2012-10-19T14:09:40.100 に答える