Fork Join Thread Pool

In this article we will discuss ForkJoinPool and ForkJoinTask which is a high performance and parallel execution framework provided by Java. We will see different use cases of it and how it is different then ExecutorService.

In the last article we discussed the details of ExecutorService with multiple examples. With executor service, you can easily spawn multiple threads and assign Callable or Runnable tasks(I/O or CPU intensive task) to them and these threads can parallelly perform these tasks. These tasks are mostly independent tasks.

The concept of Fork Join Pool is also very similar to Executor service with one main difference and that is in terms of the task. We submit the kind of task in a form of Runnable or Callable which can be split(forked) into multiple sub-tasks(recursive tasks) and each thread in a fork-join pool can pick those sub-tasks and start performing it. Once these tasks are completed, the individual small task results are then joined to form a single result of a huge task. This is called a divide and conquer algorithm.

In this case, each thread maintains its individual Queue of tasks and picks a task from only one queue concurrently. This enables easy scheduling of the threads. The queue is basically a deQueue implementation and this is required for the implementation of work-stealing algorithm. A fork-join thread is also called a lightweight thread.

The work-stealing algorithm is like if one thread has completed all the tasks present in its own queue then it will pull the task from another thread queue from the rear side of it as it is a dequeue. This enables efficient processing when most tasks spawn other subtasks

Now, let us see some examples where we can use this Fork Join Pool. We can use it in every algorithm where recursion is involved such as Fibonacci series calculation, Merge Sort, Tree Traversals, etc.

Let us implement the solution of the Fibonacci series using Fork Join Pool.

Fibonacci Series Using Fork Join Pool

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

public class FibonacciDemo extends RecursiveTask {

    private volatile long number;

    public FibonacciDemo(long number) {
        this.number = number;
    }

    @Override
    protected Long compute() {
        long n = number;
        if (n <= 10) {
            number = fib(n);
        } else {
            FibonacciDemo f1 = new FibonacciDemo(n - 1);
            FibonacciDemo f2 = new FibonacciDemo(n - 2);
            ForkJoinTask.invokeAll(f1, f2);
            number = f1.number + f2.number;
        }
        return number;
    }

    private static long fib(long n) {
        if (n <= 1) return n;
        else return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        FibonacciDemo task = new FibonacciDemo(50);
        System.out.println(new ForkJoinPool().invoke(task));
    }
}