BrewlearnFork/Join framework in Java
Divide and conquer with RecursiveTask and work stealing.
Divide and conquer
Fork/Join speeds up divide-and-conquer work across CPU cores. A RecursiveTask<V> returns a value; a RecursiveAction returns nothing. In compute(): if the piece is small, solve it directly; otherwise split it into subtasks.
fork, compute, join
fork() schedules one half asynchronously. The current thread computes the other half itself. Then join() waits for the forked half's result.
protected Long compute() {
if (hi - lo <= 1_000) return sumDirect();
int mid = (lo + hi) >>> 1;
var left = new SumTask(a, lo, mid);
left.fork();
long right =
new SumTask(a, mid, hi).compute();
return right + left.join();
}Order matters
left.fork();
long l = left.join();
long r = right.compute();
return l + r;Joining right after forking makes this thread wait for the left half before starting the right one. Correct sums, zero speedup.
left.fork();
long r = right.compute();
long l = left.join();
return l + r;The right half runs while the left half runs elsewhere. Join last.
The threshold
Every fork costs something: creating a task object, scheduling it, joining it. Split until the pieces are reasonably large, then compute sequentially. Too small a threshold and the bookkeeping dwarfs the useful work.
Work stealing
Each worker has its own deque of tasks. It works from one end; idle workers steal from the other end of busy workers' deques. Load spreads automatically, keeping every core busy without a central dispatcher.
Why compute one half yourself?
Why not just fork() both halves and then join() them both?
Think about it, then reveal the answer
The current thread would only sit waiting. Computing one half itself keeps it busy, and it saves the overhead of one extra task. Fork one, compute one, join last.
Blocking the common pool
Parallel streams run on the shared ForkJoinPool.commonPool(), sized for CPU work with about (cores − 1) threads. Call a slow REST API inside parallelStream() and blocking I/O occupies those few workers, so unrelated parallel streams across the app crawl. Keep Fork/Join tasks CPU-bound.
Hiding in plain sight
You may already use Fork/Join without knowing it: parallel streams and Arrays.parallelSort run on the common pool. It shines on big CPU-heavy jobs like sorting, image processing and aggregations, and does nothing for I/O.
Key takeaways
- RecursiveTask<V> returns a value; RecursiveAction doesn't
- Split until small, then compute sequentially (threshold)
- fork() one half, compute() the other, then join()
- Work stealing balances load; avoid blocking I/O in tasks
The common pool's default parallelism is cores minus one, because the thread that calls join() or starts a parallel stream pitches in too.
Practice questions
Why does a RecursiveTask stop splitting below a threshold?
- Creating and scheduling tiny tasks costs more than computing them directly
- ForkJoinPool limits each task to 1,000 elements
- Splitting further always causes StackOverflowError
- Small tasks can't be stolen by other workers
Check your answer
Creating and scheduling tiny tasks costs more than computing them directly. Every fork has overhead. A sensible threshold keeps tasks large enough that the useful work dwarfs the bookkeeping.
A team uses list.parallelStream() to call a slow REST API for each item. Soon unrelated parallel streams across the app become sluggish. Why?
- Parallel streams share ForkJoinPool.commonPool(); blocking calls tie up its few workers
- Each parallelStream() call creates a new pool and exhausts memory
- REST clients are not allowed inside streams
- Parallel streams always run on a single thread
Check your answer
Parallel streams share ForkJoinPool.commonPool(); blocking calls tie up its few workers. The common pool is sized for CPU-bound work. Blocking I/O occupies its threads, starving every other user of the pool.