How to make use of RecursiveTask and ForkJoinPool

RecursiveTask is a predefined class in the package java.util.concurrent. This class allows you to implement recursivity using multiple threads. To illustrate, let's assume that you want to calculate the sum of numbers from 1 to 1.000.000 making use of 10 threads at same time(parallelism) and exploiting efficiently processors available on the computer:

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

// This class illustrates how we can compute the sum of 1..N numbers using fork/join framework.
// The range of numbers are divided into half until the range can be handled by a thread.
// Once the range summation completes, the result gets summed up together.  

class SumOfNUsingForkJoin {

private static long N = 1000_000; // one million - we want to compute sum
// from 1 .. one million

private static final int NUM_THREADS = 10;
// number of threads to create for
// distributing the effort

// This is the recursive implementation of the algorithm; inherit from
// RecursiveTask
// instead of RecursiveAction since we're returning values.
static class RecursiveSumOfN extends RecursiveTask<Long> {
long from, to;
// from and to are range of values to sum-up

public RecursiveSumOfN(long from, long to) {
this.from = from;
this.to = to;
}

// the method performs fork and join to compute the sum if the range
// of values can be summed by a threadremember that we want to divide
// the summation task equally among NUM_THREADS) then, sum the range
// of numbers from..to using a simple for loop;
// otherwise, fork the range and join the results
@Override
public Long compute() {

if ((to - from) <= N / NUM_THREADS) {
// the range is something that can be handled
// by a thread, so do summation

long localSum = 0;
// add in range 'from' .. 'to' inclusive of the value 'to'
for (long i = from; i <= to; i++) {
localSum += i;
}

System.out.printf("\tSum of value range %d to %d is %d %n", from, to, localSum);
return localSum;
} else {
// no, the range is too big for a thread to handle,
// so fork the computation
// we find the mid-point value in the range from..to
long mid = (from + to) / 2;
System.out.printf("Forking computation into two ranges: " + "%d to %d and %d to %d %n", from, mid, mid,
to);

// determine the computation for first half
// with the range from..mid
RecursiveSumOfN firstHalf = new RecursiveSumOfN(from, mid);

// now, fork off that task
firstHalf.fork();
// determine the computation for second half
// with the range mid+1..to
RecursiveSumOfN secondHalf = new RecursiveSumOfN(mid + 1, to);
long resultSecond = secondHalf.compute();

// now, wait for the first half of computing sum to
// complete, once done, add it to the remaining part
return firstHalf.join() + resultSecond;
}
}
}

public static void main(String[] args) {
// Create a fork-join pool that consists of NUM_THREADS
ForkJoinPool pool = new ForkJoinPool(NUM_THREADS);

// submit the computation task to the fork-join pool
long computedSum = pool.invoke(new RecursiveSumOfN(0, N));

// this is the formula sum for the range 1..N
long formulaSum = (N * (N + 1)) / 2;

// Compare the computed sum and the formula sum
System.out.printf("Sum for range 1..%d; computed sum = %d, " + "formula sum = %d %n", N, computedSum,
formulaSum);
}
}

Executing the example will result in:

Forking computation into two ranges: 0 to 500000 and 500000 to 1000000 
Forking computation into two ranges: 500001 to 750000 and 750000 to 1000000 
Forking computation into two ranges: 0 to 250000 and 250000 to 500000 
Forking computation into two ranges: 500001 to 625000 and 625000 to 750000 
Forking computation into two ranges: 0 to 125000 and 125000 to 250000 
Forking computation into two ranges: 750001 to 875000 and 875000 to 1000000 
Forking computation into two ranges: 500001 to 562500 and 562500 to 625000 
Forking computation into two ranges: 125001 to 187500 and 187500 to 250000 
Forking computation into two ranges: 0 to 62500 and 62500 to 125000 
Sum of value range 187501 to 250000 is 13671906250 
Forking computation into two ranges: 625001 to 687500 and 687500 to 750000 
Sum of value range 500001 to 562500 is 33203156250 
Sum of value range 62501 to 125000 is 5859406250 
Sum of value range 625001 to 687500 is 41015656250 
Forking computation into two ranges: 250001 to 375000 and 375000 to 500000 
Forking computation into two ranges: 375001 to 437500 and 437500 to 500000 
Sum of value range 687501 to 750000 is 44921906250 
Sum of value range 0 to 62500 is 1953156250 
Sum of value range 562501 to 625000 is 37109406250 
Sum of value range 125001 to 187500 is 9765656250 
Forking computation into two ranges: 750001 to 812500 and 812500 to 875000 
Forking computation into two ranges: 875001 to 937500 and 937500 to 1000000 
Sum of value range 750001 to 812500 is 48828156250 
Sum of value range 937501 to 1000000 is 60546906250 
Sum of value range 812501 to 875000 is 52734406250 
Sum of value range 375001 to 437500 is 25390656250 
Sum of value range 437501 to 500000 is 29296906250 
Forking computation into two ranges: 250001 to 312500 and 312500 to 375000 
Sum of value range 875001 to 937500 is 56640656250 
Sum of value range 250001 to 312500 is 17578156250 
Sum of value range 312501 to 375000 is 21484406250 
Sum for range 1..1000000; computed sum = 500000500000, formula sum = 500000500000