最近、スキップ リストと呼ばれるデータ構造に出会いました。二分探索木と非常によく似た動作をしているようです。
二分探索木に対してスキップ リストを使用する必要があるのはなぜでしょうか。
72954 次
7 に答える
282
スキップ リストは、同時アクセス/変更により適しています。Herb Sutter は、並行環境におけるデータ構造に関する記事を書きました。より詳細な情報があります。
二分探索木の最も頻繁に使用される実装は、赤黒木です。ツリーが変更されると、再調整が必要になることがよくあります。リバランス操作はツリーの大部分に影響を与える可能性があり、多くのツリー ノードでミューテックス ロックが必要になります。スキップ リストへのノードの挿入は、はるかにローカライズされており、影響を受けるノードに直接リンクされているノードのみをロックする必要があります。
Jon Harrops のコメントからの更新
Fraser と Harris の最新論文Concurrent Programming without locksを読みました。ロックフリーのデータ構造に興味があるなら、本当に良いことです。この論文は、トランザクショナル メモリと、マルチワード比較およびスワップ MCAS の理論的な操作に焦点を当てています。これらは、まだハードウェアでサポートされていないため、ソフトウェアでシミュレートされます。彼らが MCAS をソフトウェアで構築できたことに、私はかなり感銘を受けました。
ガベージ コレクタが必要なため、トランザクショナル メモリは特に魅力的ではありませんでした。また、ソフトウェア トランザクショナル メモリは、パフォーマンスの問題に悩まされています。しかし、ハードウェアのトランザクショナル メモリが一般的になれば、私は非常に興奮します。最終的にはまだ研究段階であり、あと 10 年ほどは製品コードには使用されません。
セクション 8.2 では、いくつかの並行ツリー実装のパフォーマンスを比較しています。彼らの調査結果を要約します。50、53、および 54 ページに非常に有益なグラフがいくつかあるので、pdf をダウンロードする価値があります。
- スキップ リストのロックは非常に高速です。同時アクセス数に応じて非常にうまくスケーリングします。これがスキップ リストを特別なものにしている理由です。他のロック ベースのデータ構造は、プレッシャーの下で鳴き声を上げる傾向があります。
- ロックフリー スキップ リストは、ロック スキップ リストより一貫して高速ですが、わずかです。
- トランザクション スキップ リストは、ロックおよび非ロック バージョンより一貫して 2 ～ 3 倍遅くなります。
- 赤黒の木をロックすると、同時アクセスで鳴きます。それらのパフォーマンスは、新しい同時ユーザーごとに直線的に低下します。既知の 2 つのロッキング赤黒ツリーの実装のうち、1 つには基本的にツリーの再調整中にグローバル ロックが適用されます。もう 1 つは凝った (そして複雑な) ロックのエスカレーションを使用しますが、それでもグローバル ロック バージョンよりも大幅に優れているわけではありません。
- ロックフリーの赤黒木は存在しません (もはや真実ではありません。更新を参照してください)。
- トランザクションの赤黒ツリーは、トランザクションのスキップ リストに匹敵します。それは非常に驚くべきことであり、非常に有望でした。トランザクション メモリ。書き込みははるかに簡単ですが、速度は遅くなります。非並行バージョンでは、クイック検索と置換と同じくらい簡単です。
更新
ここにロックフリーツリーに関する論文があります: Lock-Free Red-Black Trees Using CAS。
深くは調べていませんが、表面的にはしっかりしているように見えます。
于 2008-11-03T23:03:41.803 に答える
93
まず、ランダム化されたデータ構造と、最悪のケースを保証するデータ構造を公平に比較することはできません。
スキップ リストは、Dean と Jones の「Exploring the Duality Between Skip Lists and Binary Search Trees」で詳しく説明されているように、ランダムにバランスのとれた二分探索木 (RBST) と同等です。
逆に、最悪の場合のパフォーマンスを保証する決定論的なスキップ リストを使用することもできます。マンロー等。
上記の一部の主張とは対照的に、並列プログラミングでうまく機能する二分探索木 (BST) を実装できます。同時実行性に重点を置いた BST の潜在的な問題は、赤黒 (RB) ツリーから得られるように、バランスに関して同じ保証を簡単に得られないことです。(しかし、「標準」、つまりランダム化されたスキップ リストでも、これらの保証は得られません。常にバランスを維持することと、適切な (そしてプログラムしやすい) 同時アクセスとの間にはトレードオフがあるため、通常は緩和されたRB ツリーが使用されます。良好な並行性が必要な場合。緩和は、すぐにツリーのバランスを取り直さないことにあります。少し古い (1998 年) 調査については、Hanke の「The Performance of Concurrent Red-Black Tree Algorithms」[ps.gz]を参照してください。
これらの最近の改善点の 1 つは、いわゆるクロマティック ツリーです(基本的に、黒が 1 で赤がゼロになるような重みがありますが、その間の値も許可されます)。そして、クロマティック ツリーはスキップ リストに対してどのように機能しますか? ブラウンらが何を見てみましょう。「ノンブロッキング ツリーの一般的なテクニック」 (2014) は次のように述べています。
128 スレッドの場合、私たちのアルゴリズムは Java のノンブロッキング スキップリストよりも 13% から 156% 優れています。Bronson らのロックベースの AVL ツリーです。63% から 224% 増加し、ソフトウェア トランザクショナル メモリ (STM) を使用する RBT は 13 倍から 134 倍増加します。
追加する編集: Fraser and Harris (2007) でベンチマークされたPughのロックベースのスキップ リストは、独自のロックフリー バージョンに近づいているとしてベンチマークされました (ここのトップの回答で十分に主張されているポイント)。また、良好な同時操作のために微調整されています。Pugh の"Concurrent Maintenance of Skip Lists"ですが、かなり穏やかな方法です。それにもかかわらず、2009年の新しい論文「A Simple Optimistic skip-list Algorithm」Herlihy et al. は、並列スキップ リストの (Pugh のものよりも) 単純であると思われるロックベースの実装を提案していますが、Pugh は十分に説得力のある正当性の証明を提供していないと批判しました。この（おそらくあまりにも衒学的な）不安を脇に置いて、Herlihy et al。スキップリストのより単純なロックベースの実装は、JDKのロックフリー実装と同様に実際にはスケーリングに失敗することを示していますが、競合が多い場合（50％の挿入、50％の削除、および0％の検索）のみです... which Fraserハリスはまったくテストしませんでした。Fraser と Harris は、ルックアップ 75%、挿入 12.5%、削除 12.5% のみをテストしました (スキップ リストで 500K 要素まで)。Herlihyらのより単純な実装。テストした競合が少ない場合 (ルックアップ 70%、挿入 20%、削除 10%) の場合、JDK のロックフリー ソリューションに近づきます。スキップ リストを十分に大きくして、つまり 200K から 2M 要素にすると、このシナリオのロックフリー ソリューションを実際に打ち負かし、ロックでの競合の可能性が無視できるようになりました。もしHerlihyらが Pugh の証明に関する問題を解決し、彼の実装もテストしましたが、残念ながらそれは行われませんでした。
EDIT2: すべてのベンチマークの (2015 年に公開された) マザーロードを見つけました: Gramoli の「More Than You Wanted to Know about Synchronization. Syncrobench、Measuring the Impact of the Synchronization on Concurrent Algorithms」 : これは、この質問に関連する抜粋された画像です。
「Algo.4」は、上記の Brown らの前身 (古い、2011 年版) です。(2014年版がどれだけ良いか悪いかはわかりません)。「Algo.26」は前述の Herlihy のものです。ご覧のとおり、更新時に破棄され、元の論文の Sun CPU よりも、ここで使用されている Intel CPU の方がはるかに悪いです。「Algo.28」は、JDK の ConcurrentSkipListMap です。他の CAS ベースのスキップ リストの実装と比較して、期待どおりには機能しません。競合が激しい場合の勝者は、Crain らによって記述されたロックベースのアルゴリズム (!!) である「Algo.2」です。「競合しやすいバイナリ検索ツリー」および「Algo.30」では、「マルチコアの対数データ構造」からの「ローテーション スキップリスト」です。". Gramoli は、これら 3 つの勝者アルゴリズム論文すべての共著者であることに注意してください。「Algo.27」は Fraser のスキップ リストの C++ 実装です。
Gramoli の結論は、同様のスキップ リストを台無しにするよりも、CAS ベースの同時実行ツリーの実装を台無しにする方がはるかに簡単だということです。そして、数字に基づいて、反対するのは難しい. この事実に対する彼の説明は次のとおりです。
ロックフリーのツリーを設計する難しさは、複数の参照をアトミックに変更する難しさに起因します。スキップ リストは、サクセサ ポインタを介して相互にリンクされたタワーで構成され、各ノードはそのすぐ下のノードを指します。各ノードにはサクセサ タワーとその下にサクセサがあるため、ツリーに似ていると見なされることがよくありますが、主な違いは、下向きポインタは一般に不変であるため、ノードのアトミックな変更を簡素化することです。この違いが、[上の図] に見られるように、激しい競合下でスキップ リストがツリーよりも優れている理由と考えられます。
Brown らの最近の研究では、この困難を克服することが重要な関心事でした。 彼らは、 (マシンレベルの) CAS を使用して実装された、LLX/SCX と呼ばれるマルチレコード LL/SC 複合「プリミティブ」の構築に関する別の (2013) 論文「ノンブロッキング データ構造の実用的なプリミティブ」を持っています。ブラウン等。この LLX/SCX ビルディング ブロックを 2014 年 (2011 年ではなく) の同時ツリー実装で使用しました。
ここで、 「ホット スポットなし」/コンテンション フレンドリー (CF) スキップ リストの基本的な考え方を要約することも、おそらく価値があると思います。. これは、緩和された RB ツリー (および同様の同時実行性を備えたデータ構造) からの重要なアイデアを追加します。タワーは、挿入後すぐに構築されるのではなく、競合が少なくなるまで遅延されます。逆に、高い塔を削除すると、多くの競合が発生する可能性があります。これは、Pugh の 1990 年のコンカレント スキップ リスト ペーパーまでさかのぼって観察されました。そのため、Pugh は削除時にポインタの反転を導入しました (スキップ リストに関するウィキペディアのページでは、残念ながら今日まで言及されていません)。CF スキップ リストは、これをさらに一歩進めて、高い塔の上層階の削除を遅らせます。CF スキップ リストでの両方の種類の遅延操作は、(CAS ベースの) 別のガベージ コレクターのようなスレッドによって実行されます。
Syncrobench コード (テスト済みのすべてのアルゴリズムを含む) は、https ://github.com/gramoli/synchrobench で入手できます。最新のブラウンら。実装 (上記には含まれていません) は、http: //www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java で入手できます。32 以上のコアのマシンを利用できる人はいますか? J/K 私のポイントは、これらを自分で実行できるということです。
于 2015-02-02T02:59:01.947 に答える
13
また、与えられた答えに加えて（バランスの取れたツリーに匹敵するパフォーマンスと組み合わされた実装の容易さ）。スキップリストには実装内にリンクリストが効果的に含まれているため、順序どおりのトラバーサル（順方向および逆方向）の実装ははるかに簡単であることがわかりました。
于 2008-11-02T06:32:23.800 に答える
12
実際に、私のプロジェクトでの B ツリーのパフォーマンスは、スキップ リストよりも優れていることがわかりました。スキップ リストの方が理解しやすいように見えますが、B ツリーの実装はそれほど難しくありません。
私が知っている 1 つの利点は、何人かの賢明な人々が、アトミック操作のみを使用するロックフリーの同時スキップ リストを実装する方法を考え出したことです。たとえば、Java 6 には ConcurrentSkipListMap クラスが含まれており、気が向いたらソース コードを読むことができます。
しかし、並列 B ツリー バリアントを記述することもそれほど難しくありません。他の誰かがそれを行っているのを見たことがあります。ツリーを下っていくときに「万が一に備えて」先制的にノードを分割およびマージすれば、その必要はありません。デッドロックを心配し、一度にツリーの 2 つのレベルでロックを保持するだけで済みます。同期のオーバーヘッドは少し高くなりますが、B ツリーの方がおそらく高速です。
于 2008-11-16T06:45:31.783 に答える
8
あなたが引用したウィキペディアの記事から：
すべてのノードに昇順でアクセスすることを強制する Θ(n) 操作 (リスト全体の出力など) は、最適な方法でスキップ リストのレベル構造の舞台裏で非ランダム化を実行する機会を提供します。スキップ リストを O(log n) 検索時間にします。[...] [そのような] Θ(n) 操作を最近実行していないスキップ リストは、より伝統的なバランスの取れたツリー データ構造と同じ絶対的な最悪の場合のパフォーマンス保証を提供しません。 (非常に低い確率ではありますが) スキップ リストを作成するために使用されるコイントスによって、バランスの取れていない構造が生成される可能性があります。
編集: これはトレードオフです: スキップ リストは、バランスの取れていないツリーに退化するリスクがあるため、使用するメモリが少なくなります。
于 2008-11-02T04:47:37.460 に答える
-1
スキップ リストには、ロック ストリッピングの利点があります。ただし、実行時間は、新しいノードのレベルがどのように決定されるかによって異なります。通常、これは Random() を使用して行われます。56000 語の辞書では、スキップ リストはスプレイ ツリーよりも時間がかかり、ツリーはハッシュ テーブルよりも時間がかかりました。最初の 2 つは、ハッシュ テーブルの実行時間と一致しませんでした。また、ハッシュテーブルの配列も同時にロック解除できます。
参照の局所性が必要な場合は、スキップ リストや同様の順序付きリストが使用されます。例: アプリケーションで日付の前後のフライトを検索する。
インメモリ二分探索スプレイ ツリーは優れており、より頻繁に使用されます。
于 2012-04-05T20:45:49.217 に答える