The background,

Some time ago, a Flutter plugin was developed to collect Raw Gnss data and support high frequency IMU data writes. A cache pool is designed to cache the log information collected in 3 minutes. Multi-threading is used to add data. A scheduled task is executed every minute to clear expired data. In order to save trouble, I directly used CopyOnWriteArrayList cache string at that time. In the subsequent use process, I found that gc garbage recycling logs frequently broke in the background. After investigation, I located this concurrent class. It also gives you a deeper understanding of why CopyOnWriteArrayList is only good for scenarios where you read too much and write too little.

Second, the meaning

CopyOnWriteArrayList is an ArrayList that is copied at write time. When a container needs to be modified, it does not modify the current container directly. Instead, it copies the current container, makes a Copy of the new container, and then changes the new container. The reference to the original container points to the new container. This completes the modification process.

Because the container creates a new copy every time it is modified, it is immutable, i.e. thread-safe, for the old container, and does not require synchronization operations such as locking. So we can take advantage of the immutability of CopyOnWriteArrayList for concurrent reads.

All the modification operations of CopyOnWriteArrayList (add, set, etc.) are realized by creating a new copy of the underlying array, so CopyOnWrite container is also a kind of idea of read and write separation, read and write using different containers, so the write will not block the read operation, Reading and writing can be done simultaneously, but only writing needs to be synchronized, so it is suitable if the reading scene is larger than writing.

Third, source code analysis

Having said that, where did the pit I encountered come from? I’m sure some of you have guessed a little bit from what I just explained, but let’s go straight to the problem from the source point of view.

The following source code analysis is based on Android 11

Add

Let’s look at the add operation first

public void add(int index, E element) {
    synchronized (lock) {
        Object[] elements = getArray();
        int len = elements.length;
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException(outOfBounds(index, len));
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1, numMoved); } newElements[index] = element; setArray(newElements); }}Copy the code

First, the code block is wrapped with the sync keyword, locking the logic to add elements. The advantage of this is that subsequent add operations cannot be executed until the last add is complete and the lock is released.

GetArray () returns a volatile array that ensures consistency across threads and is the actual element in the current list.

Next, the index is judged to be abnormal, which is also worth learning. For externally passed parameters, we need to consider exception handling.

We then use len-index to determine whether to insert elements in the middle or at the end of the array. Arraycopy is used to copy data, leaving space for insertion. Then set the index value of the new array.

Finally, a reference to the new array points to the original array.

Remove

Let’s look at Remove

public E remove(int index) {
    synchronized (lock) {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        returnoldValue; }}Copy the code

The Add method is similar, except that it does a reduction on the array. I won’t repeat it here. Just to mention that numMoved is subtracted by one because the array is indexed from 0, where len is equal to elements. Length, so it needs to be subtracted by one.

disadvantages

Through the analysis of the above 2 code, can see clearly that, in copy, delete, in memory will exist at the same time more memory object, in this way, the element of the list is long, will spend a lot of CPU resources in addition to outside, the memory overhead is not small, that is why I will see the reason of frequent GC in the background.

Iv. Solutions

Finally, tell me how I solved the problem at the beginning.

Because I need to remove the header of the queue to remove expired data and add new data to the end of the queue, I replace CopyOnWriteArrayList with LinkedList and modify the add and remove operations with sync synchronization locks.