javaフォーク/スタック使用についての明確化

Question

Java 7で導入されたFork/Joinフレームワークの実装について読みましたが、私は魔法の仕組みを理解していることを確認したかったのです。

私が理解しているように、スレッドがフォークすると、そのキューにサブタスクが作成されます（他のスレッドが盗むこともあれば盗むこともありません）。スレッドが「結合」しようとすると、実際にそのキューに既存のタスクがあるかどうかがチェックされ、再帰的に実行されます。つまり、「結合」操作の場合、スレッドコールスタックに2つのフレームが追加されます新しい取られたタスク呼び出しのために）。

私はJVMがテールコールの最適化をサポートしていないことを知っています（このような状況ではjoinメソッドスタックフレームを削除することができます）。フォークを多数使用して複雑な操作を実行しているときに、 StackOverflowError。

私はそうですか、それともそれを防ぐためのクールな方法を見つけましたか？ （簡略化のため） セイ我々は唯一forkjoinプール内の1つのスレッドを持っている：

EDITここ

は質問を明確にするのに役立つシナリオです。 ある時点で、スレッドは分岐してからjoinを呼び出します。結合メソッド中に、スレッドはforkされたタスク（キュー内にある）を実行できることを検出して、次のタスクを呼び出します。このタスクは順番に分岐してjoinを呼び出します。つまり、joinメソッドを実行している間にスレッドは（以前と同じように）キュー内のforkされたタスクを見つけ出し、呼び出します。その段階で を呼び出しスタックには、少なくとも2つのジョインと2つのタスクのフレームが含まれます。

フォーク結合フレームワークがプレーンな再帰に変換されているのが分かります。 Javaではテールコールの最適化がサポートされていないため、Javaのすべての再帰で十分な深さになるとStackOverflowErrorが発生する可能性があります。

私の質問は、フォーク/結合フレームワークの実装者は、この状況を防ぐためのクールな方法を見つけましたか？

Answer 1

残念ながら、スレッド再帰スタックに関しては何も起こっていません。あなたの最初のタスクが分岐し、合理的な解決ポイントがない場合は、StackOverflowErrorsを実行します。

JavaDocのチュートリアルで、各サブタスクを半分に分割する理由を理解できます。

Answer 2

一般に、スタックにプッシュされる新しいタスクはすべて、前のタスクのサイズの半分です。だから、仕事の量はスタックの大きさとともに指数関数的に増加します。小さなスタックでも、あなたはしばらくあなたを忙しく保つために十分な仕事以上に収まるようになるでしょう。

Answer 3

私は正しい方法であなたを理解してくれることを望みます。

実行するタスクを保持する内部キューがforkjoinpoolにあります。したがって、スタックオーバーフローは発生しませんが、高いメモリ使用率に備える必要があります。

ForkJoinWorkerThread.pushTaskは安全ではないオブジェクトを使用するため、タスクを格納するために配列が使用されることに注意してください。

EDIT： キューの先頭にあるときは、単にプッシュして実行するだけで、リターンが返されます。 （forkjointask.java:353）

依存関係がある場合、異なるアプローチが使用されます。この場合、コントロールはWorkerThreadに返され、WorkerThreadはチェーンを検出して実行します。 最初のワーカーは未処理のタスクをローカルキューでチェックし、そうでない場合は渡されたジョブを実行して結果を返します。それ以外の場合は次のケースに進みます。 これは何度か盗むのに役立っています。 何も役に立たなかった...最初のステップがMAX_HELPに等しい再試行は今やゼロです。制御はプールに渡され、いくつかのチェックが実行され、tryAwaitDoneが実行されます。 このメソッドでは、タスクの完了を待つためにwaitが呼び出されます。

これは、フォーク結合プールがいくつかの手順で終了し、待機する呼び出しを回避して速度と時間を最適化しようとしていることを意味します。しかし、それは待って終了することができます、これは非常に高価な同期プロセスを開始することを意味します。

したがって、無限深度の後続の結合はありませんが、できるだけ早くタスクを実行しようとする論理的な試みがあります。