In the previous posts about the java.util.concurrent framework, I introduced what for me is the *core* of the package and what you will use the most on real-world applications.

Going further with the topic, it’s worth to know the new fork/join framework introduced in Java 7. The pros and cons of this framework over the usage of thread pools or regular thread/runnable development has been subject of a lot of debate, but I think it is still a nice tool to have in your arsenal.

I’ll use a more classic approach to show you the basic structure of the fork/join framework and code a version of the Quicksort algorithm using it.

My goal here is to introduce you to the tools provided by the fork/join
structure in Java 7, this is not a discussion about the best Quicksort
implementation. If you want to delve into implementing the best
Quicksort possible I recommend you check out this great post about it.

The fork/join framework provides a very straightforward and intuitive
structure to implement recursive and divide and conquer problems that
can be solved concurrently. You start with the *big problem* and break it down in smaller work units until each work unit can be solved directly.

The implementation of your *problem solver* must be a subclass of ForkJoinTask, and you will most likely implement a subclass of it’s children RecursiveAction or RecursiveTask;
RecursiveAction represents a recursive problem solver, capable of
solving a small enough problem directly or breaking it down into smaller
work units; RecursiveTask is similar, but it also has the capability of
returning a result for each work unit executed.

To implement our Quicksort we will use the in-place strategy (we are hardcore, right?) and use a generic list as data so it supports any Java Comparable. With these premises our task can be coded as:

package com.ricardozuasti; import java.util.List; import java.util.concurrent.RecursiveAction; public class QuickSort<T extends Comparable> extends RecursiveAction { private List<T> data; private int left; private int right; public QuickSort(List<T> data){ this.data=data; this.left = 0; this.right = data.size() - 1; } public QuickSort(List<T> data, int left, int right){ this.data = data; this.left = left; this.right = right; } @Override protected void compute() { if (left < right){ int pivotIndex = left + ((right - left)/2); pivotIndex = partition(pivotIndex); invokeAll(new QuickSort(data, left, pivotIndex-1), new QuickSort(data, pivotIndex+1, right)); } } private int partition(int pivotIndex){ T pivotValue = data.get(pivotIndex); swap(pivotIndex, right); int storeIndex = left; for (int i=left; i<right; i++){ if (data.get(i).compareTo(pivotValue) < 0){ swap(i, storeIndex); storeIndex++; } } swap(storeIndex, right); return storeIndex; } private void swap(int i, int j){ if (i != j){ T iValue = data.get(i); data.set(i, data.get(j)); data.set(j, iValue); } } }

The *compute()* method is the one that the fork/join framework
will invoke for each work unit. Our base step (small work unit) is to do
nothing (since a size 1 list is always sorted). Our recursive step uses
the *invokeAll()* method, which is a shortcut to *fork()* all small work units and then *join()* them all again.

And that’s it! We don’t really need anything else. To actually use our new concurrent Quicksort we use a ForkJoinPool instance:

package com.ricardozuasti; import java.util.ArrayList; import java.util.List; import java.util.concurrent.ForkJoinPool; public class Concurrency3 { public static void main(String[] args) { final int SIZE = 10000; List<Integer> myList = new ArrayList<Integer>(SIZE); for (int i=0; i<SIZE; i++){ int value = (int) (Math.random() * 100); myList.add(value); } QuickSort<Integer> quickSort = new QuickSort<Integer>(myList); ForkJoinPool pool = new ForkJoinPool(); pool.invoke(quickSort); } }

And again the *invoke* method is equivalent to doing a *fork()* followed by a *join()*, so after the *pool.invoke()* method returns our list is sorted.