Copy on write collection -- copyonwritearraylist

Preface

JUC There is also a series of classes below , All are CopyOnWriteXXX , It means copy while writing , What's going on with this ？ Then take CopyOnWriteArrayList As a starting point , Let's learn how to copy while writing ？

official account ：『 Liu Zhihang 』, Record the skills in work study 、 Development and source notes ; From time to time to share some of the life experience . You are welcome to guide ！

Introduce

ArrayList A thread safe variant of , All variable operations （add、set wait ） They are all realized by making a new copy of the underlying array .

Like a name , Every time you do something , It's going to be copied once , Of course, there will be a lot of performance consumption , But in some usage scenarios , It will improve performance again . How to operate , Then read the source code step by step , And then make a summary .

Basic use

public class CopyOnWriteArrayListTest {

    public static void main(String[] args) {

        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        //  Additive elements 
        list.add("liuzhihang");

        //  Remove elements 
        list.remove("liuzhihang");

        //  Check out the elements 
        String value0 = list.get(0);

        //  Traverse 
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
        }

    }
}

Question question

1. Why copy on write sets ？
2. CopyOnWriteArrayList What is the principle of implementation ？
3. CopyOnWriteArrayList and ArrayList What's the difference? ？
4. CopyOnWriteArrayList How replication works ？

Source code analysis

The basic structure

Parameter Introduction

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /**  Use when data changes  */
    final transient ReentrantLock lock = new ReentrantLock();

    /**  Array   Only through  getArray/setArray  visit  */
    private transient volatile Object[] array;

    final Object[] getArray() {
        return array;
    }
    //  Point the array to the new array passed in 
    final void setArray(Object[] a) {
        array = a;
    }
}

The following can be learned through the parameters ：

1. Based on the array implementation ;
2. Used ReentrantLock The mutex .

Constructors

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

Initializing CopyOnWriteArrayList when , I just created one Object Array of .

add

public boolean add(E e) {
    //  Lock 
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        //  Get the current array 
        Object[] elements = getArray();
        int len = elements.length;
        //  Create a new array , And copy the original array data to the new array 
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //  Add the new element to the end of the array 
        newElements[len] = e;
        //  Point the array to the new array 
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

add The logic of the method is simple ：

1. By adding mutexes （ReentrantLock） This ensures that only one thread can write .
2. When adding elements , First use Arrays.copyOf(elements, len + 1) Copy out a length +1 New array .
3. Add elements to the new array .
4. Then point the original array object to the new array .

The picture is as follows ：

remove

public E remove(int index) {
    //  Lock 
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        //  Original array 
        Object[] elements = getArray();
        int len = elements.length;
        //  Removed value 
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            //  If you remove the last element 
            //  Copy the previous element directly 
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            //  Remove the middle element , Make two replicates 
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                                numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

remove There are more methods to judge ：

1. By adding mutexes （ReentrantLock） This ensures that only one thread can remove elements when writing .
2. If you remove the last element , Copy the previous element to the new array , And point to the new array .
3. If you remove the middle element , You need to make two replicates , Then point to the new array .

The picture is as follows ：

get

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

get The method shows that ：

1. The acquisition element is not locked .
2. The element obtained from the original array .

So in the case of concurrency , There is no guarantee that the newly inserted or removed elements can be read in a timely manner .

Array copy

By reading add and remove Related codes , You can see that when copying arrays, you use Arrays.copyOf and System.arraycopy, This is equivalent to an optimization aspect .

After all, array copy can't traverse the original array again , Next to the assignment to the new array .

So let's take a look at how the interior works ：

public class Arrays {
    
    //  Other methods omitted  ...
    
    /**
     * original  Array to copy 
     * newLength  Length of new array 
     */
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

    /**
     * original  Array to copy 
     * newLength  Length of new array 
     */
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        //  Create a new array , The length is the specified length 
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            //  Creates a new array with the specified component type and length 
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        
        //  call  System.arraycopy  Copy the array 
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
}

By reading Arrays.copyOf Related to the source code , Found in fact Arrays.copyOf The bottom layer is also called System.arraycopy

public final class System {

    //  Other methods omitted  ...

    /**
     * src  Source array 
     * srcPos  Source array start position 
     * dest  Target array 
     * destPos  The starting position of the target array 
     * length  Number of elements to copy 
     */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
}

You can see System.arraycopy It's a native Method , This is JVM Internally realized , For details, please read the relevant materials . It's better to use this way than for Circulation and clone It's a lot more efficient .

summary

Q&A

Q: Why copy on write sets ？

A: Because in add、remove A new array will be copied during operation .

Q: CopyOnWriteArrayList What is the principle of implementation ？

A: stay add、remove It will be locked during operation , And then copy out a new array , All operations are new arrays , At this time, the original array can provide query . When the operation is finished , Will point the object pointer to the new array .

Q: CopyOnWriteArrayList and ArrayList What's the difference? ？

A: CopyOnWriteArrayList In the scenario of reading more and writing less, the efficiency can be improved , and ArrayList It's just a collection of ordinary arrays , Not for concurrent scenarios , And if it's right ArrayList Lock , Will affect some of the performance .

Same for CopyOnWriteArrayList for , Only final consistency can be guaranteed . Because of the data just written , Is written to the copied array of , At this time, you can't immediately query . If you want to ensure real-time performance, you can try to use Collections.synchronizedList Or lock and so on .

Q: CopyOnWriteArrayList How replication works ？

A: The internal use is local methods System.arraycopy Copy the array .

Conclusion

By reading CopyOnWriteArrayList Source code , Understand the principle of copy on write . At the same time, you can learn to use System.arraycopy To improve the efficiency of array replication .

Again CopyOnWriteArrayList Suitable for reading more and writing less , Meet the ultimate consistency , But it can't guarantee that the data can be modified in time .