JProfiler Get rid of your performance problems and memory leaks! Modern Garbage Collection Tuning Java Performance Training Courses COURSES AVAILABLE NOW. We can provide training courses to handle all your Java performance needs Java Performance Tuning, 2nd ed The classic and most comprehensive book on tuning Java Java Performance Tuning Newsletter Your source of Java performance news. Subscribe now! Enter email: Training online Threading Essentials course JProfiler Get rid of your performance problems and memory leaks!

What is a mysterious field called modCount doing in the List Iterator classes? How can we efficiently handle iterating over collections when another thread may be updating the collection at the same time? Read on in our "Fast Fail Iterators" article from our "Learning From Code" series.

Published January 2004, Authors Jack Shirazi, Kirk Pepperdine

Page 1 of 2
next page: Locking the page and other scenarios

The "Learning From Code" series

In the "Learning From Code" series, we examine existing code for techniques that offer a performance advantages. Such advantages have already been tried and tested, and often provide very interesting tuning techniques.

AbstractList

The AbstractList class in the java.util package is normally only examined by developers intending to implement a List class. AbstractList is an abstract class, which means it is a class which provides a partial implementation of some type of behavior, and is designed to be extended by subclasses which will provide the complete implementation. In particular, AbstractList provides a skeletal implementation of the java.util.List interface, and is designed for subclasses which will be backed by a random access data structure such as an array (e.g. Object[]). ArrayList is one such subclass of AbstractList.

Iterators

One service provided by AbstractList is the iterator, or rather the iterators, which are required by the java.util.List interface. The java.util.List interface specifies three methods which return iterators:

    Iterator iterator();
    ListIterator listIterator();
    ListIterator listIterator(int index);

AbstractList provides implementations for all three iterator methods, and also provides class implementations for the Iterator objects. One aspect of these Iterator classes is of particular interest to us, a mysterious field called modCount. The following behavior is described in the AbstractList comments:

[Talking about modCount]
     * If the value of this field changes unexpectedly, the iterator (or list
     * iterator) will throw a ConcurrentModificationException in
     * response to the next, remove, previous,
     * set or add operations.  This provides
     * fail-fast behavior, rather than non-deterministic behavior in
     * the face of concurrent modification during iteration.

How does this work, and why is it useful?

Concurrency Problems

The issue under consideration is iterating through a collection while that collection may be being changed by another thread. This is a concurrency issue. In particular, what happens if thread 1 is iterating through a collection, and thread 2 changes the size of the collection at the same time, by adding or deleting an element. This is a classic concurrency problem which can result in one of four scenarios.

Corruption

The first scenario is to just do nothing about this concurrency problem. To frame this in terms of a database analogy, it would be the equivalent of performing updates to your database outside of the bounds of a transaction. If you are lucky, the iteration in thread 1 will occur before or after the collection update in thread 2, and nothing bad happens. However you obviously have a race condition, and it is likely that at some point the iteration will occur concurrently with the update. Then the outcome is undefined, usually leading to either a data corruption or some undefined error. For example, if one were to perform a concurrent delete, this may result in the iterator trying to access the element beyond the end of the now shorter collection, causing a IndexOutOfBoundsException. The other case to consider is a concurrent addition which may result in one element of the collection being missed out over the iteration. It also equally likely that other problems could occur, such as a NullPointerException due to the collection being resized requiring a new underlying array to be created and copied into. Normally, this "do nothing about it" scenario is not an acceptable solution. Returning to our analogy, current database technology imposes the constraint that one cannot update the database outside of the bounds of a transaction. Instead, it requires us to lock the resources while the update is being performed.

Continued on next page

Page 1 of 2
next page: Locking the page and other scenarios