Use the Fork/Join Framework to Sum an Array in Java
Problem
The Fork/Join framework runs divide-and-conquer tasks in parallel: a task splits itself into subtasks (fork) and combines their results (join).
Sum the numbers 1 to 100,000 stored in an array by splitting the work recursively across threads.
Java Program
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public class ForkJoinSum {
static class SumTask extends RecursiveTask<Long> {
private static final int THRESHOLD = 1_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) { // small enough: just add it up
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);
SumTask right = new SumTask(data, mid, to);
left.fork(); // run the left half asynchronously
return right.compute() + left.join(); // compute the right half here, then combine
}
}
public static void main(String[] args) {
int[] data = new int[100_000];
for (int i = 0; i < data.length; i++) data[i] = i + 1;
long total = ForkJoinPool.commonPool().invoke(new SumTask(data, 0, data.length));
System.out.println("Sum of 1..100000 = " + total);
System.out.println("Formula check = " + 100_000L * 100_001 / 2);
}
}Output
Core Logic
Each task either sums a small slice directly or splits itself in two, so the work spreads across the pool's threads.
- 1
SumTaskextendsRecursiveTask<Long>, whosecompute()returns a result. - 2Slices of 1,000 elements or fewer are summed with a plain loop.
- 3Larger slices create two subtasks: the left is
fork()ed to run asynchronously, the right is computed in the current thread. - 4
left.join()waits for the left half, and the two sums are added.
Key Point: Computing one half directly instead of forking both halves keeps the current thread busy instead of making it wait.
Why: Every element is added once overall; the recursion depth of task splitting grows logarithmically.
Key Concepts
Approach 2: Finding the Maximum with Fork/Join
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public class ForkJoinMax {
static class MaxTask extends RecursiveTask<Integer> {
private final int[] data;
private final int from, to;
MaxTask(int[] data, int from, int to) {
this.data = data;
this.from = from;
this.to = to;
}
@Override
protected Integer compute() {
if (to - from <= 500) {
int max = Integer.MIN_VALUE;
for (int i = from; i < to; i++) max = Math.max(max, data[i]);
return max;
}
int mid = (from + to) >>> 1;
MaxTask left = new MaxTask(data, from, mid);
left.fork();
int rightMax = new MaxTask(data, mid, to).compute();
return Math.max(rightMax, left.join());
}
}
public static void main(String[] args) {
int[] data = new int[50_000];
for (int i = 0; i < data.length; i++) data[i] = (int) ((i * 7919L) % 100_003); // spread-out values
int max = new ForkJoinPool(4).invoke(new MaxTask(data, 0, data.length));
System.out.println("Maximum value: " + max);
}
}
Output
Core Logic
Any operation that combines two halves — like taking the larger of two maximums — fits the same fork/join pattern.
- 1Small slices find their maximum with a loop.
- 2Larger slices split, fork the left half and compute the right half.
- 3The task returns
Math.maxof the two halves. - 4A custom
ForkJoinPool(4)limits the work to four threads.
Key Point: The combining operation must be associative — sum, max and min work; something like "first element" needs care.
Why: Each element is compared once, with logarithmic splitting depth.
Key Concepts
Interview Questions
What is work stealing?
Idle threads in a ForkJoinPool take queued subtasks from busy threads' queues, which keeps all cores busy without central coordination.
How do you choose the threshold?
Large enough that splitting overhead doesn't dominate, small enough to create enough tasks to keep every core busy — typically thousands of simple operations per task.