Fork/Join Framework in Java

The Fork/Join framework (Java 7), in java.util.concurrent, is designed for divide-and-conquer work: a big task splits (forks) itself into smaller tasks, the pieces run in parallel, and their results are combined (joined). It runs on a ForkJoinPool, whose threads use work stealing: an idle thread takes waiting tasks from the end of another thread's queue, which keeps all cores busy. Parallel streams use the same machinery. In this lesson, you will write a RecursiveTask, learn how work stealing works, and see how parallel streams use it.

The Classes

Work Stealing

• Each worker has its own double-ended queue (deque) of tasks.
• A worker pushes subtasks it forks onto its own deque and takes from that same end.
• An idle worker steals from the other end of a busy worker's deque, where the bigger, older tasks are.

Example: Summing an Array with RecursiveTask

Let's see an example that sums 10 million numbers by splitting the range until the pieces are small.

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
 
public class ForkJoinSum extends RecursiveTask<Long> {
    static final int THRESHOLD = 100_000;
    final long[] numbers;
    final int from, to;
 
    ForkJoinSum(long[] numbers, int from, int to) {
        this.numbers = numbers;
        this.from = from;
        this.to = to;
    }
 
    @Override
    protected Long compute() {
        if (to - from <= THRESHOLD) {
            long sum = 0;
            for (int i = from; i < to; i++) sum += numbers[i];
            return sum;
        }
        int mid = (from + to) / 2;
        ForkJoinSum left = new ForkJoinSum(numbers, from, mid);
        ForkJoinSum right = new ForkJoinSum(numbers, mid, to);
        left.fork();
        long rightSum = right.compute();
        return left.join() + rightSum;
    }
 
    public static void main(String[] args) {
        long[] numbers = new long[10_000_000];
        for (int i = 0; i < numbers.length; i++) numbers[i] = i + 1;
 
        long total = ForkJoinPool.commonPool()
            .invoke(new ForkJoinSum(numbers, 0, numbers.length));
        System.out.println("Sum: " + total);
        System.out.println("Correct? "
            + (total == 10_000_000L * 10_000_001L / 2));
    }
}

Sum: 50000005000000
Correct? true

Explanation: compute() sums the range directly if it's small (100,000 numbers or fewer). Otherwise it splits the range in two, forks the left half (so another worker can steal it), computes the right half itself, then joins the left result. The pool's workers keep splitting and stealing until all cores are busy.

How Parallel Streams Use Fork/Join

list.parallelStream() splits its source with a Spliterator, wraps each piece in a fork/join task, and runs them in ForkJoinPool.commonPool(). That's why parallel streams share the common pool with each other and with CompletableFuture's default async tasks (see "Parallel Streams in Java").

import java.util.concurrent.ForkJoinPool;
import java.util.stream.LongStream;
 
public class CommonPool {
    public static void main(String[] args) {
        long sum = LongStream.rangeClosed(1, 10_000_000).parallel().sum();
        System.out.println("Parallel stream sum: " + sum);
        System.out.println("Common pool parallelism: "
            + (ForkJoinPool.commonPool().getParallelism() >= 1));
    }
}

Parallel stream sum: 50000005000000
Common pool parallelism: true

Explanation: The parallel stream gives the same result as the hand-written task. The common pool's parallelism is usually one less than the number of cores, because the calling thread also helps.

Common Mistakes

Calling left.fork(); right.fork(); left.join(); right.join();. The current thread sits idle; compute one half directly.

A threshold that's too small. Creating millions of tiny tasks costs more than it saves.

Blocking I/O in common-pool tasks. It starves parallel streams and CompletableFutures.

Interview Corner

Practice

1. Easy: Change THRESHOLD to 1,000 and to 5,000,000 and time both. Explain the difference.
2. Harder: Write a RecursiveTask<Integer> that finds the maximum value in a large array.

Key Takeaways