The Fork/Join Framework in Java 7 is designed for work that can be broken down into smaller tasks and the results of those tasks combined to produce the final result. In general, classes that use the Fork/Join Framework follow the following simple algorithm:
// pseudocode
Result solve(Problem problem) {
if (problem.size < SEQUENTIAL_THRESHOLD)
return solveSequentially(problem);
else {
Result left, right;
INVOKE-IN-PARALLEL {
left = solve(extractLeftHalf(problem));
right = solve(extractRightHalf(problem));
}
return combine(left, right);
}
}In order to demonstrate this, I have created an example to find the maximum number from a large array using fork/join:
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public class MaximumFinder extends RecursiveTask<Integer> {
private static final int SEQUENTIAL_THRESHOLD = 5;
private final int[] data;
private final int start;
private final int end;
public MaximumFinder(int[] data, int start, int end) {
this.data = data;
this.start = start;
this.end = end;
}
public MaximumFinder(int[] data) {
this(data, 0, data.length);
}
@Override
protected Integer compute() {
final int length = end - start;
if (length < SEQUENTIAL_THRESHOLD) {
return computeDirectly();
}
final int split = length / 2;
final MaximumFinder left = new MaximumFinder(data, start, start + split);
left.fork();
final MaximumFinder right = new MaximumFinder(data, start + split, end);
return Math.max(right.compute(), left.join());
}
private Integer computeDirectly() {
System.out.println(Thread.currentThread() + ' computing: ' + start
+ ' to ' + end);
int max = Integer.MIN_VALUE;
for (int i = start; i < end; i++) {
if (data[i] > max) {
max = data[i];
}
}
return max;
}
public static void main(String[] args) {
// create a random data set
final int[] data = new int[1000];
final Random random = new Random();
for (int i = 0; i < data.length; i++) {
data[i] = random.nextInt(100);
}
// submit the task to the pool
final ForkJoinPool pool = new ForkJoinPool(4);
final MaximumFinder finder = new MaximumFinder(data);
System.out.println(pool.invoke(finder));
}
}The MaximumFinder class is a RecursiveTask which is responsible for finding the maximum number from an array. If the size of the array is less than a threshold (5) then find the maximum directly, by iterating over the array. Otherwise, split the array into two halves, recurse on each half and wait for them to complete (join). Once we have the result of each half, we can find the maximum of the two and return it.
Reference: Java 7: Fork/Join Framework Example from our JCG partner Fahd Shariff at the fahd.blog blog.
In the compute api, instead of calling compute() api directly on right, we can fork it like below: @Override protected Integer compute() { final int length = end – start; if ( length < SEQUENTIAL_THRESHOLD ) { return computeDirectly(); } final int split = length / 2; final MaximumFinder left = new MaximumFinder( data, start, start + split ); left.fork(); final MaximumFinder right = new MaximumFinder( data, start + split, end ); // return max( right.compute(), left.join() ); // either we can return by calling right.compute(), else call right.fork, and then call max // on right.join and left.join right.fork(); return… Read more »
thanks for your post but i observed following things main purpose of fork/join is to improve performance by running task in parallel, but what i observed that time taken by sequential processing is always better than fork join processing. //code MaximumFinder finderSeq=new MaximumFinder(data); long startTimeSeq=System.nanoTime(); Integer maxValueSeq=finderSeq.computeDirectly(); long endTimeSeq=System.nanoTime(); System.out.println(“Seq Time For execution “+(endTimeSeq-startTimeSeq)+” max value “+maxValueSeq); // submit the task to the pool final ForkJoinPool pool = new ForkJoinPool(4); final MaximumFinder finder = new MaximumFinder(data); long startTimeParallel=System.nanoTime(); Integer maxValueParallel=pool.invoke(finder); long endTimeParallel=System.nanoTime(); System.out.println(“Parallel Time For execution “+(endTimeParallel-startTimeParallel)+” maxValueParallel “+maxValueParallel); //—————– Seq Time For execution 5037392 max value 99 Parallel Time… Read more »
For the guy that mentions the time is the same in sequence and parallel processing:
I’d like to see you implementation, I’ve run many times this example vs a sequential one and my results are:
ARRAY SIZE:1,000,000
max value [99] obtained in 196 millis
seq max value [99] obtained in 6 millis
My guess is that takes more time in parallel due to creation of new instances of MaximumFinder