問題タブ [concurrentskiplistmap]

以下を置き換えるために、C++ でロックフリーのデータ構造を探しています。

セットは、最大で O(logN) の複雑さをサポート.insert()し.size()、イテレータを持ち、カスタム コンパレータで順序を維持できる必要があります。ConcurrentSkipListSet基本的に、Javaの と同じことを行います。理想的には、プラットフォームに依存しない必要があります。

CDS: http://libcds.sourceforge.net/doc/cds-api/modules.htmlを見ていますが、どのデータ構造が目標を達成できるかわかりません。ドキュメントには、一部のデータ構造について実際には複雑さがありません。

どんな提案も素晴らしいでしょう、ありがとう!

Java の Collections Framework のほとんどのクラスは、デフォルトでは非同期ですが、スレッドセーフにする必要がある場合は、同期するクラスにすることができます。同期にはパフォーマンスのペナルティがあるため、スレッドセーフである必要のないものを書いている場合は、非同期バージョンを使用する方がよいでしょう。

しかし、ConcurrentSkipListMapこのスキームには従いません。非同期バージョンはありません。SkipListMapCollections Framework の残りの部分に沿って、スレッド セーフを必要としないアプリケーション用のより高速な unsynchronized がないのはなぜですか?

私が考えることができるのは、Skip List の最も単純な実装はすでにスレッドセーフであるため、同期バージョンを使用してもパフォーマンスが低下することはないということだけです。これにはある程度の意味がありますが、ソース コードを調べても、それはまったくわかりません。コードにブロックはありませんがsynchronized、Javadoc は

このクラスは、SkipLists の並行バリアントを実装します...

これは、アルゴリズムを変更してスレッドセーフにするのが面倒であることを示唆しています。後で、私たちは読んだ

これらのリストの基本的な考え方は、同時挿入との競合を避けるために、削除時に削除されたノードの「次の」ポインタをマークすることです...

また、何らかのオーバーヘッドが関係しているようにも聞こえます。

このオーバーヘッドが非常に小さいため、非スレッドセーフにする価値がないというだけSkipListMapですか?

最近、調査ConcurrentSkipListMap中にその実装を調べたところ、その put メソッドがスレッドセーフではないことがわかりました。doPut実際にアイテムを追加する内部呼び出し。しかし、この方法ではConcurrentHashMap.

addしたがって、スレッドセーフかどうかを知りたいです。メソッドを見ると、スレッドセーフではないようです。つまり、このメソッドが 2 つのスレッドによって同時に実行されると、問題が発生する可能性があります。

ConcurrentSkipListMap内部でskiplistデータ構造を使用していることは知っていますが、addメソッドがスレッドセーフであることを期待していました。私は何か間違ったことを理解していますか? 本当にConcurrentSkipListMapスレッドセーフではありませんか?

にエントリを追加したり削除したりする複数のスレッドがあるとしますConcurrentSkipListMap。定義済みの期間にコレクションを実行し、イテレーターを使用してそのデータを更新する別のスレッドがあります。同時アクセスを考慮してこれを行う方法。どのように繰り返すのですか？イテレータは弱い整合性をサポートしていますか?

Comparator ベースのキー値マップを使用したいと考えています。これには、読み取り操作とまれな書き込み操作 (スケジューラーを介して 3 か月に 1 回) があります。コレクションの初期ロードは、アプリケーションの起動時に行われます。また、書き込みは次のことにも注意してください。

• 単一のエントリをマップに追加する
• マップへの既存のエントリを変更しません。

ConcurrentSkipListMap はこれの良い候補になるでしょうか。これに対する get 操作は、複数のスレッドに同時にアクセスできますか? 同時非ブロック読み取りであるがアトミック書き込みを探しています。