ForkJoinPool in Java is a part of the java.util.concurrent package and is designed to efficiently execute recursive tasks using a work-stealing algorithm. It works particularly well for problems that can be split into smaller subproblems and then combined to form the final result, adhering to the divide-and-conquer paradigm.
Here’s how you can use ForkJoinPool for recursive tasks:
1. Define Recursive Behavior with RecursiveTask/RecursiveAction
The main entities to use with ForkJoinPool are:
RecursiveTask<T>: Returns a result.RecursiveAction: Performs an action without returning a result.
You define the recursive logic within these classes by overriding the compute() method.
2. Implement Recursive Splitting
- A base case is defined where small tasks are computed directly.
- For larger tasks, the work is split into subtasks, and
fork()is invoked to execute them asynchronously. Results are aggregated usingjoin().
3. Run Tasks in a ForkJoinPool
The tasks are submitted to a ForkJoinPool. This pool can manage multiple tasks simultaneously and perform work-stealing to optimize performance.
Example: Parallel Sum Using RecursiveTask
package org.kodejava.util.concurrent;
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;
// RecursiveTask to calculate the sum of an array
class ParallelSumTask extends RecursiveTask<Long> {
private static final int THRESHOLD = 10; // Splitting threshold
private final int[] arr;
private final int start, end;
public ParallelSumTask(int[] arr, int start, int end) {
this.arr = arr;
this.start = start;
this.end = end;
}
@Override
protected Long compute() {
int length = end - start;
// Base case: if below a threshold, compute directly
if (length <= THRESHOLD) {
long sum = 0;
for (int i = start; i < end; i++) {
sum += arr[i];
}
return sum;
}
// Recursive splitting
int mid = start + length / 2;
ParallelSumTask leftTask = new ParallelSumTask(arr, start, mid);
ParallelSumTask rightTask = new ParallelSumTask(arr, mid, end);
leftTask.fork(); // Fork the left task
long rightResult = rightTask.compute(); // Compute the right task
long leftResult = leftTask.join(); // Wait for the left task
return leftResult + rightResult; // Combine results
}
}
public class ForkJoinExample {
public static void main(String[] args) {
int[] numbers = new int[100];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = i + 1; // Fill the array with 1 to 100
}
ForkJoinPool pool = new ForkJoinPool(); // Create ForkJoinPool
ParallelSumTask task = new ParallelSumTask(numbers, 0, numbers.length);
long result = pool.invoke(task); // Start the task and get the result
System.out.println("Sum: " + result);
}
}
Key Methods in ForkJoinTask
fork(): Asynchronously executes the task in the pool.join(): Waits for the task to finish and retrieves its result.invoke(): A shortcut forfork()+join().compute(): Defines the logic for splitting and computation of tasks.
Advantages of ForkJoinPool
- Work-Stealing Algorithm: Idle threads steal tasks from busy threads, ensuring an even workload distribution.
- Efficient for Recursive Tasks: Particularly suited for algorithms like QuickSort, MergeSort, and calculations like Fibonacci or array sums.
- Dynamic Thread Management:
ForkJoinPoolmanages the number of threads for optimal utilization based on available cores.
When to Use
- Large, recursive tasks with problems that are computationally expensive.
- Divide-and-conquer problems where each subproblem is independent after splitting.
Things to Consider
- Splitting Threshold: Choosing a suitable threshold is crucial for balancing computation and task overhead.
- Thread Contention: Ensure your tasks do not rely on a shared mutable state to avoid contention between threads.