java Fork/Join clarification about stack usage

Question

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.

Twirp

@assylias - sure if you can spare the points :) – Twirp

Answer 1

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.

Solemnize

Answer 2

Generally each new task pushed on the stack is half the size of the previous one. So the amount of work grow exponentially with stack size. Even with a tiny stack, you're going to be able to fit on more than enough work to keep you busy for some time.

Kamerad

Answer 3

I hope i understand you in the right way.

There is internal queue in forkjoinpool that keeps tasks that you want to execute, so no stack overflow could be thrown, but you have to prepare for high memory utilisation.

Very interesting place for fork method is ForkJoinWorkerThread.pushTask with unsafe object usage, so you should pay attention that array is used to store tasks.

EDIT: First and simple - when you are on the top of the queue you are simply unpushed and executed, and retult is returned. (forkjointask.java:353)

Different approach is used when you have dependencies, in this case control returned to WorkerThread who is then responsible for detecting chains and executing them. By first worker check local queue for any unfisihed tasks, and if no such tasks it executes passed job and returns result, otherwise it goes to the next case. Which is helping to stealers several times. Nothing could help... retries which is at first step equals to MAX_HELP is zero now - control is passed to pool, which performs several checks and executes tryAwaitDone. And in this method wait is invoked to wait for task completion.

This would mean that fork join pool would finish in several steps, trying to optimize speed and time by avoiding calls to wait. However it could finish in wait, then this would mean synchronization process to start which is very expensive.

So there is no subsequent joins for inifinite depth, but logical attempts to execute tasks as fast as possible.

Vital