Skip to content
Tutorials Center
My learning

Topics

Lesson 136 of 201 ยท Concurrency

The Fork/Join Framework

Learn the Java Fork/Join framework - RecursiveTask and RecursiveAction, divide-and-conquer sums and sorts, thresholds, work stealing, and how parallel streams use it.

Some problems split naturally into smaller copies of themselves: summing an array is summing two halves and adding the results; sorting is sorting two halves and merging them. That's divide and conquer, the same idea as in Recursion. The Fork/Join framework (java.util.concurrent, since Java 7) runs those pieces in parallel: a task forks subtasks that other threads can pick up, then joins them to combine their results.

Behind it sits ForkJoinPool, a thread pool built for many tiny, short-lived tasks, using a scheduling trick called work stealing. You may never write a RecursiveTask at work, but you use this machinery every time you call parallelStream(), and understanding it explains when parallelism pays off and when it doesn't. This lesson builds on Executors and Thread Pools.

The pattern

Every fork/join task has the same shape:

Java
protected Result compute() {
    if (problem is small enough) {
        return solve it directly;              // sequential base case
    }
    split into left and right halves;
    left.fork();                               // let another thread take the left half
    Result r = right.compute();                // do the right half ourselves
    Result l = left.join();                    // wait for (or help with) the left half
    return combine(l, r);
}

You extend one of two abstract classes:

  • RecursiveTask<V> when each piece returns a result (a sum, a count, a merged list).
  • RecursiveAction when pieces only have side effects (sorting or transforming an array in place).

Both extend ForkJoinTask, a lightweight cousin of Future. You start the root task with pool.invoke(task), which waits for the result.

A parallel sum with RecursiveTask

Java Summing an array with RecursiveTask

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Both sums are 1,998,000,000, as they must be. A long accumulator matters here: the total doesn't fit in an int.

The last line shows how many worker threads the shared common pool uses. It defaults to the number of CPU cores minus one, with a minimum of one (the thread that calls invoke can help too), so it differs between your laptop, a server and our sandbox. On a single-core machine you'll see no speedup at all; on eight cores, CPU-heavy work split this way can run several times faster than a plain loop once the JIT has warmed up. (A simple sum like this one is limited mostly by memory speed, so it gains less.)

Why fork one half and compute the other?

left.fork(); right.compute(); left.join(); keeps the current thread busy instead of creating two tasks and sitting idle. Two mistakes to avoid:

  • left.fork(); left.join(); right.compute(); runs the halves one after the other: no parallelism.
  • left.fork(); right.fork(); left.join(); right.join(); works, but joins in the wrong order (join the most recently forked task first) and wastes the current thread's time. If you want to fork both, use invokeAll(left, right), which does the right thing for you.

Choosing the threshold

The threshold decides when to stop splitting. Too small, and the cost of creating and scheduling millions of tiny tasks swamps the actual work. Too large, and there are too few pieces to keep every core busy or to balance uneven work. A common rule of thumb: aim for each leaf to do at least 10,000 or so basic operations, and for the total number of leaves to be a few times larger than the number of cores. Then measure.

Sorting in place with RecursiveAction

A RecursiveAction returns nothing; it works by modifying shared data. Merge sort is a natural fit: sort two halves in parallel, then merge them. Each subtask touches only its own range of the array, so no locking is needed. The join in invokeAll guarantees that the halves' writes are visible before the merge.

Java Parallel merge sort with RecursiveAction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The result matches Arrays.sort exactly. This example creates its own ForkJoinPool(4) instead of using the common pool; since Java 19 a pool can be closed with try-with-resources, which waits for its tasks. (For real code, Arrays.parallelSort already does a parallel sort on the common pool.)

Work stealing

A normal thread pool has one shared queue, and every thread competes for it. A ForkJoinPool gives each worker its own double-ended queue (deque):

  1. When a task forks a subtask, the subtask goes onto the head of the current worker's deque.
  2. The worker takes its next task from the same end (last in, first out). It keeps working on the newest, smallest pieces, whose data is probably still in the CPU cache.
  3. An idle worker steals from the tail of another worker's deque, first in, first out. The oldest tasks there are the biggest pieces (they were split off near the top of the recursion), so one steal gives the thief a lot of work.

Owners and thieves work on opposite ends, so they rarely collide. And when a thread calls join() on a task that isn't done, it doesn't just sleep: it runs other pending tasks in the meantime. That's why fork/join tasks must not block on I/O or locks: a blocked worker can't help anyone.

