Detecting concurrent modifications?

Question

In a multi-threaded application I'm working on, we occassionally see ConcurrentModificationExceptions on our Lists (which are mostly ArrayList, sometimes Vectors). But there are other times when I think concurrent modifications are happening because iterating through the collection appears to be missing items, but no exceptions are thrown. I know that the docs for ConcurrentModificationException says you can't rely on it, but how would I go about making sure I'm not concurrently modifying a List? And is wrapping every access to the collection in a synchronized block the only way to prevent it?

Update: Yes, I know about Collections.synchronizedCollection, but it doesn't guard against somebody modifying the collection while you're iterating through it. I think at least some of my problem is happening when somebody adds something to a collection while I'm iterating through it.

Second Update If somebody wants to combine the mention of the synchronizedCollection and cloning like Jason did with a mention of the java.util.concurrent and the apache collectons frameworks like jacekfoo and Javamann did, I can accept an answer.

Answer 1

Check out java.util.concurrent for versions of the standard Collections classes that are engineered to handle concurrency better.

Answer 2

You could try using defensive copying so that modifications to one List don't affect others.

Answer 3

Yes you have to synchronize access to collections objects.

Alternatively, you can use the synchronized wrappers around any existing object. See Collections.synchronizedCollection(). For example:

List<String> safeList = Collections.synchronizedList( originalList );

However all code needs to use the safe version, and even so iterating while another thread modifies will result in problems.

To solve the iteration problem, copy the list first. Example:

for ( String el : safeList.clone() )
{ ... }

For more optimized, thread-safe collections, also look at java.util.concurrent.

Answer 4

Collections.synchronizedList() will render a list nominally thread-safe and java.util.concurrent has more powerful features.

Answer 5

Usually you get a ConcurrentModificationException if you're trying to remove an element from a list whilst it's being iterated through.

The easiest way to test this is:

List<Blah> list = new ArrayList<Blah>();
for (Blah blah : list) {
     list.remove(blah); // will throw the exception
}

I'm not sure how you'd get around it. You may have to implement your own thread-safe list, or you could create copies of the original list for writing and have a synchronized class that writes to the list.

Answer 6

Wrapping accesses to the collection in a synchronized block is the correct way to do this. Standard programming practice dictates the use of some sort of locking mechanism (semaphore, mutex, etc) when dealing with state that is shared across multiple threads.

Depending on your use case however you can usually make some optimizations to only lock in certain cases. For example, if you have a collection that is frequently read but rarely written, then you can allow concurrent reads but enforce a lock whenever a write is in progress. Concurrent reads only cause conflicts if the collection is in the process of being modified.

Answer 7

ConcurrentModificationException is best-effort because what you're asking is a hard problem. There's no good way to do this reliably without sacrificing performance besides proving that your access patterns do not concurrently modify the list.

Synchronization would likely prevent concurrent modifications, and it may be what you resort to in the end, but it can end up being costly. The best thing to do is probably to sit down and think for a while about your algorithm. If you can't come up with a lock-free solution, then resort to synchronization.

Answer 8

Depending on your update frequency one of my favorites is the CopyOnWriteArrayList or CopyOnWriteArraySet. They create a new list/set on updates to avoid concurrent modification exception.

Answer 9

See the implementation. It basically stores an int:

transient volatile int modCount;

and that is incremented when there is a 'structural modification' (like remove). If iterator detects that modCount changed it throws Concurrent modification exception.

Synchronizing (via Collections.synchronizedXXX) won't do good since it does not guarantee iterator safety it only synchronizes writes and reads via put, get, set ...

See java.util.concurennt and apache collections framework (it has some classes that are optimized do work correctly in concurrent environment when there is more reads (that are unsynchronized) than writes - see FastHashMap.

Answer 10

This will get rid of your concurrent modification exception. I won't speak to the efficiency however ;)

List<Blah> list = fillMyList();
List<Blah> temp = new ArrayList<Blah>();
for (Blah blah : list) {
     //list.remove(blah);  would throw the exception
     temp.add(blah);
}
list.removeAll(temp);

Answer 11

Your original question seems to be asking for an iterator that sees live updates to the underlying collection while remaining thread-safe. This is an incredibly expensive problem to solve in the general case, which is why none of the standard collection classes do it.

There are lots of ways of achieving partial solutions to the problem, and in your application, one of those may be sufficient.

Jason gives a specific way to achieve thread safety, and to avoid throwing a ConcurrentModificationException, but only at the expense of liveness.

Javamann mentions two specific classes in the java.util.concurrent package that solve the same problem in a lock-free way, where scalability is critical. These only shipped with Java 5, but there have been various projects that backport the functionality of the package into earlier Java versions, including this one, though they won't have such good performance in earlier JREs.

If you are already using some of the Apache Commons libraries, then as jacekfoo points out, the apache collections framework contains some helpful classes.

You might also consider looking at the Google collections framework.

Answer 12

You can also synchronize over iteratins over the list.

List<String> safeList = Collections.synchronizedList( originalList );

public void doSomething() {
   synchronized(safeList){
     for(String s : safeList){
           System.out.println(s);

     }
   }

}

This will lock the list on synchronization and block all threads that try to access the list while you edit it or iterate over it. The downside is that you create a bottleneck.

This saves some memory over the .clone() method and might be faster depending on what you're doing in the iteration...