Fork/Join Framework in Java | RecursiveTask, RecursiveAction

Fork/Join allows us to divide the task into smaller pieces and combine the results. It uses Work-stealing algorithm. If more than one thread is working at the same time, and one thread completes its job while the other thread remains busy, the completed thread steals the tasks from the busy thread and begins working on them.

The basic purpose of using Fork/Join is to improve application performance by taking use of multiple processors. You’ve probably heard of the “divide and conquer” strategy. The Fork/Join system operates similarly.

Let’s understand the basics about Fork and Join. What is Fork and What is Join with some small example.

Table of Contents

What is Fork in Java?

In Java, Fork is the process of dividing a work into smaller tasks that are also independent of one another. These tasks can also be performed in parallel.

What is Join in Java?

The Join idea is used when a work is separated into smaller pieces and executed in parallel. Once all subtasks have completed their execution, the join process joins all the results; otherwise, the join will continue to wait.

Pseudocode of Fork/Join

There are a few things to think about. If your work is really small, you should not split it. It should be carried out immediately. If you work is larger, you should break it down into smaller chunks.

if (smaller work)
  do not split
else
  split work into pieces
  wait for the results

ForkJoinPool

Fork/Join is a framework that implements the ExecutorService interface. ForkJoinPool is the core of the this framework. ForkJoinPool implements the core work-stealing mechanism.

In case of ForkJoinPool, there is no separate thread for each sub-task. The task is stored in its own deque for ForkJoinPool.

Implementation of Fork/Join by extending RecursiveTask

A task can return a value if you use a RecursiveTask.

Syntax of RecursiveTask in Fork/Join


pubilc class RecursiveTaskDemo extends RecursiveTask {

   @Override
   protected Long compute() { 
		return null; 
   }
}

Example of RecursiveTask in Fork/Join


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

public class RecursiveTaskExample extends RecursiveTask {

	private long[] array;
	private int startIndex;
	private int length;

	public RecursiveTaskExample(int startIndex, int length, long[] array) {
		this.startIndex = startIndex;
		this.length = length;
		this.array = array;
	}

	@Override
	protected Long compute() {
		int processingSizeMin = 100;
		long total = 0;
		if (length - startIndex < processingSizeMin) {
			for (int i = startIndex; i < length; i++) {
				total += array[i];
			}
		} else {
			int mid = (startIndex + length) / 2;
			RecursiveTaskExample recursiveTask1 = new RecursiveTaskExample(startIndex, mid, array);
			RecursiveTaskExample recursiveTask2 = new RecursiveTaskExample(mid, length, array);
			recursiveTask1.fork();
			recursiveTask2.fork();

			total = recursiveTask1.join() + recursiveTask2.join();
		}

		return total;
	}

	public static void main(String[] args) {

		final int maxSize = 10000;
		ForkJoinPool forkJoinPool = new ForkJoinPool();
		long[] array = new long[maxSize];
		for (int i = 0; i < maxSize; i++) {
			array[i] = i;
		}
		RecursiveTaskExample recursiveTask = new RecursiveTaskExample(0, array.length, array);
		long total = forkJoinPool.invoke(recursiveTask);
		System.out.println("Sum of elements = " + total);
	}
}

Output:
Sum of elements = 49995000

Implementation of Fork/Join by extending RecursiveAction

A task doesn’t return a value if you use a RecursiveAction.

Syntax of RecursiveAction in Fork/Join


public class RecursiveActionDemo extends RecursiveAction {
   
   @Override
   protected void compute() {
	// Your code here
   }
}

Example of RecursiveAction in Fork/Join


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

public class RecursiveActionExample extends RecursiveAction {

	long[] array;
	int startIndex;
	int length;

	public RecursiveActionExample(int startIndex, int length, long[] array) {
		this.startIndex = startIndex;
		this.length = length;
		this.array = array;
	}

	@Override
	protected void compute() {

		int processingSizeMin = 100;
		if (length - startIndex < processingSizeMin) {
			for (int i = startIndex; i < length; i++) {
				array[i] = array[i] * array[i];
			}
		} else {
			int middleValue = (startIndex + length) / 2;
			invokeAll(new RecursiveActionExample(startIndex, middleValue, array),
					new RecursiveActionExample(middleValue, length, array));
		}
	}

	public static void main(String[] args) {

		final int maxLength = 100000;
		ForkJoinPool joinPool = new ForkJoinPool();
		long[] inputArray = new long[maxLength];
		for (int i = 0; i < maxLength; i++) {
			inputArray[i] = i;
		}
		RecursiveActionExample recursiveActionExample = new RecursiveActionExample(0, inputArray.length, inputArray);
		joinPool.invoke(recursiveActionExample);
		System.out.println("Parallelism Level > " + joinPool.getParallelism());

	}
}

Output:
Parallelism Level > 4

Difference between RecursiveAction and RecursiveTask in java

#	RecursiveTask	RecursiveAction
1	The method of this class returns a value if you submit the task using RecursiveTask.	But the method of this class doesn’t return any value in case of RecursiveAction.
2	protected abstract V compute(); You can change the return type as per your requirement.	protected abstract void compute() The return type is void.