Google

May 16, 2014

Java 7 fork and join tutorial with a diagram and an example

Q. How does java.util.concurrent.RecursiveTask work?
A. It uses a single ForkJoin pool to execute tasks in parallel for both computing sum of numbers recursively and chunking (or breaking) them into chunks of say 3 or less as per the following example.

Here is an example, where a an array of given numbers are summed in parallel by multiple threads. The batch size is 3. So, each thread processes 3 or less numbers asynchronously (i.e. fork) and the join to compute the final results.


Example. numbers = {1,2,3,4,5,6,7,8,9,10}, sum = 55; process them using the fork and join feature introduced in Java 7.





Here is the code

package com.fork.join;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.RecursiveTask;

class SumTask extends RecursiveTask<Integer> {

 static final int CHUNK_SIZE = 3; // execution batch size;

 Integer[] numbers;
 int begin;
 int end;

 SumTask(Integer[] numbers, int begin, int end) {
  this.numbers = numbers;
  this.begin = begin;
  this.end = end;
 }

 @Override
 protected Integer compute() {
        //sums the given number
  if (end - begin <= CHUNK_SIZE) {
   int sum = 0;
   List<Integer> processedNumbers = new ArrayList<>();
   for(int i=begin; i < end; ++i) {
    processedNumbers.add(numbers[i]);//just to track
    sum += numbers[i];
   }

   //tracking thread, numbers processed, and sum
   System.out.println(Thread.currentThread().getName() + " proceesing " +
      Arrays.asList(processedNumbers) +  ", sum = " + sum);
   return sum;
  }
  
  //create chunks, fork and join
  else {
   int mid = begin + (end - begin) / 2; //mid point to partition
   SumTask left  = new SumTask(numbers, begin, mid);  //left partition
   SumTask right = new SumTask(numbers, mid, end);    //right partition
   left.fork();            //asynchronously execute on a separate thread
   int leftAns = right.compute();                  //recurse and compute
   int rightAns = left.join();  //returns the asynchronously executed result
   System.out.println("leftAns=" + leftAns + " + " + "rightAns=" + rightAns);
   return leftAns + rightAns;                         
  }

 }
}


Here is the test class with the main method

package com.fork.join;

import java.util.concurrent.ForkJoinPool;

public class SumTaskTest {

 public static void main(String[] args) {
  int numberOfCpuCores = Runtime.getRuntime().availableProcessors();
  ForkJoinPool forkJoinPool = new ForkJoinPool(numberOfCpuCores);

  Integer[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  int sum = forkJoinPool.invoke(new SumTask(numbers, 0, numbers.length));
  
  System.out.println(sum);
 }

}


The output


ForkJoinPool-1-worker-1 proceesing [[6, 7]], sum = 13
ForkJoinPool-1-worker-3 proceesing [[8, 9, 10]], sum = 27
leftAns=27 + rightAns=13
ForkJoinPool-1-worker-2 proceesing [[3, 4, 5]], sum = 12
ForkJoinPool-1-worker-0 proceesing [[1, 2]], sum = 3
leftAns=12 + rightAns=3
leftAns=40 + rightAns=15
55


Q. Where to use fork/join as opposed to using the ExecutorService framework?

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. Multicore processors are now widespread across server, desktop, and laptop hardware. They are also making their way into smaller devices, such as smartphones and tablets. Fork/Join offers serious gains for solving problems that involve recursion. Because recursion is fundamental to parallel programming on multicore platforms. Java recursion tutorial example with a diagram and example.

The fork/join tasks should operate as “pure” in-memory algorithms in which no I/O operations come into play. Also, communication between tasks through shared state should be avoided as much as possible, because that implies that locking might have to be performed. Ideally, tasks communicate only when one task forks another or when one task joins another.

ExecutorService continues to be a fine solution for many concurrent programming tasks, and in programming scenarios in which recursion is vital to processing power, it makes sense to use Fork/join. This fork and join feature is used in Java 8 parallel stream processing with lambda expressions.

Labels: ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home