Home » Core Java » util » concurrent » RecursiveTask » java.util.concurrent.RecursiveTask Example

About Ashraf Sarhan

Ashraf Sarhan
Ashraf Sarhan is a passionate software engineer, an open source enthusiast, has a Bsc. degree in Computer and Information Systems from Alexandria University. He is experienced in building large, scalable and distributed enterprise applications/service in multiple domains. He also has a keen interest in JavaEE, SOA, Agile and Big Data technologies.

java.util.concurrent.RecursiveTask Example

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.

Download
You can download the full source code of this example here: RecursiveTaskExampleCode.zip
(No Ratings Yet)
Start the discussion Views Tweet it!

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

 

Leave a Reply

avatar
  Subscribe  
Notify of