Friday, April 27, 2012

JDK7: Using join/fork framework in Java

If you have read my previous article about concurrency "(Fork and Join) Java solves the painless parallel programming!" you will get the full understanding and an overall idea about the Fork and Join framework.

Here I will give a workable example on how this framework is working in java 7.

The join/fork framework is an approach that supports breaking a problem into smaller and smaller pieces, solving them in parallel, and then combining the results. The new java.util.concurrent.ForkJoinPool class supports this approach. It is designed to work with multi-core systems, ideally with dozens or hundreds of processors. Currently, few desktop platforms support this type of concurrency, but future machines will. With fewer than four processors, there will be little performance improvement.


The ForkJoinPool class is derived from the java.util.concurrent.AbstractExecutorService making it an ExecutorService. It is designed to work with ForkJoinTasks, though it can be used with normal threads. The ForkJoinPool class differs from other executors, in that its threads attempt to find and execute subtasks created by other currently running tasks. This is called work-stealing.


The ForkJoinPool class can be used for problems where the computation on the sub-problems is either modified or returns a value. When a value is returned, a java.util.concurrent.RecursiveTask derived class is used. Otherwise, the java.util.concurrent.RecursiveAction class is used. In this recipe we will illustrate the use of the RecursiveTask derived class.
Getting ready for lap:

To use the fork/join framework for a task that returns a result for each subtask:
1. Create a subclass of RecursiveTask that implements the computation needed.
2. Create an instance of the ForkJoinPool class.
3. Use the ForkJoinPool class' invoke method with the instance of the subclass of the RecursiveTask class.

How to do it...

This application is not intended to be implemented in the most efficient manner, but is used to illustrate the fork/join task. As a result, on systems with a small number of processors, there may be little or no performance improvement.

1. Create a new console application called ForkJoinExample. We will use a static inner class that is derived from RecursiveTask to compute the sum of squares of the integers in the numbers array. First, declare the numbers array in the main class as follows:

2. Add the SumOfSquaresTask class as follows. It creates a subrange of array elements and either uses an iterative loop to compute their sum of squares or breaks the array into smaller pieces based on a threshold size:

3. Add the following main method. For comparison purposes, the sum of squares is computed using a for loop and then using the ForkJoinPool class. The execution time is calculated and displayed as follows:

4. Execute the application. Your output should be similar to the following. However, you should observe different execution times depending on your hardware configuration:

Sum of squares: 18103503627376
Iterative solution time: 5
Sum of squares: 18103503627376
Fork/join solution time: 23

Notice that the iterative solution is faster than the one using the fork/join strategy.

As mentioned earlier, this approach is not always more efficient, unless there are a large number of processors.

Running the application repeatedly will result in different results. A more aggressive testing approach would be to execute the solution repeatedly under possibly different processor loading conditions and then take the average of the result. The size of the threshold will also affect its performance.

How it works...

The numbers array was declared as a 100,000 element integer array. The SumOfSquaresTask class was derived from the RecursiveTask class using the generic type Long. A threshold of 1000 was set. Any subarray smaller than this threshold was solved using iteration. Otherwise the segment was divided in half and two new tasks were created, one for each half.

The ArrayList was used to hold the two subtasks. This was strictly not needed and actually slows down the computation. However, it would be useful if we decided to partition the array into more than two segments. It provides a convenient way of recombining the elements when the subtasks are joined.


The fork method was used to split up the subtasks. They entered the thread pool and will eventually be executed. The join method returned the results when the subtask completed. The sum of the subtasks was added together and then returned.

In the main method, the first code segment computed the sum of squares using a for loop. The start and stop time were based on the current time measured in milliseconds. The second segment created an instance of the ForkJoinPool class, and then used it's invoke method with a new instance of the SumOfSquaresTask object. The arguments passed to the SumOfSquaresTask constructor, instructed it to start with the first element of the array and end with the last. Upon completion, the execution time was displayed.

More…

The ForkJoinPool class has several methods that report on the state of the pool, including:


getPoolSize: This method returns the number of threads that are started but are not completed.
getRunningThreadCount: This method returns an estimate of the number of threads that are not blocked but are waiting to join other tasks.
getActiveThreadCount: This method returns an estimate of the number of threads executing tasks.

The ForkJoinPool class' toString method returns several aspects of the pool.

Add the following statement immediately after the invoke method is executed:

When the program executes, you will get an output similar to the following:

forkJoinPool: java.util.concurrent.ForkJoinPool@18fb53f6[Running, parallelism = 4, size =55, active = 0, running = 0, steals = 171, tasks = 0, submissions = 0]

References:
1.(Fork and Join) Java solves the painless parallel programming!
2.ForkJoinPool class documentation.
3.Fork/Join Java SE concurrency tutorial.