Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

java Fork/Join clarification about stack usage

I read about the implementation of the Fork/Join framework that was introduced in Java 7 and I just wanted to check that I understand how the magic works.

As I understand, when a thread forks, it creates subtasks in its queue (which other thread may or may not steal). When the thread attempts to "join", it actually checks its queue for existing tasks and then recursively perform them, which mean that for any 'join' operation - 2 frames will be added into the thread call stack (one for the join and one for the new taken task invocation).

As I know that the JVM does not support tail call optimization (that may serve in this situation to remove the join method stack frame) I believe that while performing a complicated operation with a lot of forks and joins a thread may throw an StackOverflowError.

Am I right or did they find some cool way to prevent it?

EDIT

Here is a scenario to help clarifying the question: Say (for simplicity) that we only have one thread in the forkjoin pool. At some point in time - the thread forks and then calls join. While in the join method the thread discovers that it can perform the forked task (as it found in its queue) so it invokes the next task. This task in turn forks and then call join - so while executing the join method the thread will find the forked task in its queue (like before) and invoke it. in that stage the call stack will contain at least the frames for two joins and two tasks.

as you can see the fork join framework transformed to plain recursion. Because java does not support tail call optimization - every recursion in java can cause StackOverflowError if it goes deep enough.

My question is - did the implementer of the fork/join framework find some cool way to prevent this situation.

like image 726
bennyl Avatar asked Jun 29 '12 13:06

bennyl


People also ask

How does fork join work in Java?

In Java, the fork/join framework provides support for parallel programming by splitting up a task into smaller tasks to process them using the available CPU cores. In fact, Java 8's parallel streams and the method Arrays#parallelSort use under the hood the fork/join framework to execute parallel tasks.

What is the use of fork and join?

The fork/join framework is an implementation of the ExecutorService interface that helps you take advantage of multiple processors. It is designed for work that can be broken into smaller pieces recursively. The goal is to use all the available processing power to enhance the performance of your application.

What is the difference between fork and join?

The fork systems call assignment has one parameter i.e. Label (L). Join : The join instruction is the that instruction in the process execution that provides the medium to recombine two concurrent computations into a single one.

What is difference between ExecutorService and ForkJoinPool?

The Fork/Join framework in Java 7 is an implementation of the Divide and Conquer algorithm, in which a central ForkJoinPool executes branching ForkJoinTasks. ExecutorService is an Executor that provides methods to manage the progress-tracking and termination of asynchronous tasks.


1 Answers

There is unfortunately nothing magical happening in terms of the thread recursive stack. If your initial task forks/splits and doesn't have a reasonable resolution point then you will run into StackOverflowErrors.

You can probably understand why the tutorial on the JavaDoc splits each subtask in half.

like image 87
John Vint Avatar answered Oct 02 '22 12:10

John Vint