Concurrency

Fork/Join and divide and conquer

Fork/Join splits a big job into smaller pieces recursively, runs the pieces on a pool of threads, and joins the results.

🔎 Unravel this example Prerequisites (1)

Learn these first

Executors and thread pools

At a glance

Mental model

Counting a huge stack of ballots: split the pile in two, give half to a colleague, and keep splitting until each pile is small enough to count by hand; then add the partial counts up.

What happens, in order

1Extend RecursiveTask<V> (returns a value) or RecursiveAction (no value) and implement compute(): if the piece is small, do it directly; otherwise split in two, left.fork() (run asynchronously), compute the right half yourself and left.join()
2Run it with ForkJoinPool.commonPool().invoke(task) or new ForkJoinPool(4).invoke(task)
3Choose a threshold: pieces smaller than a few thousand operations are cheaper to compute than to splitToo small gives overhead; too large gives idle threads.
4Work stealing: idle workers take tasks from the back of busy workers' queues, which balances uneven pieces automatically

Remember

It suits CPU-bound, divisible and independent work (sorting, summing, image processing, tree traversal)
Fork one half and compute the other in the current thread (invokeAll(left, right)); forking both wastes a thread
Each worker has a double-ended queue

Watch out

A threshold that is too smallBlocking I/O inside tasksForking both halves and joining in the wrong orderSharing a mutable array without partitioning it

Example (highlighted lines explain it)

import java.util.concurrent.*;public class SumTask extends RecursiveTask<Long> {  private static final int THRESHOLD = 10_000;  private final int[] data; private final int from, to;  SumTask(int[] data, int from, int to) { this.data = data; this.from = from; this.to = to; }  @Override protected Long compute() {    if (to - from <= THRESHOLD) { long s = 0; for (int i = from; i < to; i++) s += data[i]; return s; }    int mid = (from + to) >>> 1;    SumTask left = new SumTask(data, from, mid);    left.fork();    long right = new SumTask(data, mid, to).compute();    return left.join() + right;  }}

line 2 uses RecursiveTask, the core of Fork/Join and divide and conquer
line 10 uses fork, the core of Fork/Join and divide and conquer

Read the full explanation (about 1 min)

Fork/Join splits a big job into smaller pieces recursively, runs the pieces on a pool of threads, and joins the results. Parallel streams and CompletableFuture run on the same machinery.

A mental model

Counting a huge stack of ballots: split the pile in two, give half to a colleague, and keep splitting until each pile is small enough to count by hand; then add the partial counts up.

How it works

Extend RecursiveTask<V> (returns a value) or RecursiveAction (no value) and implement compute(): if the piece is small, do it directly; otherwise split in two, left.fork() (run asynchronously), compute the right half yourself and left.join().

Run it with ForkJoinPool.commonPool().invoke(task) or new ForkJoinPool(4).invoke(task).

Choose a threshold: pieces smaller than a few thousand operations are cheaper to compute than to split. Too small gives overhead; too large gives idle threads.

Work stealing: idle workers take tasks from the back of busy workers' queues, which balances uneven pieces automatically.

Going deeper

It suits CPU-bound, divisible and independent work (sorting, summing, image processing, tree traversal). It is a bad fit for blocking I/O, which starves the small pool.

Fork one half and compute the other in the current thread (invokeAll(left, right)); forking both wastes a thread.

Exceptions are rethrown from join()/invoke(); the sub-tasks must not share mutable state.

Under the hood

Each worker has a double-ended queue. It pushes and pops its own tasks at one end, and thieves steal from the other, reducing contention. The pool size defaults to the number of cores minus one for the common pool.

Common mistakes

A threshold that is too small.
Blocking I/O inside tasks.
Forking both halves and joining in the wrong order.
Sharing a mutable array without partitioning it.

How Unravel recognises it

When you paste code, Unravel looks for these signs of fork/join and divide and conquer. Spotting them yourself is a good habit when you read unfamiliar code:

Types: RecursiveTask RecursiveAction ForkJoinTask
Method calls: fork() commonPool()

Part of a learning path

Concurrency beyond the basics · previous: Virtual threads · next: Timers and scheduled executors

Related concepts

Parallel streamsJava language Executors and thread poolsConcurrency RecursionJava language

Frequently asked questions

What is Fork/Join and divide and conquer?

Fork/Join splits a big job into smaller pieces recursively, runs the pieces on a pool of threads, and joins the results. Parallel streams and CompletableFuture run on the same machinery.

What are the most common mistakes with Fork/Join and divide and conquer?

A threshold that is too small. Blocking I/O inside tasks. Forking both halves and joining in the wrong order. Sharing a mutable array without partitioning it.

How can I see Fork/Join and divide and conquer in real code?

Paste your own Java into Unravel and it will point out where fork/join and divide and conquer appears, explain how it works at the detail level you choose, and draw the flow of the code around it.