How Concurrent modification exception is handled internally by CopyOnWriteArrayList/ConcurrentHashMap?

Question

I want to understand internally how concurrent modification exception is handled in concurrent collections like ConcurrentHashMap and CopyOnWriteArrayList.

There are so many blogs available in internet which suggest to use these two data structures to avoid concurrent modification exception. But nothing explains , how this exception is internally handled by concurrent collection.

Can someone give more insights on this? I need some detailed explanation.

Answer 1

Here is the add() method definition of ArrayList and CopyOnWriteArrayList.

ArrayList:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

CopyOnWriteArrayList:

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

From the above code, it is clear that CopyOnWriteArrayList takes lock before modifying the map. Here I have just posted the code of the add method. If you look on the code of remove() / addAll() or any method which modifies the List structurally you can see that it takes lock before modifying the collection. Also ArrayList's iterator's method such as next()/remove() check for modification but for CopyOnWriteArrayList's iterator's method does not check for the modification. For example :

ArrayList iterator next() method:

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

CopyOnWriteArrayList iterator next() method:

    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

Answer 2

This will, right now, answer how CopyOnWriteArrayList avoids the need for a ConcurrentModificationException.

When you modify the collection the CopyOnWriteArrayList does two things

1. It prevents other threads from modifying the collection via locking
2. Copies all the elements in the current CopyOnWriteArrayList into a new array and then assigns that new array to the class's array instance

So how does that prevent a CME? A CME in standard collections will only be thrown as a result of iterating. The exception gets thrown if, while iterating over the collection, an add or remove is executed on the same collection instance.

The CopyOnWriteArrayList's iterator assigns the current array as a final field snapshot of the collection and uses that for iteration. If another thread (or even the same thread) tries to add to the CopyOnWriteArrayList then updates will be applied to a new copy and not the snapshot one we are currently iterating.

For instance, we know the add method looks like

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

Notice the thread local newElements assignment being made, when that is completed it will set to the class instance volatile array.

Then comes the iterator, it's defined as

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

So when iterating, we are reading whatever was the array prior to any modifications, and since no other thread can modify the snapshot we are looking at a ConcurrentModificationException cannot happen.

Answer 3

The literal answer to your question is not very interesting. ConcurrentHashMap and CopyOnWriteArrayList don't throw ConcurrentModificationException because they don't include code to throw it.

It's not like ConcurrentModificationException is some low-level intrinsic thing. ArrayList and HashMap, among other collection classes, throw ConcurrentModificationException to help you. They have to include extra code to try to detect concurrent modifications, and extra code to throw an exception. ConcurrentModificationException is thrown when one of those classes detect that there is a bug somewhere that is causing an unsafe modification to your collection.

Classes that support safe concurrent modification don't throw ConcurrentModificationException because they don't need to.

If you're trying to debug a ConcurrentModificationException, there are plenty of other questions that help answer that:

• Why is a ConcurrentModificationException thrown and how to debug it
• Why doesn't this code throw a ConcurrentModificationException?