Fork Join framework

1. Overview

The fork/join framework was presented in Java 7. It provides tools to help speed up parallel processing by attempting to use all available processor cores – which is accomplished through a divide and conquer approach.

In practice, this means that the framework first “forks”, recursively breaking the task into smaller independent subtasks until they are simple enough to be executed asynchronously.

2. Description

2.1 Intuition

This framework helps to make an algorithm parallel. These fork-join framework helps to make an algorithm parallel and we don't have to bother about low-level synchronizations or lock because the framework is going to do everything. It is like a divide and conquers algorithm that we have a larger task and it can be divided into smaller tasks Plus the sub solutions can be combined in order to end up with the final resolved. The important thing is subtasks have to be independent in order to be executed in parallel. Parallel merge sort or parallel maximum finding is going to be a good example.

2.1.1 Fork

fork split the given task into smaller subtasks that can be executed in a parallel manner

2.1.2 Join

The split tasks are being executed and after all of them are finished they are merged into one result.

2.2 RecursiveTask<T>

It's generic and returns a T type. All the tasks we want to execute in parallel is a subclass of this class. We have to override the computer method that will return the solution of the subproblem.

2.3 RecursiveAction

It is a task but without any return value

2.4 ForkJoinPool

Basically it is a thread pool for executing fork-join tasks. ForkJoinPool usually creates a fixed number of threads which is the number of CPU cores.

2.4.1 Work-stealing

A task is not equivalent to a thread. Tasks are lightweight threads. So fork-join will be efficient even when there are a huge number of tasks. These threads are executing the tasks but if a thread has no task then it can steal a task from more busy threads.

3. Example

3.1 Simple RecursiveAction

public class SimpleRecursiveActionDemo extends RecursiveAction {
    private int simulateWork;

    public static void main(String[] args) {
        // So what does it mean that we are going to create a full join pool and basically this fall join pool
        // is going to contain as many threads as the number of available processors.
        ForkJoinPool pool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());
//        SimpleRecursiveActionDemo simpleRecursiveActionDemo = new SimpleRecursiveActionDemo(20);
        SimpleRecursiveActionDemo simpleRecursiveActionDemo = new SimpleRecursiveActionDemo(1000000000);
        pool.invoke(simpleRecursiveActionDemo);
    }

    public SimpleRecursiveActionDemo(int simulateWork) {
        this.simulateWork = simulateWork;
    }

    // this method computed in parallel manner
    @Override
    protected void compute() {
        if(simulateWork > 100) {
            System.out.println("Parallel execution and split task... " + simulateWork);
            SimpleRecursiveActionDemo simpleRecursiveActionDemo1 = new SimpleRecursiveActionDemo(simulateWork/2);
            SimpleRecursiveActionDemo simpleRecursiveActionDemo2 = new SimpleRecursiveActionDemo(simulateWork/2);
            // So we are going to create a fork join pool and basically when we call this fork then these are recursive
            // actions so the recursiveActionDemo1 and recursiveActionDemo2 is going to be inserted into that given pool.
            // This fork is going to make sure that their tasks are going to be executed synchronously.
            simpleRecursiveActionDemo1.fork();
            simpleRecursiveActionDemo2.fork();
        } else {
            // work is not that great. So no need to fork-join algorithms
            System.out.println("No need for parallel execution. sequential algorithm is Ok " + simulateWork);
        }
    }
}

3.2 Simple RecursiveTask

public class RecursiveTaskDemo extends RecursiveTask<Integer> {
    private int simpleWork;

    public RecursiveTaskDemo(int simpleWork) {
        this.simpleWork = simpleWork;
    }

    public static void main(String[] args) {
        ForkJoinPool pool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());
//        RecursiveTaskDemo task = new RecursiveTaskDemo(20);
        RecursiveTaskDemo task = new RecursiveTaskDemo(10000000);
        System.out.println(pool.invoke(task));
    }

    @Override
    protected Integer compute() {
        if(simpleWork > 100) {
            System.out.println("Parallel execution needed because of the huge work... " + simpleWork);
            RecursiveTaskDemo task1 = new RecursiveTaskDemo(simpleWork/2);
            RecursiveTaskDemo task2 = new RecursiveTaskDemo(simpleWork/2);

            task1.fork();
            task2.fork();

            int solution = 0;
            solution += task1.join();
            solution += task2.join();

            return solution;
        } else {
            System.out.println("No need for parallel execution...");
            return 2*simpleWork;
        }
    }
}

4. Reference

https://www.oracle.com/technical-resources/articles/java/fork-join.html

https://www.baeldung.com/java-fork-join

https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html

https://mkyong.com/java/java-fork-join-framework-examples/

https://www.tutorialspoint.com/java_concurrency/concurrency_fork_join.htm

https://www.javacodegeeks.com/2015/09/forkjoin-framework.html