Java Concurrency Bugs #4: ConcurrentModificationException

11

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.

List<Item> list = …
while(Item item : list) {
if(isOld(item)) {
list.remove(item);
}
}

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:

List<Item> list = …
Iterator<Item> iterator = list.iterator();
while(iterator.hasNext()) {
Item item = iterator.next();
if(isOld(item)) {
iterator.remove();
}
}

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.

List<Item> list = …
List<Item> listCopy) {
if(isOld(item)) {
list.remove(item);
}
}

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:

List<Item> originalList = new ArrayList();
…fill originalList…

// BROKEN
List<Item> list = Collections.synchronizedList(originalList);
while(Item item : list) {
// stuff
}

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:

List<Item> originalList = new ArrayList();
List<Item> list = Collections.synchronizedList(originalList);
synchronized(list) {
while(Item item : list) {
// stuff
}
}

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

Comments

11 Responses to “Java Concurrency Bugs #4: ConcurrentModificationException”
  1. Kutzi says:

    I think it is worth noting that in the multi-threaded case you’re not guaranteed to get a ConcurrentModificationException when modifying/iteration an non-threadsafe collection from different threads (unexperienced readers might have assumed that).

    Non-threadsafe collection cannot provide any guarantees in the multi-threaded case! Even not that they will fail-fast.

  2. Alex says:

    @Kutzi: I assume that you mean that modifications to an unsynchronized collection will have no visibility guarantees in another thread and thus a modification would not necessarily cause a CME. And that is indeed true although it’s probably the least of your worries. :) I was actually planning on talking about visibility in the next installment, so stay tuned.

  3. Eric Burke says:

    One of the most difficult bugs we encounter occurs when using Glazed Lists, and through a complex chain of event listeners, someone modifies one of the lists while an event notification is in progress. Good times!

  4. Alex says:

    @Eric: Yep. I was actually planning on mentioning this in a future installment as well although in a broader context.

  5. ConcurrentModificationException is almost never a concurrency bug (almost always ), so if you’re compiling a collection of most common concurrency bugs, I think this does not belong there.

    One would probably *not* want the extra overhead of concurrent collections just to avoid this issue, in single-threaded code.

  6. Alex says:

    @Dimitris: I agree that CME happens most frequently in a single-threaded scenario due to a misunderstanding of fail-fast iterators. But there are many cases where it occurs in multi-threaded code as well. Eric relayed one in the comments for example. It’s also a useful hook into talking about iterator styles and concurrent collections.

    I agree that you would not want to use a concurrent collection to avoid this issue in single-threaded code, which is why I said “In general, for single-threaded use cases, removing through an iterator is far preferable to avoid the copy.”

  7. Alex, I’m not familiar with Glazed Lists, but I think even Eric’s example is single-threaded (in swing’s thread in particular). To be honest, I’ve never ever encountered this bug in multi-threaded code, although it surely is possible to happen.

    I understand that it would be difficult to support meaningfully (single-threaded) modification in an ArrayList or others, but for example LinkedList’s iterator is just a pity that behaves like this (it could cope perfectly well with in-thread modifications).

    Arbitrary non-thread-safe classes trying to protect as from unsynchronized access (in ‘some’ cases, if we are lucky) is just absurd. Just imagine this approach being taken in any non-thread-safe class. I think Josh’s call was the wrong one in this case, and the exception should have been more honest: it would be better to have something like “ModificationWhileIteratingNotSupportedException” instead of “ConcurrentModificationException”, and just in those collections that indeed couldn’t support this.

  8. I’ve actually had this problem and I went to modify a collection copy. Had I only known about the iterator.remove() method!
    Excellent post!

  9. Paul Linden says:

    Ok, I know this is an old post, but even 11 months later, this series is a great resource. Knowing what can go wrong is a great step towards fixing and avoiding these bugs.

    Anyway, reading over the comments, I decided to answer Dimitris’ comment about this almost never happening in real code.

    I recently worked on a web application (an inhouse content management app) that stored some seldom-changing globally accessible data in a static ArrayList, to avoid having to read it from the db for everyone. This data was mutable, and anyone using the app could delete instances from the db … the delete (or add or modify) operations would also update the ArrayList.

    The number of users was low (maybe 10 at a time, max) and it was unlikely that two would be working on the same operations at the same time, but we did get the occasional CME (a couple of times a month?), resulting in error pages shown to the user, due to this very problem.

    Of course, it was a design problem due to the original developer not thinking about concurrent programming.

  10. Karthik says:

    Hi,

    What happens to these concurrent lists when we say we are iterating the 3rd item on the list but another thread concurrently modifies to insert an item at index 1 so this is before the current element. How does the list behave now?

  11. Alex says:

    @Karthik: Could you be more specific on what kind of collection or map you’re talking about?