Behaviour of CopyOnWriteArrayList

Question

Javadocs of CopyOnWriteArrayList says

A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.

I am confused now when will other threads see changes present in this fresh copy? Does this mean there will be number of copies of the underlying array equal to the number of mutations of the collection? If not so when are the changes of these individual copies are transferred to underlying array so that other threads can see them?

Answer 1

The idea here is that whenever you add or remove to the CopyOnWriteArrayList, the underlying array is basically copied with the modification.

Does this mean there will be number of copies of the underlying array equal to the number of mutations of the collection

Yes, for every thread that updates the ArrayList all other threads holding an older copy will in essence be referencing a different array.

when are the changes of these individual copies are transferred to underlying array so that other threads can see them?

An array you are looking at currently (lets say your iterator) will never change. When you read from an array you are reading it as it was when you started reading. If the CopyOnWriteArrayList changes by another thread, the array you're currently observing will not be effected.

To get the most updated version do a new read like list.iterator();

That being said, updating this collection alot will kill performance. If you tried to sort a CopyOnWriteArrayList you'll see the list throws an UsupportedOperationException (the sort invokes set on the collection N times). You should only use this read when you are doing upwards of 90+% reads.

Answer 2

The implementation for copy on write array list uses the underlying array and accesses it using the setter and getter methods.

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {
    return array;
}

/**
 * Sets the array.
 */
final void setArray(Object[] a) {
    array = a;
}

So for add, set operations it creates copies of the current array (using getArray) and the adds the element and returns back the updated array (using setArray).

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();
    }
}

yes the threads that have accessed the arraylist before add or set methods will be having a stale copy of data (which is fine if you can handle some degree of stale data, as CopyOnWriteArrayList is designed with this idea that traversal operations will outnumber adding or update operations) and all the threads that will create an iterator or use get operation will have the latest data of the arrayList.

public E get(int index) {
    return get(getArray(), index);
}

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

here getarray will give the latest state of the arrayList.