java - Difference between CopyOnWriteArrayList and synchronizedList

Question

As per my understanding concurrent collection classes preferred over synchronized collections because the concurrent collection classes don't take a lock on the complete collection object. Instead they take locks on a small segment of the collection object.

But when I checked the add method of CopyOnWriteArrayList, we are acquiring a lock on complete collection object. Then how come CopyOnWriteArrayList is better than a list returned by Collections.synchronizedList? The only difference I see in the add method of CopyOnWriteArrayList is that we are creating copy of that array each time the add method is called.

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

Answer 1

As per my understanding concurrent collection classes preferred over synchronized collection because concurrent collection classes don't take lock on complete collection object. Instead it takes lock on small segment of collection object.

This is true for some collections but not all. A map returned by Collections.synchronizedMap locks the entire map around every operation, whereas ConcurrentHashMap locks only one hash bucket for some operations, or it might use a non-blocking algorithm for others.

For other collections, the algorithms in use, and thus the tradeoffs, are different. This is particularly true of lists returned by Collections.synchronizedList compared to CopyOnWriteArrayList. As you noted, both synchronizedList and CopyOnWriteArrayList take a lock on the entire array during write operations. So why are the different?

The difference emerges if you look at other operations, such as iterating over every element of the collection. The documentation for Collections.synchronizedList says,

It is imperative that the user manually synchronize on the returned list when iterating over it:

    List list = Collections.synchronizedList(new ArrayList());
    ...
    synchronized (list) {
        Iterator i = list.iterator(); // Must be in synchronized block
        while (i.hasNext())
            foo(i.next());
    }

Failure to follow this advice may result in non-deterministic behavior.

In other words, iterating over a synchronizedList is not thread-safe unless you do locking manually. Note that when using this technique, all operations by other threads on this list, including iterations, gets, sets, adds, and removals, are blocked. Only one thread at a time can do anything with this collection.

By contrast, the doc for CopyOnWriteArrayList says,

The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created.

Operations by other threads on this list can proceed concurrently, but the iteration isn't affected by changes made by any other threads. So, even though write operations lock the entire list, CopyOnWriteArrayList still can provide higher throughput than an ordinary synchronizedList. (Provided that there is a high proportion of reads and traversals to writes.)