Concurrent modification of collections and Java 5

If you have worked with iterators and collections in a multi-threaded environment, then you have probably dealt with the ConcurrentModificationException. If not, then you really need to read this! [<--customary Saturday morning boast]

When you iterate over a collection which is being modified in another thread, the Iterator throws a java.util.ConcurrentModificationException. And rightly so. Regardless of whether you are invoking a next, previous, add, set or remove operation in the first thread, the Iterator chooses a fail-fast approach to interrupt the proceedings. If you delve into the source of the AbstractList in J2SE 1.4.2 for instance, here's kind of what Josh Bloch has written

public Object next() {

	checkForComodification();

	try {

	   Object next = get(cursor);

	   lastRet = cursor++;

	   return next;

	} catch(IndexOutOfBoundsException e) {

	   checkForComodification();

	   throw new NoSuchElementException();

	}

}



// a few lines of code later...



final void checkForComodification() {

	if (modCount != expectedModCount)

	throw new ConcurrentModificationException();

}

The protected transient int modCount indicates the number of times the list has been structurally modified. Each add call in ArrayList (which sub-classes the AbstractList) increments this by 1.

So how do you work around this?

There are a number of ways you can tackle this issue. You could use the pessimistic approach of enclosing your code within the synchronized block or even using a synchronized collection

List bunchOfSlowMovers = Collections.synchronizedList(list);



synchronized (bunchOfSlowMovers) {

   Iterator i = list.iterator(); 

   while (i.hasNext()) {

      foo(i.next());

   } 

}

I personally wouldn't recommend this. Although these steps assure integrity of data, they also introduce a bottleneck in the system. If you have an optimistic outlook, you may likely think that ConcurrentModificationException encounters are few and far between. This could prompt you to surround your iteration code with a try-catch block where you handle the ConcurrentModificationException instance by iterating the collection again.

private HokieBean getTheHokiestOfThemAll(List list) {

   try {

      Iterator iter = list.iterator();

      while (iter.hasNext()) {

           HokieBean hokieBean = (HokieBean)iter.next();

           if (bar(hokieBean)) {

               return hokieBean;

           }

      }    



   } catch (ConcurrentModificationException cme) {

       // for those rare occasions... 

       return getTheHokiestOfThemAll(list);

   }



}

Of course exception handling and recursion have their overheads and this scheme is useful only if ConcurrentModificationException instances are indeed rare.

The Java Collections framework has seen some enhancements in Java 5 (Tiger), most notably the addition of new concurrent utilities, apart from features like Generics, Autoboxing and Unboxing. Let's look at some of them.

java.util.concurrent.ConcurrentHashMap
This new map class extends the java.util.AbstractMap and implements the java.util.concurrent.ConcurrentMap interface. It supports full concurrency of retrievals and adjustable expected concurrency for updates. All operations are thread-safe and retrieval operations do not entail any locking. Its iterators do not throw ConcurrentModificationException. A concurrencyLevel setting dictates the estimated number of concurrently updating threads and the implementation class performs internal sizing to accomodate that number of threads. This may not completely solve our problem so lets keep looking.

java.util.concurrent.CopyOnWriteArrayList
The CopyOnWriteArrayList is a thread-safe version of the ArrayList where operations like add and set are performed on a copy of the underlying array rather than the actual array itself. In most cases, this may incur some performance costs but it can be beneficial when list traversals happen more often than updates. If you use the CopyOnWriteArrayList, you can do away with the synchronized block. Its iterator will never throw the ConcurrentModificationException because the underlying array never changes for the lifetime of the iterator, but you cannot invoke add and set on the iterator itself. That's not too bad, eh?

So we have at least 2 reasonable solutions to the problem of concurrent modification of collections. If you know of alternate approaches or ideas for the future, please leave a comment.

Email this | Bookmark this