CopyOnWriteArrayList

0

Concurrent read and write operations

Let us see how ArrayList and synchronized list behave when we have concurrent read and write operations.

  1. ArrayList won’t allow concurrent read and write operations. If it is structurally modified after the iterator is created, it will throw ConcurrentModificationException, else we may see some stale data. They are implemented by associating a modification count with the collection. If the modification count changes during iteration, hasNext() or next() throws ConcurrentModificationException. However, this check is done without synchronization, so we can’t guarantee it in multi-threaded task.
  2. If we synchronize read and write operations, then traversing will become slow as it will have to get the lock first. In concurrent applications where traversals greatly outnumber insertions or removals, synchronized list may not be the right implementation.

CopyOnWriteArrayList

CopyOnWriteArrayList Data structure
CopyOnWriteArrayList
  1. In CopyOnWriteAarrayList, read operations are not synchronized as they work on the snapshot of the internal array so multiple iterators can traverse simultaneously without blocking each other (1, 2, 4).
  2.  All write operations are synchronized. They work on a copy of the backing array (3). Once the write operation is done, the backing array is replaced with the copied one and the lock is released. The backing array is made volatile so the the call that replaces array is atomic (5).
  3. Iterators created after a write operation will be able to see the modified structure (6, 7).
  4. The iterators returned by the copy-on-write collections do not throw ConcurrentModificationException as they work on a snapshot of the array and return the elements exactly as they were at the time the iterator was created, regardless of subsequent modifications (2, 4).

So if iteration are far more frequent than modification, CopyOnWriteArrayList is the right implementation to use.

 

Share.

Leave A Reply