Why is the design criteria for ConcurrentModificationException chosen only to be structural modification

Question

I do understand that ConcurrentModificationExcpetion is thrown whenever there is a structural modification of the underlying collection after an iterator has been created. This seems to be a design decision.

I was wondering why update, through set() methods, is not considered for CME? Ultimately, the collection is getting updated and if iterator is created, traversal could still result in inconsistent results.

Answer 1

It is impossible to know the exact reasons for the design decision unless you were actually involved in making them.

I surmise that the reason might be that the iterator is designed to iterate the collection, rather than the values in the collection.

In other words, the iterator is like a "pointer" which will just be moved to point to each "space" in the collection in turn. By knowing something about the "shape" of the collection when the iterator is constructed, you know how to move the pointer to point to the next space in the collection.

If the value stored in a space changes, it doesn't really matter: that space and all other spaces in the collection are left unchanged.

However, if you change the shape of the collection via a structural modification, you've basically invalidated any assumptions that you have about where that pointer is pointing; short of doing something very clever, you may as well just give up and throw an exception.

Answer 2

Ultimately, the collection is getting updated and if iterator is created, traversal could still result in inconsistent results.

Actually, I think that the reason is that the set operations won't lead to inconsistent results. The code iterating the collection will either see the results of the set call's modification ... or not ... in a highly predictable fashion. And the code is guaranteed to still see each other element of the collection (i.e. apart from the one that you "set") exactly once.

By contrast, structural modifications on typical non-concurrent collections can cause the collection entries / elements to move around. For example:

• An insertion or deletion in an ArrayList causes the elements in the backing array to change position.

• An insertion in a HashMap or HashSet can cause resizing which causes the hash chains to be reconstructed.

In both cases, the structural modification can lead to elements being skipped, or seen more than once.

Answer 3

Please find my comments to your assumptions below.

I do understand that ConcurrentModificationException is thrown whenever there is a structural modification of the underlying collection after an iterator has been created.

Not exactly. The ConcurrentModificationException is actually thrown when the iterator attempts to fetch the next value and there has been a structural change in the underlying collection. (I want to stress that the ConcurrentModificationException is not thrown when invoking i.e. add or remove on the underlying collection).

Then, concerning your last assumption:

Ultimately, the collection is getting updated and if iterator is created, traversal could still result in inconsistent results.

I don't think this is correct. How could traversal still result in inconsistent results? If i.e. you modify the value at the i-th position of a list, you'll immediately see this change. The list is in fact modified, but not structurally modified. Only the value at the i-th position changes, but not the structure of the list (i.e. ArrayList's underlying array won't incur the risk of being resized, LinkedList won't allocate a new node, etc).

Finally, with regard to this sentence:

This seems to be a design decision.

Absolutely. It is 100% a design decision, and while I haven't been part of it, I'm certain that it has been driven by the aim of avoiding inconsistencies when traversing the underlying collection. Better than ending up with unexpected or inconsistent data, throw an exception as early as possible and let the user know.

However, the docs also mention that fail-fast iterators throw ConcurrentModificationException on a best-effort basis.

For example, consider the following code:

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    try {
        Integer next = iterator.next();
        System.out.println("iterator.next() = " + next);

        System.out.println("BEFORE remove: " + list);
        list.remove(0);
        System.out.println("AFTER remove: " + list);

    } catch (ConcurrentModificationException e) {

        System.out.println("CME thrown, ending abnormally...");
        System.exit(1);
    }
}

Here we are attempting to remove the first element of the list while iterating over it. Upon execution, you'll see the following output:

iterator.next() = 1
BEFORE remove: [1, 2, 3]
AFTER remove: [2, 3]
CME thrown, ending abnormally...

This is the expected behavior. A ConcurrentModificationException is thrown when the iterator attempts to fetch an element from the list for the second time. This is because the implementation detects that a structural change has been made since the iterator was created. Thus, iterator.next() throws a CME.

However, as fail-fast iterators are not guaranteed to always throw a ConcurrentModificationException, but to do it only on a best-effort basis, there's a way to trick the implementation. Consider the code below, which is a modified version of the previous snippet (if you execute it, be warned that it will take some time until it finishes):

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));

int structuralChanges = 0;

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    try {
        Integer next = iterator.next();
        System.out.println("iterator.next() = " + next);

        System.out.println("BEFORE remove: " + list);
        list.remove(0);
        System.out.println("AFTER remove: " + list);
        structuralChanges++;

        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            list.add(i);
            structuralChanges++;
            list.remove(list.size() - 1);
            structuralChanges++;
        }
        list.add(0);
        structuralChanges++;

        System.out.println("Structural changes so far = " + structuralChanges);

    } catch (ConcurrentModificationException e) {

        System.out.println("CME NEVER thrown, so you won't see this message");
        System.exit(1);
    }
}

System.out.println("AFTER everything: " + list);
System.out.println("Program ending normally");

Here we are again removing the first element of the list while iterating it, but before the iterator fetches the next element, we're doing millions of structural modifications. In fact, we are doing Integer.MAX_VALUE * 2 + 1 structural modifications, if we consider all the list.add(i) and list.remove(list.size() - 1) calls inside the for loop, along with the list.add(0) call immediately after the for loop.

Additionally, we're keeping track of all structural modifications via the structuralChanges variable, which is incremented immediately after each structural modification.

Upon execution of the code above, you'll see the following output:

iterator.next() = 1
BEFORE remove: [1, 2, 3]
AFTER remove: [2, 3]
Structural changes so far = 0
iterator.next() = 3
BEFORE remove: [2, 3, 0]
AFTER remove: [3, 0]
Structural changes so far = 0
iterator.next() = 0
BEFORE remove: [3, 0, 0]
AFTER remove: [0, 0]
Structural changes so far = 0
AFTER everything: [0, 0, 0]
Program ending normally

As the output shows, no ConcurrentModificationException has been thrown.

Besides, after all structural modifications have been made, the value of the structuralChanges variable ends up being 0. This is because it is a variable of type int and it is overflowing and reaching 0 again, after being incremented Integer.MAX_VALUE * 2 + 2 times (Integer.MAX_VALUE * 2 + 1 times due to our artificial for loop and subsequent increment, plus 1 due to the list.remove(0) call of the original code).

Then, after all these Integer.MAX_VALUE * 2 + 2 structural modifications, when we call iterator.next() on the following iteration of the while loop, no ConcurrentModificationException is thrown, ever. We've tricked the implementation, so we can now see what happens to the data internally. (Internally, the implementation keeps track of the structural modifications by keeping an int count, as I've done with my structuralChanges variable).