CODEWITHSUNDEEP
javadata-structurescollectionsconcurrency
chamibuddhika
chamibuddhika

Reputation: 1439

Behaviour of CopyOnWriteArrayList

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?

Upvotes: 17

Views: 8318

Answers (2)

confused
confused

Reputation: 161

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.

Upvotes: 2

John Vint
John Vint

Reputation: 40256

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.

Upvotes: 21

Related Questions