fork/joinフレームワーク - ドグマを探しに

Doug Lea氏の論文が興味深い。

Javaに関するfork/joinの概念は、元々Lea(source)が自身の論文「Fork/Join Parallelism in Java」（Javaにおけるfork/joinの並列性）(source)の中で紹介したものである。Leaのutil.concurrent パッケージはJSR-166(source)の基礎であり、Java 5でリリースされたjava.util.concurrentライブラリであった。fork/joinは単に、このJSRの修正である。

JavaOne 2008 fork-join slide : 空色ブログ

fork-join の道具立て

未熟な実装では Thread を使用します
沢山の待機スレッドが発生してしまう事が問題です
Executor も相応しくありません
スレッドプールにスレッド数上限を設定するとスタベーションデッドロックが発生します - 標準のスレッドプールは互いに独立したタスクを実行する様に設計されています
標準のスレッドプールを細粒度のタスクに使用するとタスクキューや他のデータ構造で競合が発生してしまいます
より理想に近い実装は以下を考慮する必要があります
ワーカースレッドのコンテクストスイッチによるオーバーヘッド
ハードウェアスレッドと同じだけのスレッドを作成し、奇麗に負荷分散させます
データ構造で競合が発生しない
共有タスクキューを持ちません

ワークスティーリング

fork-join フレームワークはワークスティーリングを使って実装されています
予め決めた数のワーカースレッドを作成します
各ワーカースレッドは固有の両端キュー(deque) をワークキューとして持ちます
deque は java.util.concurrent パッケージの deque ではなく、特別に最適化した物を使用しています
fork 時にワーカーは新しいタスクを自分の両端キューの先頭に入れます
タスクが終了したら自分の両端キューの先頭からタスクを取り出し、それを実行します
他のタスクの終了を待ってスリープする事はありません
ワークキューが空になったら、他のワーカーをランダムに選択し、そのワーカーのワークキューの末尾からタスクを横取り（スティール）します

ワークスティーリング（続き）

ワークスティーリングは効率的です - タスク管理のオーバーヘッドは殆ど発生しません
共有ワークキューを使うのに比べてスレッド間の競合は減少します
ワークキューの先頭では競合は全く発生しません
キューを所有しているスレッドだけが先頭にアクセスします
キューの先頭へのアクセスと末尾へのアクセスは競合しません
最適なキューのアルゴリズムが使用されています
キューの末尾では殆ど競合は発生しません
スティーリングが発生するのは稀で、スティーリングが衝突する事は更に希有です
スティーリングは殆ど発生しない
ワーカーがキューに入れたり取り出したりする場合は LIFO でアクセスします
キューに入れるデータのサイズは問題が分割されていればいるほど小さくなります
スレッドが他のワーカーのキューからスティールする時は複数のタスクをまとめて取ってきます
しばらくの間は他のスレッドからスティールする必要はありません

ワークスティーリング（続き）

pool.invoke() が呼ばれると、タスクはランダムに選ばれたワーカーのワークキューに入れられます
受け取ったワーカーがタスクを実行します
通常は受け取ったタスクを 2 つのサブタスクに分割し、自分のワークキューに入れます - これは時間は掛かりません
分割したサブタスクの片方を実行開始します
他のワーカーが最初のワーカーのもう片方のサブタスクをスティールします
fork が終了すると、タスクは各ワーカーのワークキューに行き渡った状態になります
この状態になるとワーカーはタスクの中身の逐次処理を開始します
タスクが均等に分配されてなかった場合は、スティールする事で適正化されます
結果: 十分な負荷分散
誰かが専任でスレッド間を調整する必要はありません
スケジューリングのオーバヘッドはわずかです
同期処理に掛かるコストも最小限です
同期の際に競合が発生する事は殆どありません