C++における並列処理に関する質問です。

Question

現在赤黒木の改良を考えているのですが、赤黒木におけるノードの挿入操作は、ノードが多くなるとリバランスに非常に時間がかかります。

そこで、プログラム内で挿入操作が必要となった時に、挿入操作を行うスレッド(もしくはプロセス)を新規で作成し、挿入に関してはそのスレッド、その他は元のスレッドが実行というように並列で行いたいのですが、どのようにスレッドを作れば良いか分からない為、教えてください。

挿入における排他制御(フラグ管理)などのアルゴリズムの部分は勉強したので、スレッドの作成方法が知りたいです。また、再帰を頻繁に行うプログラムなので、スレッド作成数の上限も設定したいです。

参考にしている論文
http://uc.alerta.cl/xmlui/bitstream/handle/123456789/1413/586394.pdf?sequence=1

なお、開発環境はVisual C++ 2012で、OpenMPも使用できます。ただオブジェクト指向に慣れていないため、ほとんどC言語で書いています。

以下に、簡単なソース、及び図を載せますので、お手数をおかけしますがアドバイスをいただけないでしょうか？

(簡単なソース)
main(){
x = f1();
}
int f1(){
if() y = f1(); //再帰を頻繁に行います
if() insert(); //挿入はスレッドを新規に作成し、元のスレッドと並列で実行(複数の挿入スレッドが同時に存在しうる)
return y;
}

p.s.
同じ内容の質問をyahoo知恵袋でも出しているのですが、回答してくれた方への質問に答えたりが出来ない為、こちらに転載させていただきました。

また、CreateThread()で実現できそうというアドバイスも頂けたのですが、もう少し具体的な実装方法が調べても分からなかったので、その点に関してのアドバイスでも十分ですので、よろしくお願い致します。

fresh_homepie · Accepted Answer

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 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のような方式を取りたいところなんですが…。注意２）標準ライブラリ使用に必要なヘッダファイルは省略してます。とかとか適当にincludeしてください。注意３）同時に動くスレッド数を制限するにはさらに工夫が必要です。自分でスレッドプールを作ったり、追加待ちのノードを保持するキューを作ったりする必要があるかも。注意４）C++はJavaと違ってGC（ガベージコレクション）という便利機能はないので、削除などして使わなくなったNodeやTreeのオブジェクトを適切に破棄してやる必要があります。Nodeはnewで生成していると思うので、確実にdeleteが実行されるように。（スマートポインタ管理でもいいがここに書けるだけの余裕がない…）注意５）作業スレッドが挿入作業を行ってる途中でメインのスレッドで大元のTreeが破棄されるのはまずいです（Treeの破棄時には保持するすべてのNodeを破棄しているはずなので）。破棄する時点でまだ挿入作業中なら、挿入作業完了まで待つように実装する必要があります。

LongSecret · Answer

私自身の現在直面しているプログラムの方が白熱してきたので、しばらく回答できないかもしれませんので、ちょいと報告をしておきます。

100万要素の、自作多段ハッシュへの挿入・削除を試みてみたところ、なんと単独での自作赤黒木の、さらに2倍ほど速かったです。
（よく見たらこれ自体に赤黒木が内包されてました。一番上を赤黒木にしておいて、そのノードの要素が配列を含んでて、さらにもう一段階その配列の要素として配列の出現可能性があり、それぞれ配列サイズは４・４）

※なぜ『赤黒木一本』に疑問を抱くかと言うと、私自身既に実装しているので、ものすごいバグフィックスなどが面倒だった割には意外に単純な方法に実測上勝てなくてガックシ…となったという黒い実績があるからです。
（正直なところは、ただでさえ赤黒木は複雑なコードが必要な上に、そのうえデフォでマルチスレッドを絡めるというのは、もう一回１から作れと言われたらゾッとします。それでもし大して速くならなかったらもう…）

この多段ハッシュはキーとなる数値を割って、その剰余を配列のインデックスと見立てて即時アクセス…を多段に行っていく、というもので、単純にそれぞれの段の配列要素を多くすればそれだけアクセス回数が少なくて済みます。(赤黒木同様、ポインタをたぐる時はキャッシュの恩恵をあまりよく受けられない可能性が高いため、その回数は少ないに越したことはありません。)

しかも、配列サイズを２のN乗にしといてメタプログラミングとかしとけば、インデックスの算出法はビット演算に置き換えられる可能性があり、非常に高速になる可能性があります。

