jdfive

Divide and Conquer — ForkJoin

Priya wants to sum sales numbers for every QuickCart order this month. The list has fifty thousand entries. A plain loop works, but she wonders if splitting the list in half — and half again — could use all her CPU cores better. That is the divide-and-conquer idea. Java’s ForkJoinPool is built exactly for this.

Divide and conquer in one sentence

Break a big job into smaller jobs. Run the small jobs in parallel. Combine the results.

Sum of a big array:

  1. Split the array in two halves.
  2. Sum the left half and sum the right half (maybe split those too).
  3. Add the two sums together.

When the chunk is small enough, just loop and sum — no more splitting.

What is ForkJoinPool?

ForkJoinPool is a special thread pool for recursive, divide-and-conquer work.

Characteristics:

  • Work-stealing — idle threads steal tasks from busy threads
  • Divide-and-conquer — splits tasks into smaller subtasks
  • Efficient for recursive CPU-bound algorithms
  • Used by parallel streams internally (ForkJoinPool.commonPool())

Basic usage:

import java.util.concurrent.ForkJoinPool;

ForkJoinPool pool = ForkJoinPool.commonPool(); // Shared pool — prefer this

// Or a custom pool with a fixed thread count
ForkJoinPool customPool = new ForkJoinPool(4);

// Submit and get result
Future<Long> future = customPool.submit(new OrderSumTask(array, 0, array.length));
long result = future.get();

Do not create many ForkJoin pools. Prefer commonPool() unless you have a strong reason for a private pool.

ForkJoinTask — two flavors

Type Returns a value? Use when
RecursiveTask<V> Yes Sum, search, merge — you need a result
RecursiveAction No Transform every element — no return value

Both extend ForkJoinTask and implement compute().

Key methods:

  • fork() — schedule subtask on another worker
  • compute() — run work on the current thread
  • join() — wait for a forked subtask and get its result
  • invoke() — run the whole task and block until done (called on the pool)

RecursiveTask — sum order totals

Priya sums order totals with RecursiveTask:

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class OrderSumTask extends RecursiveTask<Long> {
    private static final int THRESHOLD = 1000;

    private final long[] orderTotals;
    private final int start;
    private final int end;

    public OrderSumTask(long[] orderTotals, int start, int end) {
        this.orderTotals = orderTotals;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {
        int length = end - start;

        // Base case — small enough to sum directly
        if (length <= THRESHOLD) {
            long sum = 0;
            for (int i = start; i < end; i++) {
                sum += orderTotals[i];
            }
            return sum;
        }

        // Divide into two subtasks
        int mid = start + length / 2;
        OrderSumTask left = new OrderSumTask(orderTotals, start, mid);
        OrderSumTask right = new OrderSumTask(orderTotals, mid, end);

        left.fork();                       // Run left on another thread
        long rightSum = right.compute();   // Sum right part on this thread
        long leftSum = left.join();        // Wait for left part

        return leftSum + rightSum;
    }
}

Run it with invoke:

long[] orderTotals = loadMonthlyTotals(); // 50_000 values

ForkJoinPool pool = ForkJoinPool.commonPool();
OrderSumTask task = new OrderSumTask(orderTotals, 0, orderTotals.length);

long total = pool.invoke(task);
System.out.println("Monthly total: " + total);

fork() schedules the left subtask asynchronously. compute() runs the right subtask on the current thread. join() waits for the left result. This pattern avoids forking both sides and then waiting — one side runs locally, one runs in parallel.

Fork both vs fork one — prefer fork one

// BAD: Both fork, then join both — extra scheduling overhead
left.fork();
right.fork();
return left.join() + right.join();

// GOOD: Fork one, compute the other, join the forked one
left.fork();
long rightSum = right.compute();
long leftSum = left.join();
return leftSum + rightSum;

RecursiveAction — transform every price

When you do not need a return value — just mutate data in place — use RecursiveAction:

import java.util.concurrent.RecursiveAction;

public class ApplyDiscountTask extends RecursiveAction {
    private static final int THRESHOLD = 1000;

    private final double[] prices;
    private final int start;
    private final int end;
    private final double discountRate;

    public ApplyDiscountTask(double[] prices, int start, int end, double discountRate) {
        this.prices = prices;
        this.start = start;
        this.end = end;
        this.discountRate = discountRate;
    }

    @Override
    protected void compute() {
        int length = end - start;

        if (length <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                prices[i] = prices[i] * (1.0 - discountRate);
            }
        } else {
            int mid = start + length / 2;
            ApplyDiscountTask left = new ApplyDiscountTask(prices, start, mid, discountRate);
            ApplyDiscountTask right = new ApplyDiscountTask(prices, mid, end, discountRate);

            left.fork();
            right.compute();
            left.join();
        }
    }
}

Usage:

double[] prices = loadAllProductPrices();
ForkJoinPool pool = ForkJoinPool.commonPool();

