fork/join and work stealing

the picture

a stack of 64 exam papers to grade, four teachers. one teacher takes the whole stack, splits it, puts half on her own pile and keeps grading-and-splitting the rest. the others are standing around with nothing, so they walk over and take from the bottom of her pile, which is where the biggest untouched chunk is. she keeps working from the top of her own pile, they work from the bottom, and they almost never reach for the same papers.

that's the trick: the owner and the thieves work opposite ends of the same pile, so they rarely collide, and a thief who steals grabs a big chunk and doesn't need to come back for a while.

split, compute, join

the classic shape is RecursiveTask<V> (returns a value) or RecursiveAction (doesn't). compute() either does the work directly or splits:

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
import java.util.stream.LongStream;
 
class Sum extends RecursiveTask<Long> {
    static final int THRESHOLD = 10_000;
    final long[] a;
    final int lo, hi;
 
    Sum(long[] a, int lo, int hi) { this.a = a; this.lo = lo; this.hi = hi; }
 
    @Override
    protected Long compute() {
        if (hi - lo <= THRESHOLD) {                    // small enough: just do it
            long s = 0;
            for (int i = lo; i < hi; i++) s += a[i];
            return s;
        }
        int mid = (lo + hi) >>> 1;
        Sum left = new Sum(a, lo, mid);
        left.fork();                                   // push the left half onto my deque
        long right = new Sum(a, mid, hi).compute();    // do the right half myself
        return right + left.join();                    // then collect the left half
    }
}
 
void main() {
    long[] a = LongStream.range(0, 10_000_000).toArray();
    long total = ForkJoinPool.commonPool().invoke(new Sum(a, 0, a.length));
    IO.println(total);
    IO.println(LongStream.of(a).parallel().sum());     // a parallel stream: same pool, same idea
}

49999995000000
49999995000000

notice the shape of compute(): fork one half, compute the other yourself, then join. the current thread never sits idle waiting for both halves.

left.fork();
right.fork();
return left.join() + right.join();

left.fork();
long r = right.compute();
return r + left.join();

the left version works, but this thread pushes two tasks and then immediately waits, so one task's worth of work moves through the deque for nothing. and if you join in the wrong order (right.join() first, when left was forked last), the thread can't just pop its own most recent task, and has to do more expensive helping. fork one, compute one.

work stealing

each worker owns a double-ended queue. the owner pushes forked tasks onto the top and pops from the top (LIFO: the newest task, the smallest one, whose data is still in its cache). an idle worker picks a victim and takes from the base (FIFO: the oldest task, which, in a divide-and-conquer tree, is the biggest one left).

the numbers from a real run line up with that. summing 200 million longs with a threshold of 100,000 (so 2,000 leaf tasks) on a 14-worker pool, jdk 25, arm mac:

about 4.7× faster with 14 workers, not 14×. summing is memory-bound: the cores spend most of their time waiting for the array to stream in from RAM, and adding more cores doesn't make RAM faster. CPU-heavy leaves (hashing, image filters, simulations) scale much closer to the core count.

join doesn't just wait

when a worker calls join() on a task that isn't done, it doesn't simply park. if the task is still sitting in its own deque, it pops it and runs it right there. if a thief took it, the worker can help by running tasks from the thief's deque. so a pool of 4 threads can run a recursion thousands of tasks deep without 4,000 blocked threads. that's also why fork/join tasks should be small, CPU-bound and non-blocking: the whole scheme assumes a worker is always either computing or helping.

the common pool

ForkJoinPool.commonPool() is one JVM-wide pool, with parallelism of (cores − 1) by default, since the thread that submits work usually helps too. on my 14-core machine, that's 13. it's used by:

• parallel streams (list.parallelStream(), stream.parallel())
• CompletableFuture.supplyAsync(...) and the other *Async methods without an executor
• Arrays.parallelSort, Arrays.parallelSetAll...

so one library that blocks in the common pool slows down every parallel stream in your app. if you need isolation, create your own new ForkJoinPool(n) and invoke tasks on it.