In this example we shall show you how to make use of Java RecursiveTask class, RecursiveTask provides a convenient way to consolidate results from subtasks. Java 7 introduced another implementation of ExecutorService: the ForkJoinPool class.
ForkJoinPool is designed for handling tasks efficiently that can be repeatedly broken down into subtasks, using the RecursiveAction class (when the task produces no result) or the RecursiveTask class (when the task has a result of type T) for tasks.
According to the divide and conquer paradigm, we divide the main problem of large size into smaller problems of same type, find solutions for these smaller problems, and then the solution for the large problem is obtained from the solutions of smaller sized problems.
Let’s see a simple example to understand how to use a RecursiveTask to find the maximum in a large array of unsorted numbers.
Example:
In a sequential execution using single threaded solution, we can iterate over the complete array to find the maximum. However, in a parallel execution using the divide and conquer paradigm, we recursively split the array into two halves (left and right) until the split array size is of certain smaller size. We use a linear maximum search in that smaller sized array and return the result. At each higher level, the results of the left and right halves are compared and the maximum is returned.
MaxNumberCalculator.java:
The MaxNumberCalculator is an implementation of a RecursiveTask where it executes its computation in the compute method. The maximum is computed in the task’s compute method itself only if the array size is less than the task size THRESHOLD. Otherwise the array is split into two halves and each half is resubmitted as child task by making a fork() call and then the current task waits for results from its two halves by calling join().
package com.jcg;
import java.util.concurrent.RecursiveTask;
/**
* @author ashraf
*
*/
@SuppressWarnings("serial")
public class MaxNumberCalculator extends RecursiveTask {
public static final int THRESHOLD = 5;
private int[] numbers;
private int start;
private int end;
public MaxNumberCalculator(int[] numbers) {
this(numbers, 0, numbers.length);
}
public MaxNumberCalculator(int[] numbers, int start, int end) {
this.numbers = numbers;
this.start = start;
this.end = end;
}
@Override
public Integer compute() {
int length = end - start;
int max = 0;
if (length < THRESHOLD) {
for (int x = start; x < end; x++) {
max = numbers[x];
}
}
return max;
} else {
int split = length / 2;
MaxNumberCalculator left = new MaxNumberCalculator(numbers, start,
start + split);
left.fork();
MaxNumberCalculator right = new MaxNumberCalculator(numbers, start
+ split, end);
return Math.max(right.compute(), left.join());
}
}
}
Tip
For an effective use of ForkJoinPool, the task should avoid using any synchronized methods or blocks in its compute method and also avoid using blocking I/O.
RecursiveTaskDemo.java:
RecursiveTaskDemo generates an array of 100000000 random integers, then it performs the sequential execution to find the maximum number in the generated array, After that this array is submitted to the ForkJoinPool by calling the invoke(task) method on the main task to perform the parallel execution.
package com.jcg;
import java.util.concurrent.ForkJoinPool;
/**
* @author ashraf
*
*/
public class RecursiveTaskDemo {
private static final int SIZE = 100000000;;
/**
* @param args
*/
public static void main(String[] args) {
final int[] numbers = new int[SIZE];
int maxNum = 0;
// Start sequential calculation
long st = System.currentTimeMillis();
for (int i = 0; i < SIZE; i++) {
numbers[i] = (int) (Math.random() * 10000);
if (numbers[i] > maxNum) {
maxNum = numbers[i];
}
}
System.out.println("Calculated maximum number (sequential execution): "
+ maxNum + " -- Total time: "
+ (System.currentTimeMillis() - st));
// Start parallel calculation
long pt = System.currentTimeMillis();
ForkJoinPool pool = new ForkJoinPool(4);
MaxNumberCalculator fbn = new MaxNumberCalculator(numbers);
System.out.println("Calculated maximum number (parallel execution): "
+ pool.invoke(fbn) + " -- Total time: "
+ (System.currentTimeMillis() - pt));
}
}
Output:
As we can see that there is a significant difference in time between sequential and parallel executions, the parallel one takes almost 25% of the sequential time to finish the calculation.
Calculated maximum number (sequential execution): 9999 -- Total time: 2352 Calculated maximum number (parallel execution): 9999 -- Total time: 693
Download the Source Code of this example:
This was an example of Java Concurrency RecursiveTask.
You can download the full source code of this example here: RecursiveTaskExampleCode.zip
numbers[i] = (
int
) (Math.random() *
10000
);
I think the above line is contributing to the sequential method taking too much time in comparison to the parallel method.