[Part 16] copyonwritearraylist source code analysis and application details [key]

1.1 summary

ArrayList It is the most familiar collection for everyone to use , And this set was designed for high efficiency at the beginning , The multithreading scenario is not considered , Therefore, there are multiple threads CopyOnWriteArrayList This collection .

1.2 Principle analysis

CopyOnWriteArrayList yes ArrayList The concurrent container of

Write operations ：

By name ,CopyOnWriteArrayList The object array will be copied to the new array , When it is written, it will be written on the new array , And then CopyOnWriteArrayList Replace the object array of with a new array .

Read operations ：

The read operation does not apply any locks

After knowing how to write and read , We found that CopyOnWriteArrayList Suitable for Write less and read more Scene .

1.2.1 Remember ArrayList

1.2.1.1 A collection of fail-fast The mechanism and fail-safe Mechanism ：

• fail-fast Fast failure mechanism

One thread A When traversing a collection with an iterator , Another thread B In this case, modifying the set will result in A Fast failure , Throw out ConcurrentModificationException abnormal . stay java.util The collection classes in are all fast failing .

• fail-safe Security failure mechanism

Traversal is not on the original set , Instead, copy a set first , Traversing over the set of copies . stay java.util.concurrent The container class under the package is a security failure , It is recommended to use the collection class under this package in a concurrent environment .

1.2.1.2 ArrayList brief introduction

• ArrayList It's the realization of List Variable array of interfaces , And allow null Repeating elements within
• The underlying array implementation , Copy the old array elements to the new array during capacity expansion , Each expansion is of its capacity 1.5 times , High operation cost
• Adopted Fail-Fast Mechanism , When faced with concurrent modifications , The iterator will soon fail completely , Instead of risking arbitrary uncertainty at some uncertain time in the future
• ArrayList It's not thread safe , That's why it's used in a single thread ArrayList, And in the You can choose from multiple threads Vector perhaps CopyOnWriteArrayList

1.2.2 CopyOnWriteArrayList The source code parsing

1.2.2.1 Main attributes

// An exclusive lock , The lock applied when a write operation occurs 
final transient ReentrantLock lock = new ReentrantLock();
// Array 
private transient volatile Object[] array;

1.2.2.2 get(int index)

public E get(int index) {
    
    return get(getArray(), index);
}
private E get(Object[] a, int index) {
    
    return (E) a[index];
}

get() Nothing to say , Normal operation ！

1.2.2.3 add(E e)

public boolean add(E e) {
    
    final ReentrantLock lock = this.lock;
    // Lock 
    lock.lock();
    try {
    
        // obtain array
        Object[] elements = getArray();
        int len = elements.length;
        // take array  copy to newElements
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // take e Add to newElements Last position 
        newElements[len] = e;
        // take array The reference is set to newElements
        setArray(newElements);
        return true;
    } finally {
    
        lock.unlock();
    }
}

When add(e) When , There are the following steps ：

1、 take array Copy to a newElements in ,newElements Is the length of the len+1
2、 take e Add to newElements In the last position of
3、 take array The reference is set to newElements

We can see from the source code , We can see a problem ：
When a thread calls add() When , At this time, if there are other threads to read data , The newly added data will not be read , There will be short-lived read-write inconsistencies ！

1.2.2.4 set(int index,E e)

public E set(int index, E element) {
    
    final ReentrantLock lock = this.lock;
    // Lock 
    lock.lock();
    try {
    
        Object[] elements = getArray();
        E oldValue = get(elements, index);
        // If the elements before and after the change are inconsistent 
        if (oldValue != element) {
    
            int len = elements.length;
            // Copy a new array 
            Object[] newElements = Arrays.copyOf(elements, len);
            // Fill the new element with 
            newElements[index] = element;
            // Replace 
            setArray(newElements);
        } else {
    
            setArray(elements);
        }
        return oldValue;
    } finally {
    
        lock.unlock();
    }
}

1.2.2.4 remove(int index)

public E remove(int index) {
    
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
    
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        // The number of elements to be moved 
        int numMoved = len - index - 1;
        // If 0, Note that the last element is deleted 
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
    
            Object[] newElements = new Object[len - 1];
            // Will be taken from elements The subscript 0 Copy index Elements to newElements Of 0 The subscript begins index Elements 
            System.arraycopy(elements, 0, newElements, 0, index);
            // Will be taken from elements The subscript index+1 Copy numMoved Elements to newElements Of index The subscript begins numMoved Elements 
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
    
        lock.unlock();
    }
}

1.3 summary

1.3.1 CopyOnWriteArrayList Analysis of advantages and disadvantages

advantage
1、CopyOnWriteArrayList Using the idea of separation of reading and writing , Read operations are not locked , Write and lock , And write operation takes up more memory space , High read performance , No synchronization measures are required , It's more suitable for Concurrent scenarios with more reads and less writes .

2、 The stored data is orderly , You should have noticed when looking at the source code , It is to copy the original data first , Then assign the data to be added at the last position .

3、CopyOnWriteArrayList Use ReentrantLock Reentry lock lock , Ensure thread safety .

shortcoming

1、 Memory usage problem , Each write operation requires a copy of the original container data , When the data volume is large , There will be more pressure on memory , It may also cause frequent GC.

2、 Real time performance cannot be guaranteed when reading , This is also the price of read-write separation ,Vector It can guarantee the strong consistency of reading and writing , But the disadvantages have been mentioned above , Different scenarios use different containers .