Featured White Papers

• Measuring Risk to Improve Java Software Quality
• Do You Really Get Classloaders?
• Pragmatic Continuous Delivery with Jenkins, Nexus, and LiveRebel
• Your Next Java Web App: Less XML, No Long Restarts, Fewer Hassles
• Coding with JRebel, Java Forever Changed
• 2012 Developer Productivity Report: Java Tools, Tech, Devs, and Data

Sponsored Links

• Graph databases are 1000x faster than relational.

  Learn More!

• Career opportunities at Harman- Careers That'll Rock Your Socks Off.

  Learn More!

• Developer-friendly Java PDF libraries by Qoppa Software

  Live Demos

• Stop blaming your app! Diagnose Java performance issues.

  Free tool >

• UrbanCode: Go From Continuous Integration to
  Continuous Delivery

  Learn More!

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

Multicore processing for client-side Java applications

A parallel-programming implementation for collection sorting

By Kirill Grouchnikov, JavaWorld.com, 09/25/07

Page 2 of 3

Java implementations of sorting algorithms

A look at the implementation of the various sorting algorithms in the core Arrays and Collections classes is especially easy now that they are licensed as open source. All the sort routines in the Arrays class that operate on primitive types (such as byte, char, and double) use quicksort, which is generally recognized as the fastest sorting algorithm for most inputs. (In some corner cases the performance might degrade to quadratic.) The sort API that operates on an array of Objects is a mergesort, which is simpler to implement and provides N*log(N) performance as well. Finally, Collections.sort(List) delegates the actual sorting to the Arrays.sort(Object[]).

Taking a closer look at the mergesort in the Arrays class, you can see that it is indeed the classic mergesort with a few optimization tweaks for corner cases. If the array size is small (seven or fewer with the current implementation), it reverts to the bubble sort. Otherwise, the array is split in half, and the same method is called (recursively) on both halves. After both halves are sorted, the code "merges" them (hence the name).

Going back to the hardware advances, you can easily see that increasing the CPU speed (number of operations per second) by a factor of two results in a matching improvement in the algorithm running time. This is the case because the mergesort is a sequential recursive algorithm that does exactly the same sequence of steps, provided the same input.

Core sorting in the multicore world

What's the problem with the current mergesort implementation when it runs on a multicore machine? The answer is simple: it doesn't explore the inherent concurrency of the recursive implementation. When the array is split in half, the sorting of the second half begins only after the sorting of the first half is done. But new concurrency utilities in JDK 6.0 come to the rescue, letting you perform these subtasks in parallel without any communication between them. At the end, when both tasks are done, the sorted halves still need to be merged together. This still results in N*log(N) performance, but this time with a lower constant factor. To illustrate how much lower, I'll show you a simple implementation of a mergesort that takes advantage of a multicore environment. This takes you into the world of parallel or concurrent programming.

Parallel programming to the rescue

Here is a guided walkthrough for the concurrent implementation of this alternative implementation of Arrays.mergeSort. The code examples I'll show are based on the core JDK implementation (and as such are licensed under GPL). The first step, shown in Listing 1, is to check the number of available processors (cores). If you have only one processor, parallelizing the implementation gains you nothing; you will only pay for the overhead of creating threads and the thread-context switch while the array halves are being sorted.

Listing 1. Special case for small input and one processor

if ((a.length < 7) || (Runtime.getRuntime().availableProcessors() == 1)) {
   mergeSort(aux, a, 0, a.length, 0);
   return;
}

Now you need to decide how to split up the work among all the available processors. This decision is specific to the task at hand. In order to simplify the implementation, I'll split the work between only two processors. It's easy to see that the final merge stage can begin only when both halves are sorted. Listing 2 uses the new concurrency utilities available in JDK 6.0:

• The CountDownLatch class lets you wait for a specific number of tasks to be completed (two in this case).
• Executors.newFixedThreadPool launches two threads that sort the array halves.

Listing 2. Splitting the sort into two independently and concurrently processed halves

final CountDownLatch doneSignal = new CountDownLatch(2);
ExecutorService e = Executors.newFixedThreadPool(2);

class WorkerRunnable implements Runnable {
   int start;
   int end;

   WorkerRunnable(int start, int end) {
      this.start = start;
      this.end = end;
   }

   public void run() {
      mergeSort(aux, a, start, end, 0);
      doneSignal.countDown();
   }
}

int mid = a.length >> 1;
e.execute(new WorkerRunnable(0, mid));
e.execute(new WorkerRunnable(mid, a.length));
try {
   doneSignal.await(); // wait for all to finish
} catch (InterruptedException ie) {
}
e.shutdown();

After CountDownLatch.await returns, you know that both subtasks have been completed. At this point, you can merge the sorted halves, as shown in Listing 3. (This code is taken from Arrays.mergeSort with relevant variable renaming.)

Listing 3. Merging the two sorted halves

System.arraycopy(a, 0, aux, 0, a.length);
// merge two halves
for (int i = 0, p = 0, q = mid; i < a.length; i++) {
   if (q >= a.length || p < mid
         && ((Comparable) aux[p]).compareTo(aux[q]) <= 0)
      a[i] = aux[p++];
   else
      a[i] = aux[q++];
}