Untangling Java concurrency

Java 101: Java concurrency without the pain, Part 2

Locking, atomic variables, Fork/Join, and what to expect in Java 8

1 2 3 4 Page 4
Page 4 of 4

Listing 8. ForkJoinDemo.java

import java.util.Arrays;

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class ForkJoinDemo
{
   static class SortTask extends RecursiveAction 
   {
      private final long[] array; 
      private final int lo, hi;

      SortTask(long[] array, int lo, int hi) 
      {
         this.array = array; 
         this.lo = lo; 
         this.hi = hi;
      }

      SortTask(long[] array) 
      { 
         this(array, 0, array.length); 
      }

      private final static int THRESHOLD = 1000;

      @Override
      protected void compute() 
      {
         if (hi-lo < THRESHOLD)
            sortSequentially(lo, hi);
         else 
         {
            int mid = (lo+hi) >>> 1;
            invokeAll(new SortTask(array, lo, mid),
                      new SortTask(array, mid, hi));
            merge(lo, mid, hi);
         }
      }

      private void sortSequentially(int lo, int hi) 
      {
         Arrays.sort(array, lo, hi);
      }

      private void merge(int lo, int mid, int hi) 
      {
         long[] buf = Arrays.copyOfRange(array, lo, mid);
         for (int i = 0, j = lo, k = mid; i < buf.length; j++)
            array[j] = (k == hi || buf[i] < array[k]) ? buf[i++] : array[k++];
      }
   }

   public static void main(String[] args)
   {
      long[] array = new long[300000];
      for (int i = 0; i < array.length; i++)
         array[i] = (long) (Math.random()*10000000);
      long[] array2 = new long[array.length];
      System.arraycopy(array, 0, array2, 0, array.length);

      long startTime = System.currentTimeMillis();
      Arrays.sort(array, 0, array.length-1);
      System.out.printf("sequential sort completed in %d millis%n", 
                        System.currentTimeMillis()-startTime);
      for (int i = 0; i < array.length; i++)
         System.out.println(array[i]);

      System.out.println();

      ForkJoinPool pool = new ForkJoinPool();
      startTime = System.currentTimeMillis();
      pool.invoke(new SortTask(array2));
      System.out.printf("parallel sort completed in %d millis%n", 
                        System.currentTimeMillis()-startTime);
      for (int i = 0; i < array2.length; i++)
         System.out.println(array2[i]);
   }
}

Listing 8's ForkJoinDemo class declares a SortedTask nested class that describes a resultless fork/join task for sorting a long integer array. The key to this class is the overriding protected void compute() method, which is called by a worker thread to sort part of the array.

The mechanics of ForkJoinDemo

compute() first determines whether it should sort the array sequentially or divide the array among a pair of subtasks and invoke them recursively. As long as the difference between the lo and hi indexes is greater than or equal to THRESHOLD's value, the array is subdivided.

When a problem is very small, a sequential solution is often faster than a parallel solution because there's less overhead. The ideal threshold depends on the cost of coordinating tasks that run in parallel. The lower this cost, the lower the threshold value can be.

RecursiveAction inherits ForkJoinTask's void invokeAll(ForkJoinTask<?>... tasks) method for forking a variable number of tasks. It's passed two SortTask instances representing the low and high halves of the array to sort.

The invokeAll() call is followed by a call to merge(), which combines the results from the previously executed SortTask instances. This completes the behavior of this fork/join task.

Listing 8 also presents a main() method for running this application. This method first creates two large long integer arrays with identical content. It then sorts the first array sequentially, and sorts the second array via ForkJoinPool.

Compile Listing 8 (javac ForkJoinDemo.java) and run the application (java ForkJoinDemo). The following is a subset of the output that I observed during one run on my platform, a dual-core 64-bit AMD processor:

sequential sort completed in 94 millis
172
214
287
296
342
343
...

parallel sort completed in 78 millis
172
214
287
296
342
343
...

This output indicates that the parallel sorting is faster than sequential sorting.

Concurrency in Java 8

