Background: Poll – #1 – #2 – #3

It’s fortunate that there are lots of ways to screw up concurrency because I’ve still got a lot of these entries left. :) Today’s installment will cover one of the most common exceptions encountered with the collections library.

Collections from JDK 1.4 and earlier all use “fail-fast” iterators. These iterators are designed to be valid until the original collection is modified. At that point, they “fail fast” and will throw ConcurrentModificationException. The most common way to encounter this is to remove elements from the collection while walking through the iterator. [source:java]

List list = …

while(Item item : list) {

if(isOld(item)) {

list.remove(item);

}

}

[/source]

After the point where the first remove() is called, the iterator is now invalid. It’s quite possible to test this with 0 or 1 item in the list and see no problem, but as soon as two or more items are in the list, this is guaranteed to throw a ConcurrentModificationException. Of course, it’s quite possible that the actual code is more complicated and the remove() is separated through several method calls from the iteration. Note the scenario above is single-threaded yet causes the error.

Stepping back a bit, we need to consider a couple possible reasons you might be doing this. One is that you are actually in single-threaded code and need to modify a collection while iterating through it. If so, then the best way to do this is by using methods on the iterator itself: [source:java]

List list = …

Iterator iterator = list.iterator();

while(iterator.hasNext()) {

Item item = iterator.next();

if(isOld(item)) {

iterator.remove();

}

}

[/source]

This mechanism will not throw a ConcurrentModificationException as we are safely modifying the list through the iterator. You can also use the more capable ListIterator if you happen to be using a list. ListIterator lets you change the item under iteration and walk forward and backward through the list.

Another option you see frequently is to iterate through a copy of the list under iteration and remove from the original list. Because two lists are being used, the iterator is not affected by the modifications to the original list. [source:java]

List list = …

List listCopy) {

if(isOld(item)) {

list.remove(item);

}

}

[/source]

Of course, copying has the large down-side of needing to copy the list, which is O(n) and can be expensive if the list is large. In general, for single-threaded use cases, removing through an iterator is far preferable to avoid the copy. In a multi-threaded scenario, the copy technique might be better (assuming the collection is properly synchronized) to avoid modifying while iterating.

But an even better solution might be to use one of the concurrent collections in the java.util.concurrent package. The collections in this package are designed for concurrency and they do not use fail-fast iterators. Rather, they use other iterator styles that allow for concurrent modification (and thus don’t throw ConcurrentModificationException). Collections like CopyOnWriteArrayList or CopyOnWriteArraySet use what is known as a “snapshot” iterator. These collections internally switch to a new copy of the data when the collection is modified in any way. Prior iterators that are walking over the collection see a “snapshot” of the data at the time the iterator was created. In these data structures, writes are assumed to be rare and reads/iteration frequent so it is worth the cost of creating the copy on write.

Other collections, most notably ConcurrentHashMap, use what’s known as a “weakly consistent” iterator. Weakly consistent iterators actually allow you to iterate through the data while it’s being updated. So, some changes made during iteration will be see by the iterator. Here “some” implies the “weakly consistent” part of the name. This kind of iterator guarantees that you see all elements at the time of iterator creation and may see any changes made after creation.

One other important and related thing to mention is that using an iterator from a synchronized wrapper is NOT sufficient to address this problem. For example this won’t work: [source:java]

List originalList = new ArrayList();

…fill originalList…</p>

// BROKEN

List list = Collections.synchronizedList(originalList);

while(Item item : list) {

// stuff

}

[/source]

The problem here is that an iterator from the synchronized wrapper collection is NOT thread-safe or synchronized against the wrapped collection. To maintain thread-safety, the javadoc notes that you MUST synchronize against the returned list when you iterate: [source:java]

List originalList = new ArrayList();

List list = Collections.synchronizedList(originalList);

synchronized(list) {

while(Item item : list) {

// stuff

}

}

[/source]

The first time I encountered this, I was surprised by it, so watch out for it!