ForkJoin and work stealing

Key points

• Fork/join is divide and conquer: split until a piece is small enough, compute it, then join the pieces back up.
• Every worker has its own deque. An idle worker steals from the tail of a busy one, so no core sits still.
• The pattern is fork one half, compute the other half yourself, then join. Forking both halves wastes a thread.
• Choose a threshold where the work costs more than the split. A few thousand elements is a normal starting point.
• It is built for CPU-bound work. Blocking inside a fork/join task starves every other task in the pool.
• ForkJoinPool.commonPool() is shared by the whole JVM, and it is exactly what parallel streams use.

Example

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

public class Main {
    static class SumTask extends RecursiveTask<Long> {
        private static final int THRESHOLD = 5_000;        // below this, just do the work
        private final long[] data;
        private final int from, to;

        SumTask(long[] data, int from, int to) { this.data = data; 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 += data[i];
                return sum;
            }
            int mid = (from + to) >>> 1;
            SumTask left = new SumTask(data, from, mid);
            left.fork();                                        // queued, an idle worker may steal it
            long right = new SumTask(data, mid, to).compute();  // do one half yourself
            return right + left.join();                         // then wait for the other half
        }
    }

    public static void main(String[] args) {
        long[] data = new long[100_000];
        for (int i = 0; i < data.length; i++) data[i] = i + 1;

        ForkJoinPool pool = ForkJoinPool.commonPool();
        long total = pool.invoke(new SumTask(data, 0, data.length));

        System.out.println("sum         : " + total);
        System.out.println("expected    : " + (100_000L * 100_001L / 2));
        System.out.println("parallelism : " + pool.getParallelism());
        System.out.println("steals      : " + pool.getStealCount() + " (idle workers took queued halves)");
    }
}

Split until small, compute one half yourself, join the rest.