[解決済み】スキップリストとバイナリサーチツリーの比較

質問

として知られるデータ構造に最近出会いました。 スキップリスト . 二分探索木と非常によく似た動作をしているようです。

なぜ、バイナリサーチツリーではなく、スキップリストを使おうと思ったのでしょうか？

どのように解決するのか？

スキップリストは、同時アクセス/変更にもっと適応的です。 Herb Sutter は 記事 同時並行環境におけるデータ構造について より詳細な情報が載っています。

バイナリサーチツリーの実装で最もよく使われるのは 赤黒い木 . 同時進行の問題は、ツリーが変更されたときに、しばしばリバランスが必要になることです。 リバランス操作は、木の大部分に影響を与える可能性があり、木のノードの多くにミューテックスロックが必要になります。 ノードをスキップリストに挿入する場合は、はるかに局所的で、影響を受けるノードに直接リンクしているノードだけをロックする必要があります。

Jon Harropsのコメントからの更新

FraserとHarrisの最新論文を読みました。 ロックなしの並行プログラミング . ロックフリーのデータ構造に興味があるなら、本当に良いものだ。 この論文では トランザクショナルメモリ と理論演算であるmulti-word-compare-and-swap MCASがあります。 どちらもハードウェアではまだサポートされていないため、ソフトウェアでシミュレートしている。 MCASをソフトウェアで構築できたことに、かなり感心しています。

トランザクションメモリについては、ガベージコレクタが必要なため、特に説得力は感じませんでした。 また ソフトウェアトランザクショナルメモリ は、パフォーマンスの問題に悩まされています。 しかし、もしハードウェア・トランザクション・メモリが一般的になったら、私はとても楽しみです。 結局のところ、これはまだ研究であり、あと10年ぐらいはプロダクションコードには使えないでしょう。

8.2節では、いくつかの並列ツリー実装の性能を比較しています。 その結果を要約する。 50ページ、53ページ、54ページに非常に有益なグラフがあるので、PDFをダウンロードする価値がある。

• スキップリストのロック はめちゃめちゃ速いです。 同時アクセス数が増えても 驚くほど高速になります。 これがスキップリストの特徴で、他のロックベースのデータ構造は、圧力がかかると壊れる傾向があります。
• ロックフリースキップリスト は、ロック付きスキップリストより一貫して高速ですが、かろうじてです。
• トランザクションスキップリスト は、ロック版と非ロック版に比べ、一貫して2-3倍遅くなります。
• ロック式赤黒い木 同時アクセスに耐えられない。 その性能は、新しい同時アクセスユーザが増えるたびに直線的に低下します。 2つの既知のロック機能付き赤黒木の実装のうち、1つは基本的に木のリバランス中にグローバルロックがかかります。 もうひとつは、複雑なロックエスカレーションを使用しますが、グローバルロックの実装を大きく上回ることはありません。
• ロックフリーの赤黒い木 は存在しない（もはや真実ではない、Updateを参照）。
• トランザクション赤黒い木 は、トランザクションのスキップリストと同等である。 これはとても驚きで、とても期待できることでした。 トランザクション・メモリは、書くのがずっと簡単であれば、より遅くなります。 非同期バージョンで素早く検索と置換を行うのと同じくらい簡単なこともある。

更新情報

ロックフリーの木に関する論文はこちらです。 CASを用いたロックフリーの赤黒い木 .

深く調べたわけではありませんが、表面上はしっかりしているように思います。