Java Watching work get spread and stolen

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The prime count (22,525) and the number of leaves (256) are always the same, because the range splits exactly in half eight times. How the leaves are spread over the four workers, and the steal count, change from run to run and depend on how many cores the machine has. Sometimes one worker does most of the work, which is fine: work stealing balances only as much as needed to keep idle threads busy.

Fork/join and parallel streams

list.parallelStream() and stream.parallel() (Advanced Streams) split their source with a Spliterator and process the pieces as fork/join tasks in the common pool. Everything in this lesson applies to them:

  • Parallelism needs enough work per element, or splitting overhead wins. Summing a million numbers sequentially takes about a millisecond; parallel versions often aren't faster for work that small.
  • The source must split well. Arrays, ArrayList and IntStream.range split evenly; LinkedList, Stream.iterate and I/O-backed streams split badly.
  • No blocking. A parallel stream that makes HTTP calls ties up the common pool that every other parallel stream and CompletableFuture.supplyAsync in your JVM shares.
  • No shared mutable state. Use reduce, collect and sum, not a lambda that adds to a shared ArrayList.

If you must run a parallel stream with a different number of threads, submit it from inside your own pool; its tasks then run in that pool:

Java
try (var pool = new ForkJoinPool(3)) {
    long count = pool.submit(() -> bigList.parallelStream().filter(this::expensiveCheck).count()).join();
}

This relies on an implementation detail, but it's a widely used one. You can also size the common pool for the whole JVM with -Djava.util.concurrent.ForkJoinPool.common.parallelism=N.

Exceptions and other details

  • An exception thrown inside compute() is rethrown from join() or invoke() in the waiting thread. Unchecked exceptions come through as they are; checked ones can't be thrown from compute() at all, so wrap them.
  • fork() called from a thread outside any pool submits the task to the common pool.
  • ForkJoinTask.isCompletedAbnormally() and getException() let you inspect failures without throwing.
  • Tasks that must block occasionally can use ForkJoinPool.managedBlock(...), which lets the pool add a spare thread. For mostly-blocking work, use virtual threads instead.
  • CountedCompleter is a lower-level ForkJoinTask used inside the JDK (parallel streams use it) for completion-driven trees of tasks. You'll rarely need it directly.

When to use fork/join

Use it for CPU-bound, recursively divisible work on in-memory data: sums, searches, sorting, image filters, matrix math, tree traversals. In practice, try a parallel stream or Arrays.parallelSort/parallelPrefix first; write a RecursiveTask when the problem's shape doesn't fit a stream. Don't use it for I/O or for a handful of large independent jobs; a regular executor or CompletableFuture is clearer there.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is wrong with left.fork(); left.join(); right.compute(); inside compute()?

    join blocks until the left half is done, and only then does the current thread start on the right. Fork, compute the other half, then join.
  2. 2. Which class do you extend for a fork/join task that returns a count?

    RecursiveTask<V> returns a value from compute(); RecursiveAction is for tasks that return nothing.
  3. 3. In work stealing, from which end of another worker's deque does an idle worker steal, and why?

    Owners push and pop at the head (newest, small tasks); thieves take from the tail, where the oldest, biggest pieces from higher in the recursion sit.
  4. 4. What happens if the threshold is set to 1, so every element becomes its own task?

    The result stays correct, but creating and scheduling millions of tiny tasks costs far more than the work they do.
  5. 5. Why are blocking calls (HTTP, database) a bad idea inside parallel streams?

    The common pool has about one thread per core and is shared JVM-wide. Use an executor or virtual threads for blocking work.

Summary

  • Fork/join runs divide-and-conquer algorithms in parallel: split until small, solve directly, combine.
  • Extend RecursiveTask<V> for results and RecursiveAction for side effects; start with pool.invoke(task).
  • Use left.fork(); right.compute(); left.join(); or invokeAll(left, right); pick a threshold that keeps leaves meaningfully large.
  • ForkJoinPool uses per-worker deques and work stealing; joining threads help with other tasks, so tasks must not block.
  • Parallel streams, Arrays.parallelSort and CompletableFuture's default executor all use the common pool, whose size depends on the CPU count.
  • Fork/join suits CPU-bound work on in-memory data; use executors or virtual threads for I/O.

Next: Virtual Threads and Structured Concurrency, Java 21's answer to running millions of blocking tasks.