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
- Why copy on write sets ？
- CopyOnWriteArrayList What is the principle of implementation ？
- CopyOnWriteArrayList and ArrayList What's the difference? ？
- 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 ：
- Based on the array implementation ;
- 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 ：
- By adding mutexes （ReentrantLock） This ensures that only one thread can write .
- When adding elements , First use
Arrays.copyOf(elements, len + 1)Copy out a length +1 New array . - Add elements to the new array .
- 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 ：
- By adding mutexes （ReentrantLock） This ensures that only one thread can remove elements when writing .
- If you remove the last element , Copy the previous element to the new array , And point to the new array .
- 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 ：
- The acquisition element is not locked .
- 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 .