実装の仕方は相当色々ありそうですが、この方法では赤黒木を一番上に持ってきてるものの、配列４の２乗があるため、赤黒木の要素数自体はぐっと少なくて済みます。

こういう感じで、なんでもいいんで『赤黒木の要素数を減らす方向』に検討してみる方が、少ない労力での速度・メモリ面両方のパフォーマンスの向上可能性が高い、かもしれません。

（他には…この論文のアイデアはB木とかにも使えるかな？）

なお、仮にVC++だとCreateThreadよりかは_beginthreadexとかの方がお勧めです。

クリティカルセクションは、オブジェクトごとに持つなら別途フラグはいらずそれ単体でOKのはずです。

では、ご健闘をお祈りします。

LongSecret · Answer

う～ん、ちょっと整理させてください。
確かに、考えてみると少なくとも問答無用で上からロックを掛けていけば子ノード以下を縮小版赤黒木ととらえることで、フラクタル的に可能になる気がします。

ただ、この論文では「問答無用で上からたぐった分だけロック」しなくても「操作中は目的のノードおよびリバランスに必要な周辺のノードだけロックすればいい」と言う事を示唆している、という意味でしょうか？
（ノードが挿入されるのは「つねに末端」であるため、もしかしたら出来るのか…?という気もしなくもないですが、今ちょっと他の事に頭を使わないといけないので頭が回り切りません（笑））

もし後者であれば、たしかにやる価値はあるかもしれませんが

前者の場合は考え物です。ロックする以上は解除しないといけませんからね。
さらに、ロックしてその最中に入れ替えを行うって事は参照の時もその影響を受けざるをえないはずです。

なので、探索・参照はむしろ遅くなるはずです。

いずれにしても実際の現場でやりたい事次第ではありますが…

といいますのも、JavaはC++と比べ元々メモリ使用量が多い傾向がありますが、C++はかつかつに削ることも可能です。

仮に目的とするデータを「そのままキーとして使える」という都合のいい状況で、かつ32bit環境として、さらにその「データ」が32bit以下として計算してみますと、ノード1つあたり

leftポインタ、rightポインタ、クリティカルセクション、赤黒フラグ(しかもこれをポインタのビットに埋め込むとして)、さらに実データ

で、さらにがんばって親へのポインタをなくしても、クリティカルセクションが24バイトのアラインメント4だとして

全体のアラインメントも考慮して、おそらく最小で1ノードあたり36バイトもの消費となります。

これは、仮に100万要素だと30MBを超えます。（しかも、メモリ的に実データ以外が８割以上を占める）

これだけのサイズだと、キャッシュミスの恐れが多くなってしまって、参照はおろか挿入すら逆に遅くなってしまう可能性も否定できません。（というよりも、それは相対的な話で、ネイティブC++はちゃんと組めば元々がとても速い）

実験コードを見つけたので試してみると、そんなにハイスペックじゃないPCでの実験でしたし、私の自作コードでは並列化などはしていませんが

それでもデフォルトアロケータで100万要素の追加に、順番にやってって0.5秒程度、ランダムにシャッフルしといて挿入してっても2秒かかるかどうか程度で出来ています。

C++で、赤黒木じゃなくちゃいけなくて、しかも要素数めちゃめちゃ多くて、しかもそれほど速度を求めないといけないってなかなかないと思うのですが

…本当にそこまで速度を求めなければいけない状況なのでしょうか？（素朴な疑問）

LongSecret · Answer

補足です。

『あくまで、挿入・削除などの木構造の変更が出来るのは1スレッドからのみで、木構造の変更中の要素への参照だけだったらいくつでも別スレッドから出来る…』

ということであれば可能だと思いますし、現在時間がないので精読は出来ませんが、リンク先の内容は実際にはそう言う事ではないか、という憶測をしています。

単にそう言うことであれば納得です。回転しても、黒高さが一時的に崩れてても探索アルゴリズム自体は同様にできますからね。

LongSecret · Answer

こんにちは。
４か月ほど前に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の使ってあった個所から類推して、それを覆す内容が書いてあったようには思えませんでした。読み足りないだけかもしれませんけど）

具体的にはどういう風にどこで使って何を短縮してるのかなぁ…それによります。

