The Fork Join Overhead
In the fork join model a task forks subtasks that may run in parallel, then joins them to wait for completion. Forking and joining are not free, and that overhead shapes when parallelism pays off.
Where the cost comes from
Each fork and join carries real expense:
- Creating a task object and pushing it to a queue.
- Possible stealing by another worker, with memory traffic across cores.
- Synchronizing at the join to wait for children.
If a forked task does only a few operations, this bookkeeping can cost more than the task itself, and the parallel version runs slower than the serial one.
Cutting off the recursion
The standard fix is a sequential cutoff. Below a chosen subproblem size the algorithm stops forking and just runs serially. This keeps the cheap leaves out of the scheduler:
- Large nodes near the root still fork and expose parallelism.
- Small leaves run inline with no task overhead.
Tuning the cutoff trades exposed parallelism against per task cost.
Key idea
Forking and joining cost real time, so a sequential cutoff runs small subproblems inline and reserves task creation for large ones.