Monday, February 8, 2010

Concurrent Modification Exception

I ran into a ConcurrentModificationException (CME) during stress testing.
What does CME actually mean?
It means that you've modified (add, remove, update) your Collection while you've been iterating over it (usually in a multi-threaded fashion, but it can occur in a single thread that modifies while iterating).

A few more things to note about CME:
Best effort detection
- If you see a CME printout, first off, consider yourself lucky, CMEs are thrown only in best effort. In another universe, the concurrent modification would not have been detected, causing your collection to become corrupted, instead of fast-failing with a CME.

IDing the problem - Like deadlocks, CME's are easy to pinpoint once you inspected the exception's stack trace.

Avoiding CME:

  1. ListIterator
    To modify a collection by the same thread that is currently iterating on it, use a ListIterator that will allow you to perform both.
    Drawbacks - single thread solution only.

  2. Naive solution: Synchronizers
    Use locks to for mutually excluding traversal and modification operations.
    Advantages - easy to code.
    Drawbacks - very long lock periods while iterating.

  3. CopyOnWrite
    Take advantage of the Java.util.concurrent collections like: CopyOnWriteArrayList, CopyOnWriteArraySet. If you require a map then grab CopyOnWriteMap from Apache (this guys have been doing Sun's dirty work for years now).
    Advantages - very good reading performance (no locks are used, instead visibility is obtained via map member volatility).
    Drawbacks - very bad write performance on large maps.
    Conclusion - use for seldom mutating collections.

  4. toArray()
    toArray will create a new array holding a copy of your Set (Map.keySet() for a Map).
    You can then iterate over the array, freely modifying the original collection (the array doesn't change of course).
    Advantages - write operations are cheap.
    Disadvantages - copying the entire set could be expensive if it occurs too often, and/or the set is very large.

  5. Concurrent Collections
    If you want to go heavyweight, consider using: ConcurrentHashMap (or one of its package friends).
    Once you create an iterator over a ConcurrentHashMap (CHM), it does not freeze the collection for traversal, updates to the collection may or may not appear during the traversal (weakly consistent).

The approach I ended up taking
My use case was seldom modifying a ~ten items cache. A copyonwrite map was what I used.
In other cases I had, ConcurrentHashMap was the easiest solution (though make sure your code can live in peace with the CHM weak consistency property).

[caption id="attachment_227" align="alignleft" width="200" caption="Best pic idea I could think of to visualize Threads :)"][/caption]

No comments:

Post a Comment