そこんとこざっくりで良いので簡易的に解説していただくこと出来ますかね？（あるいはどの辺読めば分かりやすいだろう…という情報でも）
それで判断できるかもしれません。

wormhole · Answer

＞提示していただいたサイトを閲覧したのですが、再帰的な利用という点でも可能なのでしょうか。

参考になりそうなサイトを書いただけですので、そこに書かれている事が再帰的利用が可能かどうかはご自分で調べてください(あなたの代わりにそこまで調べてあげる気はありません)。
見た限りでは、そのまま参考にすると再帰で問題ありそうなのは排他制御に関する事でスレッド関連については大丈夫だと思いますが。

ulisrt · Answer

たぶん，おかしなアルゴリズムではないのでしょう．査読付きのプロシーディングに同じタイトル・著者・概要で掲載されているようですから．発表は去年のようですね．

掲載されているJavaコードを見る限り，本当にロックしか用いていませんね（私が読み落としていなければ）．ならミューテックスかバイナリセマフォ，またはWindowsのクリティカルセクションを使えば実現できるでしょう．

具体的には掲載コードに synchronized (n) { ... } があったなら，オブジェクト n と一緒に同期プリミティブを作っておき，"{"でクリティカルセクションに入り（つなりnをロックし），"..."部分の処理が終わったら"}"でクリティカルセクションを出る（nのロックを外す）ようにJavaからC++へ翻訳すればよいでしょう．もちろんマルチスレッドで．

それとこの場合，並列(parallel)より並行(concurrent)と訳した方が良いかと．

noname#171461 · Answer

同期方法はセマフォア、ミューテックス、イベントフラグなどを既にお調べなのであれば、あとはスレッド作成が出来るかどうかと言う部分でしょうか。CreateThreadでスレッドは簡単に作成できますし、MSDNやVC++のサンプルソースにいろいろとサンプルコードがあるかと思います。スレッドで一番難しいのは同期方法に慣れることと、デバッグの方法を習得することです。同期の考え方が理解できれば予測計算的な捨てスレッドなども動作させて最終的には処理時間の短縮が出来る上級設計も出来るようになります。スレッド数の上限については昔調べたことがありますが、プロセス空間内での管理可能なスレッド管理テーブル的なが制約になると想像しましたが結局わからず仕舞いでした。32ビットOSで試した際には数百個は問題なく作成できましたが、多すぎると何らかのリソースが足りなくなるようでうまく動作しませんでした。私の場合は画像のサムネイルをスレッドで生成するのに主に使用するケースが多かったです。現在のMSDNにはスレッド上限数の情報があるかもしれませんので私に代わってお調べください。また同時生成するプロセス数やスレッド数は、搭載メモリー量やHDD/SSD容量などによって最適な同時生成数が代わりますので、ある程度動作可能なプログラムが出来た時点で実測して実験を繰り返すしかないです。

wormhole · Answer

私はCでpthread使ったことしかないのでVisual C++での場合はよくわかりませんが、
http://www.atmarkit.co.jp/fdotnet/bookpreview/bunpouvcpp_1302/bunpouvcpp_1302_01.html

あたりが参考になりませんか？

wormhole · Answer

リバランスも含めノードの挿入や削除処理がそれ専用のスレッドで処理中に検索できる方法考えてありますか？検索中にツリーの構造が変化してたら困りませんか？

C++における並列処理に関する質問です。

Yahoo知恵袋はやり取りが難しいとのことなのでこちらへ…。

私自身の現在直面しているプログラムの方が白熱してきたので、しばらく回答できないかもしれませんので、ちょいと報告をしておきます。

う～ん、ちょっと整理させてください。

補足です。

この回答への補足

こんにちは。

この回答への補足

＞提示していただいたサイトを閲覧したのですが、再帰的な利用という点でも可能なのでしょうか。

たぶん，おかしなアルゴリズムではないのでしょう．査読付きのプロシーディングに同じタイトル・著者・概要で掲載されているようですから．発表は去年のようですね．

この回答への補足

同期方法はセマフォア、ミューテックス、イベントフラグなどを既にお調べなのであれば、あとはスレッド作成が出来るかどうかと言う部分でしょうか。

この回答への補足

私はCでpthread使ったことしかないのでVisual C++での場合はよくわかりませんが、

この回答への補足

リバランスも含めノードの挿入や削除処理がそれ専用のスレッドで処理中に検索できる方法考えてありますか？検索中にツリーの構造が変化して

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング