Fork-Join Framework — RecursiveTask, RecursiveAction, Work Stealing, and Parallel Arrays

In this tutorial, you will learn about Fork. We cover key concepts, practical examples, and best practices to help you master this topic.

Java's Fork-Join framework implements the divide-and-conquer algorithm pattern with efficient work-stealing thread pools. The framework is designed for tasks that can be broken into smaller subtasks recursively — instead of creating a new thread for each subtask, idle threads "steal" work from busy threads' queues, achieving near-perfect Load Balancing.

What You'll Learn

• RecursiveTask for tasks with return values
• RecursiveAction for void tasks
• The work-stealing algorithm
• Parallel array processing with ForkJoinPool

Why It Matters

The Fork-Join framework powers Arrays.parallelSort(), parallelStream(), and CompletableFuture's default pool. Understanding it helps you write efficient divide-and-conquer algorithms that automatically scale to available processors.

Real-World Use

Merge sort, quicksort, and large-scale data processing use Fork-Join. Image processing (apply filter to each pixel), financial risk calculations, and scientific simulations benefit from work-stealing parallelism.

ForkJoinPool

The default pool is available via ForkJoinPool.commonPool():

ForkJoinPool pool = ForkJoinPool.commonPool();
System.out.println(pool.getParallelism()); // typically #CPU cores - 1

RecursiveTask

For tasks that return a value:

class SumTask extends RecursiveTask<Long> {
    private static final long THRESHOLD = 10_000;
    private final long[] array;
    private final int start;
    private final int end;

    SumTask(long[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {
        int length = end - start;
        if (length <= THRESHOLD) {
            // Compute directly
            long sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        }

        // Split in half
        int mid = start + length / 2;
        SumTask left = new SumTask(array, start, mid);
        SumTask right = new SumTask(array, mid, end);

        left.fork();         // fork left (may run in another thread)
        long rightResult = right.compute(); // compute right (current thread)
        long leftResult = left.join();       // wait for left result

        return leftResult + rightResult;
    }
}

// Usage
long[] numbers = new long[1_000_000];
Arrays.fill(numbers, 1);
ForkJoinPool pool = new ForkJoinPool();
long sum = pool.invoke(new SumTask(numbers, 0, numbers.length));
System.out.println(sum); // 1,000,000

RecursiveAction

For tasks without a return value:

class ArrayTransform extends RecursiveAction {
    private static final int THRESHOLD = 1000;
    private final double[] array;
    private final int start;
    private final int end;

    ArrayTransform(double[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        int length = end - start;
        if (length <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                array[i] = Math.sqrt(array[i] * array[i] + array[i] * array[i]);
            }
            return;
        }

        int mid = start + length / 2;
        ArrayTransform left = new ArrayTransform(array, start, mid);
        ArrayTransform right = new ArrayTransform(array, mid, end);

        invokeAll(left, right); // fork both and join — convenience method
    }
}

Work Stealing

The magic of Fork-Join lies in work stealing:

1. Each worker thread maintains a deque of tasks
2. When a thread executes fork(), it pushes the task onto its own deque (LIFO)
3. When a thread runs out of work, it steals from the tail of another thread's deque (FIFO)
4. Stealing from the opposite end ensures large tasks are stolen (they are at the tail), keeping stolen work coarse-grained

This design achieves excellent load balancing with minimal contention.

Join Strategies

class ExampleTask extends RecursiveTask<Integer> {
    ExampleTask left, right;

    @Override
    protected Integer compute() {
        // Strategy 1: fork left, compute right, join left
        left.fork();
        int rightResult = right.compute();
        int leftResult = left.join();
        return leftResult + rightResult;

        // Strategy 2: invokeAll (convenience)
        // invokeAll(left, right);
        // return left.join() + right.join();

        // Strategy 3: fork both, join both (less optimal)
        // left.fork();
        // right.fork();
        // return left.join() + right.join();
    }
}

Strategy 1 is optimal — the current thread computes one subtask while the other may run in parallel.

Custom ForkJoinPool

// Custom pool with 4 threads
ForkJoinPool pool = new ForkJoinPool(4);
MyTask task = new MyTask(data);
pool.execute(task);  // asynchronous
pool.invoke(task);   // synchronous, returns result

// Always shut down when done
pool.shutdown();

// Common pool — do not shut down
ForkJoinPool.commonPool().invoke(task);

Parallel Arrays

Java 8's Arrays.parallel* methods use Fork-Join internally:

int[] numbers = {5, 3, 1, 4, 2};
Arrays.parallelSort(numbers);                      // multi-threaded sort
Arrays.parallelSetAll(numbers, i -> i * i);         // parallel initialization
Arrays.parallelPrefix(numbers, Integer::sum);        // parallel prefix (cumulative)

For large arrays, parallelSort outperforms sort significantly.

Common Mistakes

1. Setting the threshold too low. The overhead of forking and joining exceeds the cost of sequential computation. A good rule: threshold should yield at least 10,000-100,000 operations per leaf task.
2. Calling fork() before compute() on both subtasks. left.fork(); right.fork(); left.join(); right.join(); is correct but less efficient than left.fork(); right.compute(); left.join();.
3. Using ForkJoinPool on I/O-bound tasks. Fork-Join is designed for CPU-bound tasks. I/O-bound tasks block worker threads, reducing parallelism. Use ThreadPoolExecutor for I/O.
4. Not shutting down a custom ForkJoinPool. Custom pools have non-daemon threads. Always call shutdown() or use the common pool.
5. Sharing mutable state between subtasks. Each subtask should work on its own slice of data. Accessing shared state requires synchronization, defeating parallelism.

Practice Questions

1. What is the difference between RecursiveTask and RecursiveAction?
RecursiveTask returns a value from compute(). RecursiveAction is void.

2. How does work stealing work?
Idle threads steal tasks from the tail of busy threads' deques. Since the tail contains large (coarse-grained) tasks, stolen work is substantial enough to justify the steal.

3. What is the optimal strategy for forking subtasks?
Fork one subtask, compute the other directly, then join the forked task. This ensures the current thread stays busy.

4. What is the common pool?
ForkJoinPool.commonPool() — a shared pool across all parallel streams and CompletableFutures. Its size is Runtime.getRuntime().availableProcessors() - 1.

5. How is the threshold determined?
By profiling. The threshold should be large enough that the sequential overhead of forking is negligible compared to the computation. Start with 10,000-100,000 elements per leaf task.

Challenge Question:
Implement a parallel merge sort using Fork-Join. For arrays smaller than 1000 elements, use Arrays.sort(). For larger arrays, split, sort recursively, and merge. Use invokeAll() to parallelize both halves. Test on a 10-million-element array and compare performance with sequential Arrays.sort().

FAQ

Mini Project

Write a program ForkJoinDemo.java that:

1. Implements parallel sum using RecursiveTask — compare with sequential sum
2. Implements parallel array transform using RecursiveAction (square each element)
3. Implements a parallel search — find maximum value in a large array
4. Compares ForkJoinPool.commonPool() vs custom pool performance
5. Compares sequential vs parallel merge sort for different array sizes
6. Demonstrates the effect of threshold size on performance
7. Uses Arrays.parallelSort() and compares it with custom Fork-Join sort

What's Next

Fork-Join parallelism is powerful but still uses platform threads. Java 21 introduced virtual threads (Project Loom) — lightweight threads that drastically simplify concurrent programming. Lesson 57 covers virtual threads, structured concurrency, and the differences from platform threads.