A Tale of Two Iterators: Competitive Modification Strategies in Java

The author of the note is Grzegorz Mirek, a software developer from Krakow (Poland). He started developing in Java about 6 years ago, while still at university, and since that time he has been tirelessly polishing his skills in this area. He is particularly interested in JVM performance and optimization, which is what he mainly writes about on his blog . Some of the most popular Java interview questions include: What is the difference between fail-fast and fail-safe iterators? The most simplified answer to this is: A fail-fast iterator throws a ConcurrentModificationException if the collection changes during iteration, but a fail-safe iterator does not. Although this sounds quite meaningful, it remains unclear what the interviewer means by fail-safe? The Java Language Specifications do not define this term in relation to iterators. However, there are four competitive modification strategies.

Competitive modification

First, let's define what competitive (or parallel) modification is. Let's say we have a collection and when the iterator is active, some changes occur that do not come from this iterator. In this case, we get a competitive modification. Let me give you a simple example: let's say we have several threads. The first thread iterates, and the second thread inserts or removes elements from the same collection. However, we can get a ConcurrentModificationException when running in a single-threaded environment:

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Fail-fast

The above code fragment is an example of a fail-fast iterator. As you can see, a ConcurrentModificationException was thrown when trying to retrieve the second element from the iterator . How does an iterator know that the collection has been modified since it was created? For example, the collection might have a date/time stamp, say lastModified . When creating an iterator, you should copy this field and store it in an iterator object. Then, each time the next() method is called , you will simply compare the lastModified value from the collection with the copy from the iterator. A very similar approach is used, for example, in the implementation of the ArrayList class . It has an instance variable modCount that stores the number of times the list has been modified:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

It is important to note that fail-fast iterators operate on a best-of-breed basis, meaning that there is no guarantee that a ConcurrentModificationException will be thrown in the event of a concurrent modification. So you shouldn't rely on them - rather, they should be used to detect errors. Most non-concurrent collections provide fail-fast iterators.

Weak Consistency

Most concurrent collections in the java.util.concurrent package (such as ConcurrentHashMap and most Queue ) provide weakly consistent iterators. The meaning of this term is very well explained in the documentation :

• They can be processed concurrently with other operations
• They never throw a ConcurrentModificationException
• They are guaranteed to traverse existing elements at the time the iterator was created exactly once, and can (but are not required to) reflect subsequent modifications.

Snapshot

With this strategy, the iterator is associated with the state of the collection at the time of its creation - this is a snapshot of the collection. Any changes made to the original collection result in the creation of a new version of the underlying data structure. This leaves our snapshot unchanged, so it doesn't reflect changes to the collection that occurred after the iterator was created. This is the good old copy-on-write (COW) technique . It completely solves the problem of concurrent modifications, so a ConcurrentModificationException is not generated with this approach. Additionally, iterators do not support operations that change elements. Copy-on-write collections tend to be too expensive to use, but it makes sense to use them if changes occur much less frequently than iterator traversals. Examples are the CopyOnWriteArrayList and CopyOnWriteArraySet classes .

Undefined behavior

You may encounter undefined behavior in legacy collection types such as Vector and Hashtable . Both have standard fail-fast iterators, but in addition, they allow the use of implementations of the Enumeration interface , and they do not know how to behave in case of concurrent modification. You may encounter some elements being repeated or missing, or even some strange exceptions. It's better not to play with them!