Taming Tiger: Concurrent Collections

Moving beyond Map, Collection, List, and Set: John Zukowski discusses the new library release in the Tiger release of the J2SE platform and what it provides: a set of utilities commonly needed in concurrent programs. If you are interested in optimizing multithreaded access to your collections, you’ve come to the right place. (This intermediate-level article was first published by IBM developerWorks, June 16, 2004, at http://www.ibm.com/developerWorks.)

What began as author Doug Lea’s util.concurrent package has morphed into JSR-166 and into the Tiger release of the J2SE platform. What the new library provides is a set of utilities commonly needed in concurrent programs. If you are interested in optimizing multithreaded access to your collections, you’ve come to the right place. Share your thoughts on this article with the author, John Zukowski, and other readers in the accompanying discussion forum.

In the early days of Java programming, a professor from the State University of New York (SUNY) College at Oswego decided to create a simple library to help developers build applications that were better able to handle multithreaded situations. This isn’t to say you couldn’t get by with the existing libraries, but just like having a standard networking library, it was easier to do multithreading yourself with a debugged, trusted library. With the help of a related book from Addison-Wesley, over time this library became popular. Eventually, the author, Doug Lea, decided to pursue making it a standard part of the Java platform as JSR-166. What that library has morphed into is the java.util.concurrent package of the Tiger release. In this Taming Tiger tip, you’ll explore the new Queue interface in the Collections Framework, the non-concurrent and concurrent implementations of that interface, a concurrent Map implementation, and special-purpose concurrent List and Set implementations for when read operations heavily exceed write operations.

Introducing the Queue interface

The java.util package offers a new base interface for collections: java.util.Queue. While you certainly can treat a java.util.List as a queue by adding and removing from opposite ends, what the new Queue interface offers is additional methods to support adding, removing, and inspecting the collection, as shown below:

public boolean offer(Object element)
public Object remove()
public Object poll()
public Object element()
public Object peek()

Basically, a queue is a first-in, first-out (FIFO) data structure. Some queues are restricted in size, so when you want to add a new item to a full queue, the additional item is rejected. That’s where the new offer method comes into play. Instead of throwing an unchecked exception with a call to the add() method, you just get false returned by offer(). The remove() and poll() methods are both for removing the first element (head) of the queue. While remove() behaves like the Collection interface version, instead of throwing an exception when called with an empty collection, the new poll() method just returns null. The newer methods are thus more for when the exceptional condition is the norm. The last two methods, element() and peek(), are for querying the element at the head of the queue. Like the remove() method, element() throws an exception when the queue is empty, whereas peek() returns null.

IBM developerWorksVisit developerWorks for thousands of developer articles, tutorials, and resources related to open standard technologies, IBM products, and more. See developerWorks.

{mospagebreak title=Using the Basic Queues}

There are two sets of Queue implementations in Tiger: those that implement the new BlockingQueue interface, and those that don’t. First, I’ll take a look at those that don’t.

In the simplest case, the pre-existing java.util.LinkedList implementation has been retrofitted to implement not only the java.util.List interface, but also the java.util.Queue interface. You can treat the collection as either. Listing 1 shows one way a LinkedList as a Queue can be used:

Listing 1. Using a Queue implementation

Queue queue = new LinkedList();
queue.offer(“One”);
queue.offer(“Two”);
queue.offer(“Three”);
queue.offer(“Four”);
// Head of queue should be One
System.out.println(“Head of queue is: ” + queue.poll());

Next up in complexity is the new java.util.AbstractQueue class. This class works similarly to the java.util.AbstractList and java.util.AbstractSet classes. Instead of implementing the entire interface yourself when creating a custom collection, you just subclass the abstract implementation and fill in the details. With AbstractQueue, the methods you must provide implementations for are offer(), poll(), and peek(). Methods like add() and addAll() are modified to use offer(), while clear() and remove() use poll(). Finally, element() uses peek(). You certainly can provide optimized implementations of these methods in your subclasses, but you don’t have to. And, instead of creating your own subclasses, you can use one of the several built-in implementations, two of which aren’t blocking queues: PriorityQueue and ConcurrentLinkedQueue.

The PriorityQueue and ConcurrentLinkedQueue classes add two more concrete collection implementations to the Collections Framework. The PriorityQueue class essentially maintains an ordered list. Elements added to a Queue are positioned in the PriorityQueue class based on either their natural ordering (through its java.util.Comparable implementation) or according to the java.util.Comparator implementation passed into the constructor. Changing LinkedList in Listing 2 to PriorityQueue will result in Four being printed out instead of One, as Four comes first alphabetically — the natural ordering of strings. A ConcurrentLinkedQueue is a thread-safe queue based on linked nodes. Concurrent access does not need to be synchronized. Because it adds elements to the end of the queue and removes them from the head, ConcurrentLinkedQueue works well for shared access to a common collection, as long as you don’t need to know the size of the queue. Collecting this information is slow, requiring queue traversal.

IBM developerWorksVisit developerWorks for thousands of developer articles, tutorials, and resources related to open standard technologies, IBM products, and more. See developerWorks.

{mospagebreak title=Using the Blocking Queues}

The new java.util.concurrent package adds the BlockingQueue interface and five blocking queue classes to the set of concrete collection classes available in the Collections Framework. For those unfamiliar with the concept of a blocking queue, it is essentially a FIFO data structure, with a twist. Instead of adding and removing elements from the queue immediately, the thread performing the operation blocks until space or an element is available. The Javadoc for the BlockingQueue interface demonstrates the basic usage of a blocking queue, as shown in Listing 2. The put() operation in the producer will block when there is no space available and the take() operation in the consumer will block when there is nothing in the queue.

Listing 2. Using a BlockingQueue

 class Producer implements Runnable {
   private final BlockingQueue queue;
   Producer(BlockingQueue q) { queue = q; }
   public void run() {
     try {
       while(true) { queue.put(produce()); }
     } catch (InterruptedException ex) { … handle …}
   }
   Object produce() { … }
 }

 class Consumer implements Runnable {
   private final BlockingQueue queue;
   Consumer(BlockingQueue q) { queue = q; }
   public void run() {
     try {
       while(true) { consume(queue.take()); }
     } catch (InterruptedException ex) { … handle …}
   }
   void consume(Object x) { … }
 }

 class Setup {
   void main() {
     BlockingQueue q = new SomeQueueImplementation();
     Producer p = new Producer(q);
     Consumer c1 = new Consumer(q);
     Consumer c2 = new Consumer(q);
     new Thread(p).start();
     new Thread(c1).start();
     new Thread(c2).start();
   }
 }

Each of the five queues offers something different:

  • ArrayBlockingQueue: A bounded queue backed by an array

  • LinkedBlockingQueue: An optionally bounded queue backed by linked nodes

  • PriorityBlockingQueue: An unbounded priority queue backed by a priority heap

  • DelayQueue: A time-based scheduling queue backed by a priority heap

  • SynchronousQueue: A simple rendezvous mechanism utilizing the
    BlockingQueue interface

The first two classes, ArrayBlockingQueue and LinkedBlockingQueue are nearly identical, differing only by their backing store and that LinkedBlockingQueue is not always bounded by capacity. A LinkedBlockingQueue class unbound by size will never cause a wait when adding an element to the blocking queue (at least not until there are Integer.MAX_VALUE elements in it).

PriorityBlockingQueue is a queue with an unbound capacity that maintains elements in their logical order through use of the Comparable sort order of the contained elements. Think of it as a possible replacement for TreeSet. For instance, adding the strings One, Two, Three, and Four to the queue will result in Four being the first one taken out. For elements without a natural order, you can provide a Comparator to the constructor. There is one trick with PriorityBlockingQueue, though. The Iterator instance returned from iterator() doesn’t necessarily return the elements in priority order. If you must get all the elements in priority order for traversal, get them all through the toArray() method and sort them yourself, like Arrays.sort(pq.toArray()).

The new DelayQueue implementation is probably the most interesting (and complicated) of the bunch. Elements added to the queue must implement the new Delayed interface (just one method — long getDelay(java.util.concurrent.TimeUnit unit)). While the queue is unbound in size, enabling adds to return immediately, one cannot take an element from the queue until the delay time has expired. When multiple elements have expired delays, the element with the earliest/oldest delay expiration will be taken first. It sounds more complicated then it is. Listing 3 demonstrates the use of this new blocking queue collection:

Listing 3. Using a DelayQueue implementation

import java.util.*;
import java.util.concurrent.*;

public class Delay {
  /**
   * Delayed implementation that actually delays
   */
  static class NanoDelay implements Delayed {
    long trigger;
    NanoDelay(long i) {
      trigger = System.nanoTime() + i;
    }
    public int compareTo(Object y) {
      long i = trigger;
      long j = ((NanoDelay)y).trigger;
      if (i < j) return -1;
      if (i > j) return 1;
      return 0;
    }
    public boolean equals(Object other) {
      return ((NanoDelay)other).trigger == trigger;
    }
    public boolean equals(NanoDelay other) {
      return ((NanoDelay)other).trigger == trigger;
    }
    public long getDelay(TimeUnit unit) {
      long n = trigger – System.nanoTime();
      return unit.convert(n, TimeUnit.NANOSECONDS);
    }
    public long getTriggerTime() {
      return trigger;
    }
    public String toString() {
      return String.valueOf(trigger);
    }
  }
  public static void main(String args[]) throws InterruptedException {
    Random random = new Random();
    DelayQueue queue = new DelayQueue();
    for (int i=0; i < 5; i++) {
      queue.add(new NanoDelay(random.nextInt(1000)));
    }
    long last = 0;
    for (int i=0; i < 5; i++) {
      NanoDelay delay = (NanoDelay)(queue.take());
      long tt = delay.getTriggerTime();
      System.out.println(“Trigger time: ” + tt);
      if (i != 0) {
        System.out.println(“Delta: ” + (tt – last));
      }
      last = tt;
    }
  }
}

The example starts with an inner class NanoDelay that will essentially pause for the given random number of nanoseconds, taking advantage of the new nanoTime() method of System. The main() method then only puts NanoDelay objects into the queue and takes them out again. If you wanted the queued item to do something else, you would need to add that to the implementation of the Delayed object and call that new method upon retrieval from the queue. (Feel free to expand on NanoDelay yourself to demonstrate having an additional method to do something interesting.) The time delta is displayed between successive calls to get elements from the queue. If the delta is ever negative, consider that an error, as you should never get an item from the queue with an earlier trigger time, when the delay has ended.

The SynchronousQueue class is the simplest of the bunch. It has no internal capacity. It works as a handoff mechanism between threads. The producer adding an element to the queue will wait for a consumer in another thread. When that consumer is available, the element is passed directly between consumer and producer, never literally getting added to the blocking queue.

IBM developerWorksVisit developerWorks for thousands of developer articles, tutorials, and resources related to open standard technologies, IBM products, and more. See developerWorks.

{mospagebreak title=Using the ConcurrentMap implementation}

The new java.util.concurrent.ConcurrentMap interface and the ConcurrentHashMap implementation let you add an element to a map only if the key isn’t present and remove an element from a map only if the key is present and mapped to a specific value.

For adding to the map, there’s the new putIfAbsent() method. The method accepts the key and value to add to the ConcurrentMap implementation, like the normal put() method, but will only add the key to the map if the map doesn’t contain the key. If the map already contains the key, the existing value for the key is preserved. The putIfAbsent() method is atomic. Without calling this atomic operation, the code in Listing 4 would need to be called from an appropriately synchronized block:

Listing 4. Equivalent putIfAbsent() code


  if (!map.containsKey(key)) {
    return map.put(key, value);
  } else {
    return map.get(key);
  }


Like the putIfAbsent() method, the overloaded version of the remove() method accepts two arguments — a key and value. When called, it will only remove the key from the map if the key is mapped to the specific value. If there is no match, the key isn’t removed, and false is returned. If the value matches the current map contents for the key, the key is removed. Listing 5 shows the equivalent source for this operation:

Listing 5. Equivalent remove() code

  if (map.get(key).equals(value)) {
    map.remove(key);
    return true;
  } else {
    return false;
  }

Using CopyOnWriteArrayList and CopyOnWriteArraySet

The copy-on-write pattern is described best in Doug Lea’s Concurrent Programming in Java book, Chapter 2, Section 2.4.4 (see Resources list). Essentially, the pattern states that to maintain a consistent snapshot of an object, you rely on immutability to eliminate the need for synchronization when you need to coordinate readings of separate but related attributes. For collections, that means that if you have a lot of reads (that is, get()) and iterations, you don’t have to synchronize the operations to worry about the occasional write (that is, add()) call. For the new CopyOnWriteArrayList and CopyOnWriteArraySet classes, all mutable operations make a copy of the backing array first, make the change to the copy, and then replace the copy. This behavior guarantees that ConcurrentModificationException will never be thrown while iterating over a collection that is changing underneath itself. Iterating through the collection will complete with the original collection, while the updated collection will be available for future operations.

These new collections, CopyOnWriteArrayList and CopyOnWriteArraySet, work best when the read operations typically far outweigh the write operations. One example frequently mentioned is for the use of listener lists. Having said that, the Swing components have not been modified to use the new collections. Instead, they continue to use a javax.swing.event.EventListenerList for the maintenance of their lists of listeners.

As Listing 6 demonstrates, the use of the collection is identical to their non-copy-on-write alternative. Just create the collection and add or remove elements from it. Even as objects get added to the collection, the original Iterator can proceed, working through the items in the original collection.

Listing 6. Demonstrating a copy-on-write collection

import java.util.*;
import java.util.concurrent.*;

public class CopyOnWrite {
  public static void main(String args[]) {
    List list1 = new CopyOnWriteArrayList(Arrays.asList(args));
    List list2 = new ArrayList(Arrays.asList(args));
    Iterator itor1 = list1.iterator();
    Iterator itor2 = list2.iterator();
    list1.add(“New”);
    list2.add(“New”);
    try {
      printAll(itor1);
    } catch (ConcurrentModificationException e) {
      System.err.println(“Shouldn’t get here”);
    }
    try {
      printAll(itor2);
    } catch (ConcurrentModificationException e) {
      System.err.println(“Will get here.”);
    }
  }
  private static void printAll(Iterator itor) {
    while (itor.hasNext()) {
      System.out.println(itor.next());
    }
  }
}

The sample program creates both a CopyOnWriteArrayList and ArrayList instance from the command line arguments. After getting an Iterator from each, an element is added to each. The CopyOnWriteArrayList iteration is able to proceed without exception while the ArrayList iteration stops immediately with a ConcurrentModificationException problem, because the original collection changed after getting the iterator. As long as this is the behavior you want, like for notifying all of the elements in the original set of event listeners, you’re better off using the copy-on-write collections. If not, stick with the originals, and be sure to deal with the exception if and when it happens.

Conclusion

There are many big additions to the Tiger release of the J2SE platform. In addition to the language-level changes like generics support, this one library is probably the biggest addition as far as what will be used by the widest audiences. Not to belittle other packages added to the platform, like the Java Management Extensions (JMX), but most other big library enhancements are meant for narrower groups of developers. This library isn’t. In addition to the other concurrency utilities for locking and atomic operations, expect to use these classes regularly. Learn them early and take advantage of what they offer.

IBM developerWorksVisit developerWorks for thousands of developer articles, tutorials, and resources related to open standard technologies, IBM products, and more. See developerWorks.

{mospagebreak title=Resources}

Resources

Participate in the discussion forum on this article. (You can also click Discuss at the top or bottom of the article to access the forum.)

Download J2SE 1.5 Beta 2 from the Sun Developer Network.

Download the source code example zip file used in this article.

Read the java.util.concurrent package Javadocs for 1.5.0.

Read all about the Concurrency Utilities in the documentation for JSR-166.

Follow the progress of JSR-166 by signing up for the concurrency-interest mailing list.

Java theory and practice columnist Brian Goetz discusses Doug Lea’s earlier util.concurrent package in “Concurrency made simple (sort of)” (developerWorks, November 2002) and “Concurrent collections classes” (developerWorks, July 2003).

Read the complete set of Taming Tiger tips from John Zukowski. And if you’re still working with J2SE 1.4, you’ll want to read Magic with Merlin series, too.

Learn the principles of threading in the “Introduction to Java threads” tutorial.

Start at the source of the java.util.concurrent package by exploring Doug Lea’s book, Concurrent Programming in Java: Design Principles and Patterns (Addison-Wesley, 1999).

Examine the progress of Tiger (J2SE 1.5) with JSR 176.

Email bug reports to Sun at j2se-beta-feedback@sun.com.

Visit the Developer Bookstore for a comprehensive listing of technical books, including hundreds of Java-related titles.

You’ll find hundreds of articles about every aspect of Java programming in the developerWorks Java technology zone.

Interested in test driving IBM products without the typical high-cost entry point or short-term evaluation license? The developerWorks Subscription provides a low-cost, 12-month, single-user license for WebSphere®, DB2®, Lotus®, Rational®, and Tivoli® products — including the Eclipse-based WebSphere Studio IDE — to develop, test, evaluate, and demonstrate your applications.

See the URL for the download zip file in the Resources list:

http://www-106.ibm.com/developerworks/java/library/j-tiger06164.html

About the author

John Zukowski conducts strategic Java consulting with JZ Ventures, Inc. and is working with SavaJe Technologies to develop a next-generation mobile phone platform. His latest books are Mastering Java 2, J2SE 1.4 (Sybex, April 2002) and Learn Java with JBuilder 6 (Apress, March 2002). Reach him at jaz@zukowski.net.

IBM developerWorksVisit developerWorks for thousands of developer articles, tutorials, and resources related to open standard technologies, IBM products, and more. See developerWorks.

[gp-comments width="770" linklove="off" ]

antalya escort bayan antalya escort bayan Antalya escort diyarbakir escort