Difference between CopyOnWriteArrayList and synchronizedList

Question

According to my understanding, parallel collection classes prefer more synchronized collections, because parallel collection classes do not take locks for the entire collection object. Instead, they take locks on a small segment of the collection object.

But when I checked the add CopyOnWriteArrayList method, we acquire a lock for the complete collection object. Then how is CopyOnWriteArrayList better than the list returned by Collections.synchronizedList ? The only difference that I see in the add CopyOnWriteArrayList method is that we create a copy of this array every 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

For a write (add) operation, CopyOnWriteArrayList uses a ReentrantLock and backs up the data, and the base reference to the volatile array is updated via setArray (Any read operation on the list before setArray returns the old data before adding). Moreover, CopyOnWriteArrayList provides a fault-tolerant snapshot iterator and does not throw a ConcurrentModifficationException when writing / adding.

But when I checked the method of adding the CopyOnWriteArrayList.class method, we find a lock on the full collection object. Then, as it turned out, CopyOnWriteArrayList is better than synchronizedList. The only difference that I see in the CopyOnWriteArrayList add method is that we create a copy of this array every time the add method is called.

• No, the lock is not in the entire Collection object. As stated above, this is a ReentrantLock and is different from an object's internal lock.
• The add method always creates a copy of an existing array and modifies the copy, and then finally updates the volatile array reference, pointing to this new array. And so we have the name "CopyOnWriteArrayList" - makes a copy when writing to it. It also avoids ConcurrentModificationException

Answer 2

1) get and other read operations on CopyOnWriteArrayList not synchronized.

2) CopyOnWriteArrayList iterator never throws ConcurrentModificationException , while the Collections.synchronizedList iterator can throw it.

Answer 3

According to my understanding, parallel collection classes prefer a more synchronized assembly, because parallel collection classes do not take locks for the entire collection object. Instead, it blocks a small segment of the collection object.

This is true for some collections, but not for all. The map returned by Collections.synchronizedMap blocks the entire map around each operation, while ConcurrentHashMap blocks only one hash bit for some operations or may use a non-blocking algorithm for others.

For other collections, the algorithms used, and therefore the tradeoffs, are different. This is especially true for lists returned by Collections.synchronizedList compared to CopyOnWriteArrayList . As you noted, both synchronizedList and CopyOnWriteArrayList lock the entire array during write operations. So why so different?

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

It is imperative that the user manually synchronizes 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 can lead to deterministic behavior.

In other words, iterating over a synchronizedList is not thread safe unless you manually block it. Please note that when using this method, all operations with other threads in this list, including iteration, retrieval, collection, addition and deletion, are blocked. Only one thread at a time can do anything with this collection.

In contrast, the doc for CopyOnWriteArrayList says

The snapshot style iterator method uses a reference to the state of the array at the point at which the iterator was created. This array never changes during the life of the iterator, so no interference is possible, and the iterator is guaranteed not to throw a ConcurrentModificationException . The iterator will not display additions, deletions, or changes to the list since the creation of the iterator.

The operations of other threads in this list can be performed simultaneously, but the iteration is not affected by changes made by other threads. Thus, even though write operations block the entire list, CopyOnWriteArrayList can still provide higher throughput than a regular synchronizedList . (Provided that there is a large share of reads and crawls for writing.)