Java Fork-Join pool

The purpose of a Fork-Join Pool in Java is to provide a framework for parallelism and concurrent execution of tasks, especially for parallelizing CPU-bound tasks that can be divided into smaller subtasks.

In a Fork-Join Pool, each worker thread is responsible for a subset of tasks, and these subtasks are stored in double-ended queues (dequeues). Each worker thread retrieves subtasks from its dequeue and executes them.

Key purposes and benefits

1. Fork-Join Pools allow you to break down a larger task into smaller subtasks that can be executed concurrently. This is particularly valuable for tasks that can be divided into independent parts, such as recursive algorithms, matrix multiplication, sorting, and searching.
2. This framework is well-suited for tasks that follow a recursive structure. A task is divided into smaller tasks until it reaches the base case, at which point the results are computed.
3. Improved Performance: Parallel execution on multi-core processors can yield significant performance improvements, especially for compute-intensive tasks.
4. Work Stealing: Fork-Join Pools employ work-stealing algorithms, enabling idle threads to ‘steal’ tasks from other threads’ task queues when they have completed their own work.
5. Efficient Load Balancing: This work-stealing mechanism ensures efficient load balancing because idle worker threads can always find tasks to execute, even if other threads are busy. It prevents some threads from being overloaded while others remain idle.

ForkJoinPools can be used to execute independent tasks in parallel. You can submit a Runnable or a Callable object and run it in a new thread. However, an implementation of ExecutorService can also be used for this purpose.

ForkJoinPool is not a replacement for Java’s ExecutorService. It is an addition to the capabilities of the java.util.concurrent package.

What types of tasks can be executed in a Fork-Join Pool? In addition to Callable and Runnable, you can submit two other types of classes to a Fork-Join Pool: RecursiveAction and RecursiveTask.

Example

Retrieve the count of occurrences of a specific integer in a given array using Fork-Join Pool.

package com.gathi.porkjoin;

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

public class SearchTask extends RecursiveTask<Integer> {

 private int[] arr;
 private int start;
 private int end;
 private int element;
 private int chunkSize = 100;
 ForkJoinPool pool = ForkJoinPool.commonPool();
 
 public SearchTask(int [] arr, int element) {
  this.arr = arr;
  this.start = 0;
  this.end = arr.length;
  this.element = element;
 }
 
 public SearchTask(int [] arr, int start, int end, int element) {
  this.arr = arr;
  this.start = start;
  this.end = end;
  this.element = element;
 }
 
 @Override
 protected Integer compute() {
  
  int length = end - start;
  
  int occurance = 0;
  if (length <= chunkSize) {
   for (int i=start; i<end; i++) {
    if (arr[i] == element) {
     occurance++;
    }
   }
   return occurance;
  }
  
  int mid = start + length / 2;
        SearchTask taskFirst = new SearchTask(arr, start, mid, element);
        SearchTask taskSecond = new SearchTask(arr, mid, end, element);

        taskFirst.fork();
        int resultSecond = taskSecond.compute();
  
  return taskFirst.join() + resultSecond;
 }
}

ForkJoinPool pool = ForkJoinPool.commonPool();
  
  int [] arr = {...};
  
  SearchTask searchTask = new SearchTask(arr, 4);
  
  //this is a synchronous or blocking call. Calling thread waits until
  //it returns a value
  int x = pool.invoke(searchTask);
  System.out.println(x);

Explanation

A thread from the ForkJoinPool (let’s call it thread1) picks up the searchTask and invokes the compute method on it. The taskFirst.fork() method creates a new task and submits it to thread1's deque. Thread1 continues to execute the taskSecond.compute method in a recursive manner. Eventually, it waits for the completion of taskSecond.

At this point, either thread1 or another thread (let’s call it thread2) from the pool can pick up taskSecond from thread1's deque and execute the task.

As you can see, if the input array size is large, tasks are continuously added to the deque of each thread. Any available thread can pick up a task from another thread’s deque and execute it. This is called task stealing.

Work-stealing is a fundamental feature of Fork-Join Pools, and it helps ensure that the pool’s worker threads are kept busy, resulting in better utilization of available CPU cores and more efficient parallel execution of tasks. This dynamic load balancing contributes to the overall performance improvement in multi-threaded applications.