In depth analysis of the source code design of CopyOnWriteArrayList

CopyOnWriteArrayList provides thread safety and scalability

Scalability refers to the performance of an application's throughput as its workload and available processing resources increase.

A scalable program can handle a larger workload by using more processors, memory, or I/O bandwidth.

Locking a shared resource for exclusive access creates a scalability bottleneck -- it prevents other threads from accessing that resource, even if there are idle processors that can call those threads * *. In order to achieve scalability, we must eliminate or reduce our dependence on exclusive resource locks**

CopyOnWriteArrayList

CopyOnWriteArrayList is java1 Version 5 provides a thread safe ArrayList variant. ArrayList has the fast fail feature. It is a value. During traversal, if the contents of ArrayList are modified, a ConcurrentModificationException will be thrown.

This situation becomes particularly prominent in a multithreaded environment. Using subscript instead of iterator will bring a problem. There is no separation between reading and writing. Write operation affects the accuracy of reading, and even leads to IndexOutOfBoundsException. Instead of directly traversing the list, copy the list to an array and then traverse.

Copy on write: naturally, when performing a write operation, copy the original data to a new array. There are three main methods related to the write operation: add, remove and set. In each add operation, the array is copied to a copy. This is the principle of copy on write. What are the advantages of copy on write and copy on read and how to choose?

If the traversal operation of a list is more frequent than the write operation, CopyOnWriteArrayList should be used. If the write operation of a list is more frequent than the traversal operation, the read-time copy should be considered.

Principle analysis of CopyOnWriteArrayList source code

1 usage scenario

• It is used to replace Vector and synchronized list. It has better concurrency performance than Vector and synchronized list
• The copy on write concurrency container also includes CopyOnWriteArraySet, which is used to replace the synchronization Set
• It is mainly applicable to those who have fast requirements for reading operation, that is, fast reading and slow writing

2 reading and writing rules

• We all know that the rule of read-write lock is: read-write mutual exclusion, write mutual exclusion
• CopyOnWrite has made an upgrade: the read is completely unlocked, and the write will not block the read operation. Only the write and write need to wait synchronously. (read and write are not mutually exclusive, write and write are mutually exclusive)
• In addition, we can delete and modify elements in the iteration. Let's see a case

/**
 * CopyOnWriteArrayList You can modify the contents of the array in the iteration, but ArrayList can't
 * @author yiren
 */
public class CopyOnWriteArrayListExample01 {
    public static void main(String[] args) {
        // ArrayList<String> list = new ArrayList<>();
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(list);
            String next = iterator.next();
            System.out.println(next);

            if (next.equals("2")) {
                list.remove("3");
            }

            if (next.equals("4")) {
                list.add("3 add");
            }
        }
    }
}

[1, 2, 3, 4, 5]
1
[1, 2, 3, 4, 5]
2
[1, 2, 4, 5]
3
[1, 2, 4, 5]
4
[1, 2, 4, 5, 3 add]
5

Process finished with exit code 0

• The result output does not correspond to the elements in the list. CopyOnWriteArrayList is this idea. You can change it in the iteration, but you can change yours. I iterate mine. Its internal copy mechanism is different from the iterator of ArrayList. There is a modCount value in ArrayList to judge whether you modify it during the iteration

  final void checkForComodification() {
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
          }
  
  

  • The expectedModCount is obtained from the ArrayList object before the iterator is created. If the original ArrayList object is deleted from the left and right, the modCount will be different from the expectedModCount, and then it will fail quickly.

3 implementation principle

• CopyOnWrite: during the write operation, it will first copy a copy to the new memory, and then modify it. After the modification is completed, point the original pointer to the past, and then OK.
• This process leads to that when you iterate, the iterated memory is still the value in the old memory, not the modified value
• So note: each modification or addition will create a new copy to separate reading and writing, while the old memory data will not change.
• Let's look at another case

/**
 * @author yiren
 */
public class CopyOnWriteArrayListExample02 {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        list.add("1");
        list.add("2");
        list.add("3");
        Iterator<String> itr1 = list.iterator();
        list.add("4");
        Iterator<String> itr2 = list.iterator();

        itr1.forEachRemaining(System.out::print);
        System.out.println();
        itrforEachRemaining(System.out::print);
    }
}

123
1234
Process finished with exit code 0

• In the use of CopyOnWrite iterator, even if you modify it, its iteration content only depends on the data content of the collection when it is created. It does not depend on whether the actual list is modified.
• Therefore, data expiration may occur in the iterative process

4 shortcomings

• Data consistency: as mentioned above, it * * can only ensure the consistency of final data, but not the real-time consistency of data** If you need to write real-time response, it is not recommended.
• Memory waste: CopyOnWrite's write is a copy mechanism. When writing, one copy will be copied. This is a waste of memory

5 source code analysis

• Firstly, CopyOnWriteArrayList is a list collection of arrays, and its basic storage is arrays

    private transient volatile Object[] array;

• When multiple threads write at the same time, it is ReentrantLock.

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

• Its creation, constructor can be imagined, that is to give an empty array.

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

• However, it provides a constructor that can directly put the data into the collection, putting the data into the array first, and then pointing directly to the past

    public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);
    }

• add method

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        //Lock when adding
        lock.lock();
        try {
            // Copy a copy to a new array, array length + 1
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // Put the new value at the end and point the pointer to it
            newElements[len] = e;
            // Finally, return true and release the lock
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

• get method
  • Without any lock, the corresponding value is returned directly

    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

    /**
     * {@inheritDoc}
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        return get(getArray(), index);
    }