Even a chimp can write code

Saturday, September 18, 2004

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

12 Comments:

  • This was very informative and concise. Thanks!

    By Anonymous Anonymous, at June 9, 2005 at 9:17 AM  

  • Hmmm ... interessting. The java api description for 1.4 says that you must use the returned synchronized collection instead of the original collection ... which does not work either ...

    http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#synchronizedCollection(java.util.Collection)


    Collection c = Collections.synchronizedCollection(myCollection);
    ...
    synchronized(c) {
    Iterator i = c.iterator(); // Must be in the synchronized block
    while (i.hasNext())
    foo(i.next());
    }

    your code looks like this, using the original collection.

    List bunchOfSlowMovers = Collections.synchronizedList(list);synchronized (bunchOfSlowMovers) { Iterator i = list.iterator(); while (i.hasNext()) { foo(i.next()); } }

    any suggestions ?

    Regards,
    Mark

    By Anonymous Mark, at November 17, 2005 at 2:08 AM  

  • A wonderful well-written article!!!

    Thanks a lot!

    By Anonymous Anonymous, at October 17, 2006 at 4:36 PM  

  • Very useful information. and I like the style too.

    By Anonymous Anonymous, at January 12, 2007 at 12:41 PM  

  • This is exactly the information I was looking for.. many thanks! :-)

    By Anonymous Steve, at April 15, 2008 at 5:10 PM  

  • The code mark quoted works, but I personally wouldn't even keep a reference to the original list around. You can do anything you want to the original list as long as it's inside a block synchronized on the returned list. The thing about the returned list is that all its methods are synchronized, so they're automatically thread-safe.

    By Blogger PJ, at May 6, 2008 at 10:19 PM  

  • hey perfect.. that was really helpful, thanks a lot

    By Anonymous rashmi, at August 7, 2008 at 7:03 AM  

  • Very helpful - thanks!

    By Anonymous Andrew, at March 6, 2009 at 3:55 PM  

  • Ooo ooo ooo! Ah ah ah! Kyaaaagh!! Uggh uggh!

    By Blogger Jim Ryan, at October 20, 2009 at 12:48 PM  

  • I am facing this problem.I used synchrozied concept....i hope the second option will help me i mean concurrenthashmap.....

    By Anonymous Mohan, at January 19, 2010 at 12:28 AM  

  • Real helpful. Cheers.

    By Blogger Luc Boudreau, at February 24, 2010 at 2:59 PM  

  • Thank you very much. It really helps me. I choose to use CopyOnWriteArrayList instead of ArrayList.

    By Blogger Jay, at November 4, 2010 at 3:57 AM  

Post a Comment | Home | Inference: my personal blog