All topics
83 / 101
library
advanced

Fork/Join Framework

Divide computational tasks into subtasks recursively and process them in parallel with work-stealing.

Fork/join splits a task into subtasks, runs them in parallel, and combines the results.

Fork/Join = a team of chefs preparing a banquet. The head chef (main task) divides the menu (fork). Each chef works on their dishes. If one finishes early, they help others (work stealing). Finally, all dishes are combined (join).

Key Concepts

1
    class SumTask extends RecursiveTask<Long> {
      private final long[] a; private final int lo, hi;
2
      protected Long compute() {
        if (hi - lo <= 10_000) {               // base case: just do it
          long s = 0;
          for (int i = lo; i < hi; i++) s += a[i];
          return s;
        }
        int mid = (lo + hi) >>> 1;
        SumTask left = new SumTask(a, lo, mid);
        left.fork();                            // queue it
        long right = new SumTask(a, mid, hi).compute();   // do this one here
        return right + left.join();             // wait for the other
      }
    }
3
    long total = ForkJoinPool.commonPool().invoke(new SumTask(data, 0, data.length));
4
The idiom in that code is worth copying. Fork one half, compute the other on the current thread, then join. Forking both halves and joining both wastes a thread doing nothing.
5
The two task types.
    RecursiveTask<V>    returns a result
    RecursiveAction     returns nothing
6
Work stealing is what makes it scale. Every worker has its own double-ended queue. It pushes and pops its own tasks at one end; an idle worker steals from the other end. There is no central queue to contend on, and load balances itself.
7
The threshold decides whether it pays.
    too small   more time spent creating tasks than working
    too large   idle cores
    start at    size / availableProcessors, then measure
8
Parallel streams run on this. list.parallelStream() builds fork/join tasks over a Spliterator, using ForkJoinPool.commonPool() by default.
list.parallelStream()SpliteratorForkJoinPool.commonPool()
9
Which is the gotcha. The common pool is shared by the whole JVM and sized to cores minus one. One blocking task in it starves everything else, including other parallel streams:
10
    new ForkJoinPool(4).submit(() -> list.parallelStream()...).get();
11
Run your own pool when the work might block, and keep blocking out of the common pool entirely.
12
And it is for CPU-bound divide-and-conquer. For blocking I/O, virtual threads are the better tool — they unmount instead of occupying a worker.
13
What the interviewer is probing.1. "What makes fork/join different from a normal thread pool?" Probing: work stealing. Stalls: "It is just a pool." Moves up: each worker has its own deque and idle workers steal from the other end, so there is no central queue to contend on and load balances itself.
14
2. "Why fork one half and compute the other directly?" Probing: the idiom. Stalls: "Fork both, it is more parallel." Moves up: forking both leaves the current thread waiting; computing one keeps it busy and halves the task overhead.
15
3. "What goes wrong if you block inside the common pool?" Probing: the shared resource. Stalls: "Nothing." Moves up: the common pool is sized to cores minus one and shared by every parallel stream in the JVM, so one blocking task starves everything else.
16
4. "How do you pick the threshold?" Probing: whether you measure or guess. Stalls: "A round number." Moves up: start around size divided by available processors and benchmark — too small and task creation dominates, too large and cores idle.
Use cases:ConcurrencyAlgorithmsPerformance