Introduction to the

CopyOnWriteArrayList is a concurrent container provided in Java. It is a thread-safe, lock-free ArrayList that reads and writes by creating a new copy of the underlying array. It is a concurrent strategy for read-write separation. A similar container for Java and packages is CopyOnWriteSet. This article will be on CopyOnWriteArrayList implementation principle and source analysis.

Realize the principle of

As we all know, ArrayList in the collections framework is thread-safe, whereas Vector is thread-safe but performs poorly due to its crude locking synchronization mechanism. CopyOnWriteArrayList provides a different concurrency strategy (for specific concurrency scenarios, of course).

A lot of times, our systems deal with concurrent scenarios where we read too much and write too little. CopyOnWriteArrayList allows concurrent reads. The read operation is lockless and has high performance. For writes, such as adding an element to a container, a copy of the current container is first made, the write is performed on the new copy, and a reference to the original container is then referred to the new container.

Advantages and disadvantages analysis

Now that you know how CopyOnWriteArrayList works, it’s easy to analyze its pros and cons and usage scenarios.

Advantages:

The read operation performance is high because no synchronization measures are required. Therefore, the read operation is suitable for concurrent scenarios with many reads and few writes. Java list in traversed, if midway have other threads to modify the list container, will throw ConcurrentModificationException. The CopyOnWriteArrayList because of its ideas, read and write “separate” traverse and modify the operating effect respectively in different list container, so when using iterators traversal, also won’t throw ConcurrentModificationException

Disadvantages:

The disadvantages are also obvious. First, memory usage is a problem. After all, each write operation requires a copy of the original container. Second, it cannot guarantee real-time performance. Vector locks all read and write operations to ensure strong read and write consistency. CopyOnWriteArrayList, however, because of its implementation strategy, writes and reads work on old and new containers. During the write operation, the read does not block but reads data from the old container.

Inheritance system

CopyOnWriteArrayList’s inheritance system can be seen from the class diagram.

  • Implement List, RandomAccess, Cloneable, Java. IO.Serializable interface.

  • List is implemented, providing basic add, delete, traverse, and so on.

  • RandomAccess is implemented to provide the ability of RandomAccess.

  • Implementation of Cloneable, can be cloned.

  • Serializable is implemented and can be serialized.

Source code analysis

attribute

Final TRANSIENT ReentrantLock LOCK = new ReentrantLock(); Private TRANSIENT volatile Object[]; private transient volatile Object[]; final Object[] getArray() { return array; } final void setArray(Object[] a) { array = a; }Copy the code
  • Lock: used to lock when changing, use transient modifier to indicate not automatic serialization.
  • Array: Used as volatile to indicate that changes made by one thread to a field are immediately visible to another thread.

A constructor

  • No-argument constructor: Creates an empty array

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

  • Has a parameter constructor that takes a set 
    public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; / / if c is CopyOnWriteArrayList type / / then get its array directly using the if (c.g etClass () = = CopyOnWriteArrayList. Class) elements = ((CopyOnWriteArrayList<? >)c).getArray(); Else {// otherwise, convert to array 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); }Copy the code
  • Takes an array as an argument constructor 
    // Copy the toCopyIn element to the current list array. public CopyOnWriteArrayList(E[] toCopyIn) { setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); }Copy the code

add(E e)

Add an element to the end

Public Boolean add(E E) {final ReentrantLock lock = this.lock; The lock (); / / lock lock. Try {// Old array Object[] elements = getArray(); Int len = elements. Length; [] newElements = array.copyof (Elements, len + 1); NewElements [len] = e; // Set the array to a new array setArray(newElements); return true; } finally {// unlock lock.unlock(); }}Copy the code

add(int index, E element)

Inserts an array at the specified location

Public void add(int index, E element) {// Final ReentrantLock lock = this.lock; The lock (); / / lock lock. Try {// Old array Object[] elements = getArray(); int len = elements.length; / / whether the subscript crossing the if (index > len | | index < 0) throw new IndexOutOfBoundsException (" index: "+ index +", Size: "+ len); // New array Object[] newElements; int numMoved = len - index; NewElements = array.copyof (Elements, len +1); newElements = Array.copyof (elements, len +1); NewElements = new Object[len +1]; newElements = new Object[len +1]; newElements = new Object[len +1]; Arraycopy (elements, 0, newElements, 0, index); arrayCopy (elements, 0, newElements, 0, index); // Copy the rest of the old array to the new array [index+1,... Arraycopy (elements, index, newElements, index +1, numMoved); arrayCopy (elements, index, newElements, index +1, numMoved) } newElements[index] = element; // Assign array setArray(newElements); } finally {// unlock lock.unlock(); }}Copy the code

Write operation:

  • In each of the above operations to add elements, a lock is performed
  • Copy a new array equal to the length of the original array plus 1, and copy the elements of the original array into the new array
  • Assign the new array to the array property of the current object, overwriting the original array

remove(int index)

Remove data element based on subscript position:

Public E remove(int index) {// Final ReentrantLock lock = this.lock; The lock (); / / lock lock. Try {// Old array Object[] elements = getArray(); int len = elements.length; E oldValue = get(elements, index); int numMoved = len - index - 1; SetArray (Array.copyof (Elements, Len-1)); if (numMoved == 0) Else {// If the last bit is not removed // then create a new array of n-1 Object[] newElements = new Object[len-1]; System. arrayCopy (elements, 0, newElements, 0, index); System. Arraycopy (elements, index + 1, newElements, index, elements); numMoved); setArray(newElements); } return oldValue; } finally {// unlock lock.unlock(); }}Copy the code

** Delete Operations: ** Delete operations similarly, copy elements other than those to be deleted into the new copy, and then switch references to point the original container reference to the new copy. Both write operations need to be locked.

get(int index)

    public E get(int index) {
        return get(getArray(), index);
    }

    final Object[] getArray() {
        return array;
    }

    private E get(Object[] a, int index) {
        return (E) a[index];
    }
Copy the code

Fetch operation: The fetch operation is a read operation. It directly fetches data elements by array subscript without locking, thus ensuring performance.

size()

Public int size() {// Return getArray().length; }Copy the code

Unlike ArrayList, which has the size attribute, ArrayList is actually larger than the size of the collection. CopyOnWriteArrayList is a copy of an array that can store exactly the number of elements it needs, so it doesn’t need the size property and returns the length of the array.

How to keep thread safe

* The array container is volatile, which ensures that any thread that changes the memory address of the array is notified to any other thread; * All changes to the array are locked, so that only one thread can modify the array at a time. For example, when I add, I cannot remove; * During the modification process, the original array is copied, is modified on the new array, the modification process, will not have any impact on the original array.

conclusion

  • CopyOnWriteArrayList uses ReentrantLock to lock, ensuring thread safety;

  • CopyOnWriteArrayList write operations must first copy a new array, make changes in the new array, and then replace the old array with the new array, so the space complexity is O(n), relatively low performance;

  • The read operation of CopyOnWriteArrayList supports random access and the time complexity is O(1).

  • CopyOnWriteArrayList uses the idea of read and write separation, read operation without lock, write operation lock, and write operation occupies a large memory space, so it is suitable for read more write less occasions;

  • CopyOnWriteArrayList only guarantees final consistency, not real-time consistency.