Java 8 is expected to reach general availability status in March 2014. Although this release will likely be celebrated (and remembered) for introducing Lambda expressions to the Java language, it includes other new features that will help to improve developer productivity. Consider the following enhancements to the Java Concurrency Utilities:

  • Improved ConcurrentHashMap class: The java.util.concurrent.ConcurrentHashMap class has been improved to make it and classes that use it more useful as caches. New methods include sequential and parallel bulk operations (forEach, search, and reduce) methods.
  • Fence intrinsics: This update exposes memory fence controls into Java code so that the Java Concurrency Utilities APIs can more accurately and efficiently control memory ordering and bounding. This task is accomplished by adding "three memory-ordering intrinsics to the sun.misc.Unsafe class."
  • Changes to the Fork/Join framework: The ForkJoinPool and ForkJoinTask classes have been updated to improve performance and supply additional functionality. "New features include support for completion-based designs that are often most appropriate for IO-bound usages, among others." Additionally, a new CountedCompleter class that subclasses ForkJoinTask and provides a completion action that's "performed when triggered and there are no remaining pending actions" has been introduced.
  • New CompletableFuture class: The new java.util.concurrent.CompletableFuture class is a "Future that may be explicitly completed (setting its value and status), and may include dependent functions and actions that trigger upon its completion." This class is associated with the new java.util.concurrent.CompletableFuture.AsynchronousCompletionTask interface and the new java.util.concurrent.CompletionException exception. Check out Tomasz Nurkiewicz's Java 8: Definitive guide to CompletableFuture blog post for an extensive tutorial on how to use CompletableFuture.
  • New StampedLock class: The new java.util.concurrent.locks.StampedLock class is "a capability-based lock with three modes for controlling read/write access." Check out Dr. Heinz Kabutz's Phaser and StampedLock Concurrency Synchronizers video presentation to learn about StampedLock. A PDF file of this presentation is also available.
  • Parallel array sorting: The java.util.Arrays class has been augmented with several parallel-prefixed class methods (such as void parallelSort(int[] a)) that leverage the Fork/Join framework to sort arrays in parallel.
  • Scalable updatable variables: The java.util.concurrent.atomic package includes new DoubleAccumulator, DoubleAdder, LongAccumulator, and LongAdder classes that address a scalability problem in the context of maintaining a single count, sum, or some other value with the possibility of updates from many threads. These new classes "internally employ contention-reduction techniques that provide huge throughput improvements as compared to atomic variables. This is made possible by relaxing atomicity guarantees in a way that is acceptable in most applications."

In conclusion

The Java Concurrency Utilities framework offers an alternative to Java's low-level threading capabilities. This article completes my two-part series on java.util.concurrent by focusing on the Locking framework, atomic variables, and the Fork/Join framework. I also introduced seven significant enhancements to the Java Concurrency Utilities, which are coming in Java 8.

The two articles in this series couldn't cover every API in the Java Concurrency Utilities, but there is more to explore. The code file for this article includes more demos, including exercises using the java.util.concurrent.ThreadLocalRandom and java.util.concurrent.locks.LockSupport classes, and more.

Jeff Friesen is a freelance tutor and software developer with an emphasis on Java and Android. In addition to writing Java and Android books for Apress, Jeff has written numerous articles on Java and other technologies for JavaWorld, informIT, Java.net, DevSource, and SitePoint. Jeff can be contacted via his website at TutorTutor.ca.

Learn more about this topic

Previous articles in Java 101: The next generation

Concurrency tutorials on JavaWorld:

  • Modern threading for not-quite-beginners (Cameron Laird, JavaWorld, January 2013): Get an overview of callable and runnable, learn more about synchronized blocks, and find out how you can use java.util.concurrent to work around deadlock and similar threading pitfalls.
  • Multicore processing for client-side Java applications (Kirill Grouchnikov, JavaWorld, September 2007): Get a hands-on introduction to collection sorting using the CountDownLatch and Executors.newFixedThreadPool concurrency utilities.
  • Java concurrency with thread gates (Obi Ezechukwu, JavaWorld, March 2009): See the Java concurrency utilities at work in a realistic implementation of the Thread Gates concurrency pattern.
  • Hyper-threaded Java (Randall Scarberry, JavaWorld, November 2006): See for yourself how two java.util.concurrent classes were used to optimize thread use for faster performance in a real-world application.
  • Java Tip 144: When to use ForkJoinPool vs ExecutorService (Madalin Ilie, JavaWorld, October 2011): Demonstrates the performance impact of replacing the standard ExecutorService class with ForkJoinPool in a web crawler.
1 2 3 4 Page 4
Page 4 of 4