Fork/Join Framework in Java

In this article, we will understand how the Fork/Join Framework works, explore its core classes such as ForkJoinPool, RecursiveTask, and RecursiveAction, and learn how to build scalable parallel algorithms in Java.

Why Not Use ExecutorService?

The ExecutorService framework is an excellent choice for executing independent tasks such as handling HTTP requests, processing messages, or running background jobs. Each submitted task is generally unrelated to the others and can execute independently.

Consider an application that must process one thousand customer orders. Each order can be submitted as a separate task to an ExecutorService because the processing of one order does not depend on any other.

However, divide-and-conquer algorithms are fundamentally different. Instead of executing independent tasks, they repeatedly split one large computation into smaller subtasks until the work becomes sufficiently small to execute efficiently.

For example, sorting a large array involves repeatedly dividing the array into smaller parts, sorting each part independently, and finally merging the sorted results.

Implementing this recursive decomposition manually using an ExecutorService requires creating, submitting, coordinating, and combining numerous subtasks, making the code unnecessarily complex.

The Fork/Join Framework automates this entire process. Developers focus only on describing how to divide the problem and combine the results, while the framework efficiently schedules the subtasks across available CPU cores.

What is Divide-and-Conquer?

The Fork/Join Framework is based on the divide-and-conquer algorithmic strategy.

Instead of solving a large problem directly, the computation is recursively divided into smaller, more manageable subtasks. Each subtask is processed independently, often in parallel, and the partial results are then combined to produce the final solution.

The overall workflow is illustrated below.

      Large Problem
            │
            ▼
 Split into Smaller Tasks
            │
      ┌─────┴─────┐
      ▼           ▼
    Task A      Task B
      │           │
      ▼           ▼
   Results Combined
            │
            ▼
      Final Result

This recursive decomposition continues until each subtask becomes small enough to execute efficiently without further splitting.

Many well-known algorithms naturally follow this strategy, including Merge Sort, Quick Sort, matrix multiplication, image filtering, recursive directory traversal, and various scientific simulations.

Since the subtasks are largely independent, they can execute simultaneously on multiple processor cores, significantly reducing the overall execution time.

ForkJoinPool

The central component of the Fork/Join Framework is the ForkJoinPool. It manages a group of worker threads responsible for executing recursive tasks.

A pool can be created as follows.

ForkJoinPool pool = new ForkJoinPool();

The pool automatically creates an appropriate number of worker threads based on the available processor cores. Each worker repeatedly executes tasks until the entire computation is complete.

Instead of assigning every task to a shared queue, each worker thread maintains its own task queue.

This design minimizes contention between threads and forms the basis of the framework's highly efficient work-stealing algorithm.

The Common ForkJoinPool

Java provides a shared pool that can be reused throughout the application. The common pool is created lazily and shared by all components that use it.

ForkJoinPool commonPool = ForkJoinPool.commonPool();

The common pool is widely used throughout the JDK. For example, asynchronous methods of CompletableFuture, such as supplyAsync() and runAsync(), use this shared pool by default when no custom executor is supplied.

Using the common pool reduces thread creation overhead and allows multiple components of an application to share the same set of worker threads efficiently.

Work-Stealing Algorithm

One of the most important innovations of the Fork/Join Framework is its work-stealing scheduler.

Instead of maintaining a single shared queue, each worker thread owns its own double-ended queue (deque) containing tasks that it must execute.

Suppose Worker A still has several pending tasks while Worker B has already completed all of its assigned work.

          Worker A                  Worker B
             │                         │
   ┌─────────┼─────────┐               │
   ▼         ▼         ▼               ▼
 Task 1    Task 2    Task 3        No Tasks

Without work stealing, Worker B would remain idle while Worker A continued processing every remaining task. This results in poor CPU utilization.

Instead, the Fork/Join Framework allows idle workers to steal tasks from busy workers.

          Worker A                  Worker B
             │                         │
      ┌──────┴──────┐                  │
      ▼             ▼                  ▼
    Task 1        Task 2            Task 3

Both workers now execute tasks simultaneously, improving load balancing and maximizing processor utilization.

This process occurs automatically without any intervention from the developer.

As worker threads finish their own queues, they continuously search for additional work by stealing tasks from other workers, ensuring that CPU cores remain busy whenever possible.

RecursiveTask

The Fork/Join Framework represents each unit of work as a task. When a parallel computation needs to return a result, the framework provides the RecursiveTask class, where V represents the type of the computed result.

A RecursiveTask recursively divides a large problem into smaller subtasks until each subtask becomes small enough to execute efficiently. The partial results are then combined to produce the final answer.

A custom task is created by extending RecursiveTask and implementing its compute() method.

import java.util.concurrent.RecursiveTask;

class SumTask extends RecursiveTask<Integer> {
    @Override
    protected Integer compute() {
        return 0;
    }
}

The framework repeatedly invokes the compute() method while recursively processing subtasks.

The compute() method contains the entire divide-and-conquer algorithm. It decides whether the current task is small enough to execute directly or should be divided into smaller subtasks.

The general structure is:

protected Integer compute() {

    if (smallEnough()) {
        return computeDirectly();
    }

    splitTask();
    return combineResults();
}

Every Fork/Join algorithm follows this pattern. Small tasks execute sequentially, while larger tasks are recursively divided until they reach an appropriate size.

Choosing a Threshold

Recursive decomposition cannot continue indefinitely. Eventually, further splitting becomes more expensive than executing the computation directly.

For this reason, Fork/Join algorithms define a threshold, representing the smallest task size that should still be divided.

Suppose an application processes an array of one million elements.

      1,000,000 Elements
               │
               ▼
     Threshold = 10,000
               │
               ▼
Split Until Task Size ≤ 10,000

Once a subtask contains fewer than ten thousand elements, it executes sequentially instead of being divided further.

Selecting an appropriate threshold is important because excessively small tasks increase scheduling overhead, while excessively large tasks reduce opportunities for parallel execution.

Complete Example

The following example computes the sum of an integer array in parallel.

import java.util.concurrent.RecursiveTask;

class SumTask extends RecursiveTask<Integer> {
    private static final int THRESHOLD = 4;

    private final int[] array;
    private final int start;
    private final int end;

    SumTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Integer compute() {
        if (end - start <= THRESHOLD) {
            int sum = 0;

            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        }

        int mid = (start + end) / 2;

        SumTask left = new SumTask(array, start, mid);
        SumTask right = new SumTask(array, mid, end);

        left.fork();

        int rightResult = right.compute();
        int leftResult = left.join();

        return leftResult + rightResult;
    }
}

The task repeatedly divides the array into two halves until each portion contains no more than four elements. Each small portion computes its sum directly, after which the partial sums are combined to produce the final result.

Executing the Task

The task is submitted to a ForkJoinPool using the invoke() method.

import java.util.concurrent.ForkJoinPool;

public class Main {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8};
        ForkJoinPool pool = new ForkJoinPool();

        SumTask task = new SumTask(
                numbers,
                0,
                numbers.length
        );

        int result = pool.invoke(task);
        System.out.println(result);
    }
}

Output:

The framework automatically distributes subtasks across worker threads, allowing multiple sections of the array to be processed simultaneously.

RecursiveAction

Not every parallel computation produces a result. Some tasks simply perform work such as updating files, processing images, or printing output. For these situations, the Fork/Join Framework provides the RecursiveAction class.

Unlike RecursiveTask, a RecursiveAction does not return a value.

import java.util.concurrent.RecursiveAction;

class PrintTask extends RecursiveAction {
    @Override
    protected void compute() {

    }
}

Its compute() method performs the required work without returning a result.

Example

The following example prints array elements in parallel.

import java.util.concurrent.RecursiveAction;

class PrintTask extends RecursiveAction {
    private static final int THRESHOLD = 3;

    private final int[] array;
    private final int start;
    private final int end;

    PrintTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {

        if (end - start <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                System.out.println(array[i]);
            }
            return;
        }

        int mid = (start + end) / 2;
        invokeAll(
                new PrintTask(array, start, mid),
                new PrintTask(array, mid, end)
        );
    }
}

Since no result is produced, the task simply performs its work in parallel and terminates.

fork(), join() and invoke()

The Fork/Join Framework provides three fundamental operations for executing recursive tasks. The fork() method submits a subtask for asynchronous execution by another worker thread.

 left.fork();

The calling thread does not wait. It continues executing immediately. The join() method waits for a previously forked task to complete and returns its result.

 int result = left.join();

If the task has already finished, the result is returned immediately. Otherwise, the current thread waits until the computation completes.

The invoke() method submits a task to a ForkJoinPool and waits for its completion.

 int result = pool.invoke(task);

It combines task submission and waiting into a single operation and is typically used to start the initial computation.

invokeAll()

When a task needs to create multiple independent subtasks, invoking fork() on each subtask individually can make the code verbose.

The Fork/Join Framework provides the invokeAll() method as a convenient way to fork several subtasks simultaneously and schedule them for parallel execution.

For example, instead of writing:

left.fork();
right.fork();

left.join();
right.join();

the same operation can often be written more concisely as:

invokeAll(left, right);

The framework schedules both subtasks for execution, allowing them to run concurrently whenever worker threads are available.

This approach improves readability and is commonly used in RecursiveAction implementations where subtasks do not return values.

Although the Fork/Join Framework excels at CPU-bound computations, it is designed primarily for CPU-bound computations rather than blocking I/O operations.

For example, tasks involving database queries, REST API calls, file downloads, network communication, or other I/O-intensive operations should not be implemented using Fork/Join.

While a worker thread waits for an external resource, it cannot perform useful computation, reducing overall throughput and limiting the effectiveness of the work-stealing scheduler.

In such cases, an ExecutorService, virtual threads, or CompletableFuture is typically a better choice because these frameworks are designed to manage independent or asynchronous tasks that may block while waiting for external resources.

Conclusion

The Fork/Join Framework provides Java's high-performance solution for recursive divide-and-conquer algorithms on multicore processors.

By combining recursive task decomposition, work-stealing scheduling, and efficient load balancing, it enables CPU-intensive computations to scale across available processor cores with minimal developer effort.

While the Fork/Join Framework is ideal for computational workloads, ExecutorService is better suited for independent tasks, CompletableFuture excels at asynchronous workflows, and the Fork/Join Framework remains the preferred choice for recursive parallel algorithms.