ForkJoin Framework in Java

Introduction

Java introduced the ForkJoin Framework in Java 7 as part of the java.util.concurrent package to facilitate parallel processing and improve the performance of multi-core systems. It provides a powerful mechanism to execute tasks recursively by dividing them into smaller subtasks and then merging the results.

In this blog, we will explore the ForkJoin Framework, understand its working, and see how it can be effectively used with practical examples.

What is the ForkJoin Framework?

The ForkJoin Framework is designed for parallel execution of tasks using a divide-and-conquer approach. It splits large tasks into multiple smaller tasks, executes them concurrently, and then combines the results to produce the final output.

Key Components of ForkJoin Framework

The framework consists of two main classes:

ForkJoinPool: A special thread pool that manages and executes ForkJoinTask instances.
ForkJoinTask: An abstract class that represents a computation task that can be split into smaller subtasks.

ForkJoinTask has two subclasses:

RecursiveTask: Used for tasks that return a result.
RecursiveAction: Used for tasks that do not return a result.

How the ForkJoin Framework Works

The ForkJoin Framework follows a work-stealing algorithm, where idle threads in the pool can "steal" tasks from busy threads to maximize CPU utilization.

Basic Steps:

A large task is divided into smaller subtasks.
Each subtask is processed independently.
If a subtask is too large, it is further split and executed recursively.
The results of all subtasks are merged to obtain the final result.

Example: Using ForkJoin Framework

Example 1: Sum of an Array using ForkJoinTask

Below is an example demonstrating how to compute the sum of an array using RecursiveTask.

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

class SumTask extends RecursiveTask<Integer> {
    private static final int THRESHOLD = 5; // Threshold for splitting
    private int[] arr;
    private int start, end;

    public SumTask(int[] arr, int start, int end) {
        this.arr = arr;
        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 += arr[i];
            }
            return sum;
        } else {
            int mid = (start + end) / 2;
            SumTask leftTask = new SumTask(arr, start, mid);
            SumTask rightTask = new SumTask(arr, mid, end);
            leftTask.fork(); // Fork left task
            int rightResult = rightTask.compute(); // Compute right task
            int leftResult = leftTask.join(); // Join left task
            return leftResult + rightResult;
        }
    }
}

public class ForkJoinExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        ForkJoinPool pool = new ForkJoinPool();
        SumTask task = new SumTask(arr, 0, arr.length);
        int sum = pool.invoke(task);
        System.out.println("Sum of array: " + sum);
    }
}

Explanation:

If the task size is below a defined THRESHOLD, it computes directly.
If it is larger, it is split into two subtasks recursively.
The fork() method starts a new thread for left task execution.
The join() method waits for the left task result while executing the right task synchronously.

Example 2: Using RecursiveAction

If the task does not return a value, we use RecursiveAction. Below is an example where an array is modified using ForkJoin.

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

class IncrementTask extends RecursiveAction {
    private static final int THRESHOLD = 5;
    private int[] arr;
    private int start, end;

    public IncrementTask(int[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if (end - start <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                arr[i] += 1;
            }
        } else {
            int mid = (start + end) / 2;
            IncrementTask leftTask = new IncrementTask(arr, start, mid);
            IncrementTask rightTask = new IncrementTask(arr, mid, end);
            invokeAll(leftTask, rightTask);
        }
    }
}

public class ForkJoinActionExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        ForkJoinPool pool = new ForkJoinPool();
        IncrementTask task = new IncrementTask(arr, 0, arr.length);
        pool.invoke(task);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Explanation:

This example increments each element of an array.
The task is recursively divided until the threshold is met.
The invokeAll() method runs both tasks concurrently.

Advantages of ForkJoin Framework

Parallel Execution: Maximizes CPU usage using multiple threads.
Work Stealing: Idle threads pick pending tasks, improving efficiency.
Better Performance: Useful for large computational tasks.
Automatic Load Balancing: No need for explicit thread management.

When to Use ForkJoin Framework?

When dealing with recursive tasks like sorting and searching.
When the problem can be broken down into independent subtasks.
When tasks require parallel execution for better performance.

Conclusion

The ForkJoin Framework in Java provides an efficient way to implement parallel processing using divide-and-conquer techniques. By leveraging ForkJoinPool, RecursiveTask, and RecursiveAction, developers can efficiently distribute workload across multiple CPU cores, resulting in improved performance.

It is particularly useful for handling large datasets, parallel computations, and CPU-intensive tasks in modern Java applications.