ApplyDiscountTask task = new ApplyDiscountTask(prices, 0, prices.length, 0.10);
pool.invoke(task);
// prices array is now updated — 10% off everywhere

RecursiveAction returns void. The work happens as a side effect on shared data (here, the array). Make sure only the base-case threads write to non-overlapping ranges — which divide-and-conquer guarantees.

The threshold matters

THRESHOLD controls when to stop splitting. Too small — too many tiny tasks, scheduling overhead wins. Too large — not enough parallelism.

Start around 500–2000 for array work and tune with real data. Priya picked 1000 for QuickCart’s order totals.

// Too small: overhead > benefit
private static final int THRESHOLD = 10;

// Too large: only one chunk, no parallelism
private static final int THRESHOLD = 1_000_000;

// Reasonable starting point
private static final int THRESHOLD = 1000;

Work-stealing in plain English

Each worker thread keeps its own double-ended queue (deque) of tasks.

  1. A thread pushes and pops tasks from its own deque.
  2. When a thread runs out of work, it steals a task from the bottom of another thread’s deque.
  3. Stealing from the opposite end reduces contention with the owner thread.

Example:

Thread 1: [Task1, Task2, Task3]  <- idle thread steals from here
Thread 2: [Task4, Task5]
Thread 3: [empty]                 <- steals Task3 from Thread 1
Thread 4: [empty]                 <- steals Task5 from Thread 2

That is why ForkJoin pools balance load well for divide-and-conquer — fast threads pick up slack from slow threads automatically.

Search example: find a product id

Summing is not the only pattern. Priya searches a list of product ids:

import java.util.concurrent.RecursiveTask;

public class FindProductTask extends RecursiveTask<String> {
    private static final int THRESHOLD = 500;

    private final String[] productIds;
    private final int start;
    private final int end;
    private final String target;

    public FindProductTask(String[] productIds, int start, int end, String target) {
        this.productIds = productIds;
        this.start = start;
        this.end = end;
        this.target = target;
    }

    @Override
    protected String compute() {
        int length = end - start;

        if (length <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                if (productIds[i].equals(target)) {
                    return productIds[i];
                }
            }
            return null;
        }

        int mid = start + length / 2;
        FindProductTask left = new FindProductTask(productIds, start, mid, target);
        FindProductTask right = new FindProductTask(productIds, mid, end, target);

        left.fork();
        String found = right.compute();
        if (found != null) {
            return found;
        }
        return left.join();
    }
}

Usage:

ForkJoinPool pool = ForkJoinPool.commonPool();
String result = pool.invoke(
    new FindProductTask(productIds, 0, productIds.length, "SKU-8842")
);

Same split-fork-join shape. Different base-case logic. For search, check the right result before waiting on the left — you can stop early if found.

ForkJoinPool vs parallel streams

Parallel streams already use ForkJoinPool.commonPool() internally. Use parallel streams for simple collection processing:

long total = orderTotals.parallelStream().mapToLong(Long::longValue).sum();

Write a RecursiveTask when:

  • The problem is naturally recursive (merge sort, tree walk, big array scan).
  • You need control over splitting strategy and threshold.
  • Stream operations do not fit the shape of the problem.

For Priya’s monthly sum, either works. The explicit task teaches what parallel streams do behind the scenes.

What not to do

Do not put blocking I/O inside ForkJoin tasks. Database calls and HTTP requests block a worker thread. ForkJoin workers expect short CPU work. Use an ExecutorService for I/O.

// BAD: Blocks a ForkJoin worker waiting on network
pool.submit(() -> httpClient.fetchOrderStatus(orderId));

Do not create many ForkJoin pools — each has overhead and its own threads:

// BAD
ForkJoinPool pool1 = new ForkJoinPool();
ForkJoinPool pool2 = new ForkJoinPool();

// GOOD
ForkJoinPool pool = ForkJoinPool.commonPool();

Always handle exceptions from join() and invoke() — failures in subtasks bubble up wrapped in ExecutionException:

try {
    Long result = pool.invoke(task);
} catch (Exception e) {
    // Handle failure from subtask
}

What to remember

  • Divide-and-conquer splits big work into smaller pieces, then combines results.
  • RecursiveTask returns a value; RecursiveAction returns nothing.
  • Extend the right class and implement compute().
  • Use fork() on one subtask, compute() the other, then join() for the result.
  • Pick a threshold — below it, solve directly without more splitting.
  • Work-stealing lets idle threads grab tasks from busy threads.
  • Prefer ForkJoinPool.commonPool() — parallel streams use it too.
  • Use ForkJoin for CPU-bound recursive jobs, not for I/O.

What Priya does next: she has the building blocks — collections, atomics, ThreadLocal, latches, parallel streams, and ForkJoin. She wires them into real QuickCart patterns like producer-consumer queues and learns how to spot deadlocks before they hit production.