- ベストアンサー
C++における赤黒木の並列挿入操作について
- C++における赤黒木のノードの挿入操作にはリバランスに時間がかかる課題がある。
- 挿入操作を並列化するために、スレッドを新規作成して並列で挿入を実行したい。
- スレッドの作成方法や挿入操作の排他制御について具体的なアドバイスを求めている。
- みんなの回答 （11）
- 専門家の回答
質問者が選んだベストアンサー
Yahoo知恵袋はやり取りが難しいとのことなのでこちらへ…。 論文に書かれているJavaのコードを見ると、ノード毎に個別にロックをかける必要があるのですね。 WindowsではWindows APIのMutexやCritical Sectionを使用するのが一般的ですが、VC++2012であれば新しいC++標準（C++11）のスレッド関連ライブラリを使えるので（記憶では確か使えたはず…私の手持ちがVS2010なので試せないですが）、それでも良いと思います。Windows APIに依存させないことにより、後でWindows以外の環境（Linuxとか）でも動かすことができます。それより古いコンパイラでも動かすならBoostライブラリを導入するという手もありますが。 ノードを定義するクラスまたは構造体のメンバとして、ノードの排他アクセスに使用する std::mutex または std::recursive_mutex を含めておきます。（recursiveな方が必要かどうかは論文をちゃんと見てないので分からないですが…Javaのsynchronizedはrecursiveなはずなのでそっちを使っておけば問題ないかしら） struct Node { ...(中略：他に必要なメンバを書く)... std::recursive_mutex mutex; // ノードアクセス用のミューテックス }; そして、Javaのコード上で synchronized (node) { ... (処理コード) ... } と書かれている（ノードに対して排他制御されている）部分をC++では { std::lock_guard<std::recursive_mutex> lock(node->mutex); ... (処理コード) ... } と書きます（ここでは変数nodeはNodeオブジェクトへのポインタと仮定）。上記のように書くと、変数「lock」のコンストラクタ実行時にノードをロックし、デストラクタ実行時に（最後の「}」の位置で）ロック解除されるようになります。 新しいスレッドの作成には std::thread クラスを使います。 // 引数なしのinsert()関数を新しいスレッドで実行 std::thread t(insert); t.detach(); detach() メンバ関数は、「呼び出し側はもう新しいスレッドには関知しないのであとは勝手に動いててね」というものです。本当ならちゃんとスレッドの実行を管理するべきですが、簡単化のためここではこう書いてます。 また、insert関数に引数がある場合は以下のように。 std::thread t(insert, 引数1, 引数2); 注意１）ノード毎にstd::recursive_mutexを持つ実装なので、消費メモリが少なくとも ノード数×sizeof(std::recursive_mutex) の分だけ増加します。本当ならJavaのsynchronizedやC#のlockのような方式を取りたいところなんですが…。 注意２）標準ライブラリ使用に必要なヘッダファイルは省略してます。<mutex>とか<thread>とか適当にincludeしてください。 注意３）同時に動くスレッド数を制限するにはさらに工夫が必要です。自分でスレッドプールを作ったり、追加待ちのノードを保持するキューを作ったりする必要があるかも。 注意４）C++はJavaと違ってGC（ガベージコレクション）という便利機能はないので、削除などして使わなくなったNodeやTreeのオブジェクトを適切に破棄してやる必要があります。Nodeはnewで生成していると思うので、確実にdeleteが実行されるように。（スマートポインタ管理でもいいがここに書けるだけの余裕がない…） 注意５）作業スレッドが挿入作業を行ってる途中でメインのスレッドで大元のTreeが破棄されるのはまずいです（Treeの破棄時には保持するすべてのNodeを破棄しているはずなので）。破棄する時点でまだ挿入作業中なら、挿入作業完了まで待つように実装する必要があります。
その他の回答 (10)
- LongSecret
- ベストアンサー率68% (22/32)
私自身の現在直面しているプログラムの方が白熱してきたので、しばらく回答できないかもしれませんので、ちょいと報告をしておきます。 100万要素の、自作多段ハッシュへの挿入・削除を試みてみたところ、なんと単独での自作赤黒木の、さらに2倍ほど速かったです。 （よく見たらこれ自体に赤黒木が内包されてました。一番上を赤黒木にしておいて、そのノードの要素が配列を含んでて、さらにもう一段階その配列の要素として配列の出現可能性があり、それぞれ配列サイズは４・４） ※なぜ『赤黒木一本』に疑問を抱くかと言うと、私自身既に実装しているので、ものすごいバグフィックスなどが面倒だった割には意外に単純な方法に実測上勝てなくてガックシ…となったという黒い実績があるからです。 （正直なところは、ただでさえ赤黒木は複雑なコードが必要な上に、そのうえデフォでマルチスレッドを絡めるというのは、もう一回１から作れと言われたらゾッとします。それでもし大して速くならなかったらもう…） この多段ハッシュはキーとなる数値を割って、その剰余を配列のインデックスと見立てて即時アクセス…を多段に行っていく、というもので、単純にそれぞれの段の配列要素を多くすればそれだけアクセス回数が少なくて済みます。(赤黒木同様、ポインタをたぐる時はキャッシュの恩恵をあまりよく受けられない可能性が高いため、その回数は少ないに越したことはありません。) しかも、配列サイズを２のN乗にしといてメタプログラミングとかしとけば、インデックスの算出法はビット演算に置き換えられる可能性があり、非常に高速になる可能性があります。 実装の仕方は相当色々ありそうですが、この方法では赤黒木を一番上に持ってきてるものの、配列４の２乗があるため、赤黒木の要素数自体はぐっと少なくて済みます。 こういう感じで、なんでもいいんで『赤黒木の要素数を減らす方向』に検討してみる方が、少ない労力での速度・メモリ面両方のパフォーマンスの向上可能性が高い、かもしれません。 （他には…この論文のアイデアはB木とかにも使えるかな？） なお、仮にVC++だとCreateThreadよりかは_beginthreadexとかの方がお勧めです。 クリティカルセクションは、オブジェクトごとに持つなら別途フラグはいらずそれ単体でOKのはずです。 では、ご健闘をお祈りします。
- LongSecret
- ベストアンサー率68% (22/32)
う～ん、ちょっと整理させてください。 確かに、考えてみると少なくとも問答無用で上からロックを掛けていけば子ノード以下を縮小版赤黒木ととらえることで、フラクタル的に可能になる気がします。 ただ、この論文では「問答無用で上からたぐった分だけロック」しなくても「操作中は目的のノードおよびリバランスに必要な周辺のノードだけロックすればいい」と言う事を示唆している、という意味でしょうか？ （ノードが挿入されるのは「つねに末端」であるため、もしかしたら出来るのか…?という気もしなくもないですが、今ちょっと他の事に頭を使わないといけないので頭が回り切りません（笑）） もし後者であれば、たしかにやる価値はあるかもしれませんが 前者の場合は考え物です。ロックする以上は解除しないといけませんからね。 さらに、ロックしてその最中に入れ替えを行うって事は参照の時もその影響を受けざるをえないはずです。 なので、探索・参照はむしろ遅くなるはずです。 いずれにしても実際の現場でやりたい事次第ではありますが… といいますのも、JavaはC++と比べ元々メモリ使用量が多い傾向がありますが、C++はかつかつに削ることも可能です。 仮に目的とするデータを「そのままキーとして使える」という都合のいい状況で、かつ32bit環境として、さらにその「データ」が32bit以下として計算してみますと、ノード1つあたり leftポインタ、rightポインタ、クリティカルセクション、赤黒フラグ(しかもこれをポインタのビットに埋め込むとして)、さらに実データ で、さらにがんばって親へのポインタをなくしても、クリティカルセクションが24バイトのアラインメント4だとして 全体のアラインメントも考慮して、おそらく最小で1ノードあたり36バイトもの消費となります。 これは、仮に100万要素だと30MBを超えます。（しかも、メモリ的に実データ以外が８割以上を占める） これだけのサイズだと、キャッシュミスの恐れが多くなってしまって、参照はおろか挿入すら逆に遅くなってしまう可能性も否定できません。（というよりも、それは相対的な話で、ネイティブC++はちゃんと組めば元々がとても速い） 実験コードを見つけたので試してみると、そんなにハイスペックじゃないPCでの実験でしたし、私の自作コードでは並列化などはしていませんが それでもデフォルトアロケータで100万要素の追加に、順番にやってって0.5秒程度、ランダムにシャッフルしといて挿入してっても2秒かかるかどうか程度で出来ています。 C++で、赤黒木じゃなくちゃいけなくて、しかも要素数めちゃめちゃ多くて、しかもそれほど速度を求めないといけないってなかなかないと思うのですが …本当にそこまで速度を求めなければいけない状況なのでしょうか？（素朴な疑問）
- LongSecret
- ベストアンサー率68% (22/32)
補足です。 『あくまで、挿入・削除などの木構造の変更が出来るのは1スレッドからのみで、木構造の変更中の要素への参照だけだったらいくつでも別スレッドから出来る…』 ということであれば可能だと思いますし、現在時間がないので精読は出来ませんが、リンク先の内容は実際にはそう言う事ではないか、という憶測をしています。 単にそう言うことであれば納得です。回転しても、黒高さが一時的に崩れてても探索アルゴリズム自体は同様にできますからね。
補足
論文の内容を上手く説明できるか怪しいですが、論文の要点は、 1. これはリラックスした赤黒木であり、アンバランスが存在するなら、スレッドによって所持されなければならない。 ※リラックス：木内で動作中のスレッドが存在する限りアンバランスは存在するが、木内で動作中のスレッドが1つも存在しないならばバランスが保証されるという意味 2. リバランス操作(回転や色変えなど)は複数のスレッドで、木内の様々な場所で同時に進行しているが、同一のノードを同時に扱うことは許さない(ロックで防ぐ) 3. リバランス操作は基本的にボトムアップで進行する為、木の上に行くほどスレッドの衝突が多くなりそう。 しかし2.により、１つのスレッドがリバランスを行うことでもう1つのスレッドはリバランスが不必要となり終了する為、木の上方におけるスレッドの数の増加は意識しなくて良い。 非常に大雑把ではありますが、このような内容でした。
- LongSecret
- ベストアンサー率68% (22/32)
こんにちは。 ４か月ほど前にC++でleft-leaning red-black 2 - 3 tree（左傾2-3赤黒木）を０から自作した者です。 STL同様templateで要素とアロケータを指定でき、関数の再帰呼び出しを自前のスタックとループに置き換えることで、STLより挿入・削除・探索が速く省メモリ…というのを実現してた記憶がありますが、それでもあんまり要素数増えてくると、結局自作多段ハッシュの方が理論的にも物理的にもさらにずっと探索が速かったりするので、そう言う場合はそっちを使っています。 （パフォーマンスに関しては正確な数値を覚えてないので、STLをとりあえずの指標として、そもそもが目的に対して影響があるほど遅いものなのかどうか試してみてください。） とりあえず ＞ノードの挿入操作は、ノードが多くなるとリバランスに非常に時間がかかります。 確かに時間は増えます。ただ 赤黒木はバランス悪くても最高の高さが最低の高さの2倍以下ほどなので 例えば要素数が相当多くて100万までいったとしても、2の20乗が100万超えるので、高さは最悪でも高々40以下くらい・・・のはずです。 でもって、細かい処理は煩雑だったので忘れましたが、末尾から順々に上にあがっていき、その場合最悪40回までの「回転・色付け替え」などの操作ですむ・・・だった気がします。 運が良ければ単に挿入するだけで済みます。 元々あんまり要素数多いなら、前述の通り他のタイプのコンテナでいくほうが良い可能性が高いため、実際上はそれほど問題となるとは思えません。 ロック法に関しては、VC++2012は私もまだ使えないので分かりませんが 結局「依存」と言う事に関して言えば、templateでロック法指定できるようにしとけばラップしたクラスを作ってどうとでも後で交換出来ますから、完全にC++11使える環境でなければ、あるいはあっても少なくともパフォーマンス的にはクリティカルセクションのラップで全然OKじゃね？ と思いますが（イメージとしては、必要な個所でtemplateで作っといてそれに対しEnterやLeave呼び出しで囲っといて…後はテンプレートパラメータに↓のようなクラスを指定） class MyThreadSection{ CRITICAL_SECTION cs; public: MyThreadSection(){ InitializeCriticalSection( &cs ); } ~MyThreadSection(){ DeleteCriticalSection( &cs ); } inline BOOL TryEnter(){ return TryEnterCriticalSection(&cs); } inline void Enter(){ EnterCriticalSection(&cs); } inline void Leave(){ LeaveCriticalSection(&cs); } }; ただ、その前に、どういう操作に対してロックが必要になるかの把握が重要です。 削除が不要といっても、挿入の時にも 「あるノード」の挿入によって、必要がある場合は「その親ノード」方向へ順番に回転操作や色の付け替えを行わないといけないはずなのですが、その操作自体は順番に行う必要がある・・・んじゃないんでしょうか？ （リンク先はざっとしか読んでないですが、synchronizedの使ってあった個所から類推して、それを覆す内容が書いてあったようには思えませんでした。読み足りないだけかもしれませんけど） 具体的にはどういう風にどこで使って何を短縮してるのかなぁ…それによります。 そこんとこざっくりで良いので簡易的に解説していただくこと出来ますかね？（あるいはどの辺読めば分かりやすいだろう…という情報でも） それで判断できるかもしれません。
補足
回答ありがとうございます。 上の補足に論文の要点を記載しました。 さらに補足しますと、ノードを挿入するごとに1つスレッドを作成し、そのノードを入れたことによってアンバランスを解消するまで親の方へとボトムアップでリバランスして行きます。 通常の赤黒木ですと、その1つのノードによるアンバランスが解消されるまで(最悪rootまで)リバランスし続け、その後にまたノードの追加及びリバランス、という流れで進みますが、 この赤黒木ですと、ノードを追加しリバランスしている間にまた別のノードの追加を行っていけるので、大幅な時間短縮の実行結果が実験より得られているそうです(The Performance of Concurrent Red-Black Tree Algorithmsの論文より)
- wormhole
- ベストアンサー率28% (1626/5665)
＞提示していただいたサイトを閲覧したのですが、再帰的な利用という点でも可能なのでしょうか。 参考になりそうなサイトを書いただけですので、そこに書かれている事が再帰的利用が可能かどうかはご自分で調べてください(あなたの代わりにそこまで調べてあげる気はありません)。 見た限りでは、そのまま参考にすると再帰で問題ありそうなのは排他制御に関する事でスレッド関連については大丈夫だと思いますが。
お礼
失礼致しました。 回答をいただけたことに感謝しています。もう少し自分で調べてみます。
たぶん，おかしなアルゴリズムではないのでしょう．査読付きのプロシーディングに同じタイトル・著者・概要で掲載されているようですから．発表は去年のようですね． 掲載されているJavaコードを見る限り，本当にロックしか用いていませんね（私が読み落としていなければ）．ならミューテックスかバイナリセマフォ，またはWindowsのクリティカルセクションを使えば実現できるでしょう． 具体的には掲載コードに synchronized (n) { ... } があったなら，オブジェクト n と一緒に同期プリミティブを作っておき，"{"でクリティカルセクションに入り（つなりnをロックし），"..."部分の処理が終わったら"}"でクリティカルセクションを出る（nのロックを外す）ようにJavaからC++へ翻訳すればよいでしょう．もちろんマルチスレッドで． それとこの場合，並列(parallel)より並行(concurrent)と訳した方が良いかと．
補足
論文まで見ていただいてどうもありがとうございます。 クリティカルセクションに関して少し調べてみたのですが、例えば「各ノードにロックされているかどうかのフラグを持たせて、それを変更する時はクリティカルセクション内で行う」ということでしょうか？ それともフラグを持たせる必要は無く、クリティカルセクションだけで管理できるということでしょうか？ そしてconcurrentですが、確かにこれだと擬似並列も含んでいいようなので並行でした。ご指摘ありがとうございます。
同期方法はセマフォア、ミューテックス、イベントフラグなどを既にお調べなのであれば、あとはスレッド作成が出来るかどうかと言う部分でしょうか。CreateThreadでスレッドは簡単に作成できますし、MSDNやVC++のサンプルソースにいろいろとサンプルコードがあるかと思います。スレッドで一番難しいのは同期方法に慣れることと、デバッグの方法を習得することです。同期の考え方が理解できれば予測計算的な捨てスレッドなども動作させて最終的には処理時間の短縮が出来る上級設計も出来るようになります。スレッド数の上限については昔調べたことがありますが、プロセス空間内での管理可能なスレッド管理テーブル的なが制約になると想像しましたが結局わからず仕舞いでした。32ビットOSで試した際には数百個は問題なく作成できましたが、多すぎると何らかのリソースが足りなくなるようでうまく動作しませんでした。私の場合は画像のサムネイルをスレッドで生成するのに主に使用するケースが多かったです。現在のMSDNにはスレッド上限数の情報があるかもしれませんので私に代わってお調べください。また同時生成するプロセス数やスレッド数は、搭載メモリー量やHDD/SSD容量などによって最適な同時生成数が代わりますので、ある程度動作可能なプログラムが出来た時点で実測して実験を繰り返すしかないです。
補足
回答どうもありがとうございます。 やはりCreateThread()で作成するのが良さそうですね。 同期方法に関しては、アルゴリズム内のロックによる排他制御で実現できると信じているのですが、デバッグと同様にひたすら試行錯誤して改善していきたいと考えています。 スレッド数の上限設定は難しそうですね。CreateThread時に総数を確認した上で実行、だとやはり怪しいですかね・・。 最適な生成数は色々と試してみます。
- wormhole
- ベストアンサー率28% (1626/5665)
私はCでpthread使ったことしかないのでVisual C++での場合はよくわかりませんが、 http://www.atmarkit.co.jp/fdotnet/bookpreview/bunpouvcpp_1302/bunpouvcpp_1302_01.html あたりが参考になりませんか？
補足
回答ありがとうございます。 提示していただいたサイトを閲覧したのですが、再帰的な利用という点でも可能なのでしょうか。 pthreadについては知らなかったので、調べてみます。
- wormhole
- ベストアンサー率28% (1626/5665)
リバランスも含めノードの挿入や削除処理がそれ専用のスレッドで処理中に検索できる方法考えてありますか？検索中にツリーの構造が変化してたら困りませんか？
補足
すいません、1つ言い忘れていましたが、私の利用目的では削除操作は行いません。 そして質問に対する返事ですが、concurrentなB木のアルゴリズムでの探索操作と似た探索方法を考えています。 確実に問題がないとは言い切れませんが、並行環境を実装できた後に改良していきたいと考えています。
- Tacosan
- ベストアンサー率23% (3656/15482)
複数ノードの挿入って, 並行してできるんだっけ? 逐次処理にしかならないんだったら, スレッドにしても何もうれしくないんじゃないかなぁ.
補足
添付のサイトは今年発表された並列処理の赤黒木アルゴリズムの論文でして、逐次処理でなくロックを用いることで並列処理可能なアルゴリズムになっています。
お礼
非常に丁寧なアドバイスを頂き本当にありがとうございます。 実際にソースの提示もしていただけて非常に分かりやすいです。使用したことのない関数がいくつかあったのできちんと調べ、こちらを参考に実装を進めて行きたいと思います。 そして、yahoo知恵袋だけでなくこちらでもアドバイス頂けたこと、非常に感謝しております。