preface
There is also a series of classes under JUC, all of which are CopyOnWriteXXX, which means copy while writing. So let’s start with CopyOnWriteArrayList and see what copy-on-write is.
[liuzhirichard] Record technology, development and source code notes in work and study. From time to time, share what you’ve seen and heard in your life. Welcome to guide!
introduce
A thread-safe variant of ArrayList, where all mutable operations (add, set, and so on) are implemented by making a new copy of the underlying array.
As the name indicates, each time an operation is performed, a copy is performed. Of course, there is a significant performance cost, but in some scenarios, performance can be improved. Specifically how to operate, then read the source code step by step, and then do a summary.
The basic use
public class CopyOnWriteArrayListTest {
public static void main(String[] args) {
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
// Add elements
list.add("liuzhihang");
// Remove the element
list.remove("liuzhihang");
// View the element
String value0 = list.get(0);
/ / traverse
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) { String next = iterator.next(); }}}Copy the codeQuestion question
- Why is it called copy-on-write collection?
- How does CopyOnWriteArrayList work?
- What’s the difference between CopyOnWriteArrayList and ArrayList?
- CopyOnWriteArrayList How does a copy work?
Source code analysis
The basic structure
Parameter is introduced
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();
/** Arrays can only be accessed via getArray/setArray */
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; }}Copy the codeYou can learn the following about parameters:
- Implementation based on array;
- The ReentrantLock mutex is used.
The constructor
public CopyOnWriteArrayList(a) {
setArray(new Object[0]);
}
Copy the codeWhen you initialize CopyOnWriteArrayList, you create an array of Objects.
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 data from the original array to the new array
Object[] newElements = Arrays.copyOf(elements, len + 1);
// Add new elements to the end of the array
newElements[len] = e;
// Point the array to the new array
setArray(newElements);
return true;
} finally{ lock.unlock(); }}Copy the codeThe logic of the add method is simple:
- ReentrantLock is used to ensure that only one thread can write.
- When adding an element, use it first
Arrays.copyOf(elements, len + 1)Copy out a new array of length +1. - Adds elements to the new array.
- Then point the old array object to the new array.
The drawing is as follows:
remove
public E remove(int index) {
/ / lock
final ReentrantLock lock = this.lock;
lock.lock();
try {
/ / the original array
Object[] elements = getArray();
int len = elements.length;
// Remove the value
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
// If the last element is removed
// Just copy the previous element
setArray(Arrays.copyOf(elements, len - 1));
else {
// Remove the middle element and duplicate it twice
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(); }}Copy the codeThe remove method is relatively more judgmental:
- ReentrantLock is used to ensure that only one thread can remove elements at write time.
- If you remove the last element, just copy the previous element into the new array and point to the new array.
- If you remove the middle element, you need to copy it twice and point to the new array.
The drawing is as follows:
get
public E get(int index) {
return get(getArray(), index);
}
Copy the codeThe get method shows that:
- The element is not locked.
- The element obtained from the original array.
So in concurrent cases, there is no guarantee that the inserted or removed elements will be read in a timely manner.
Copy an array
Array.copyof and System.arrayCopy are used for array.copyof and System.arrayCopy.
Array copy, after all, can’t just iterate over the original array, assigning values next to the new array.
Let’s look at how it works internally:
public class Arrays {
// Other ways to omit...
/** * original Array to copy * newLength Length of the 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 the new array */
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// Create a new array of 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 to copy the array
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
returncopy; }}Copy the codeArrays. CopyOf is also called System. Arraycopy
public final class System {
// Other ways to omit...
/** * SRC source array * srcPos source array start position * dest destination array * destPos destination array start position * length number of elements to copy */
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
}
Copy the codeAs you can see, System. arrayCopy is a native method that is implemented internally by the JVM. Using this approach is much more efficient than for loops and clones.
conclusion
Q&A
Q: Why is it called a copy-on-write collection?
A: Because the add and remove operations copy A new array.
Q: How does CopyOnWriteArrayList work?
A: During add and remove operations, locks will be added, and then A new array will be copied. The new array will be operated on, while the original array can provide queries. When the operation is finished, the object pointer points to the new array.
Q: What’s the difference between CopyOnWriteArrayList and ArrayList?
A: CopyOnWriteArrayList can improve efficiency in A scenario where there are many reads and few writes. An ArrayList is just an ordinary array collection and is not suitable for A concurrent scenario. Locking an ArrayList will affect some performance.
Also with CopyOnWriteArrayList, only final consistency is guaranteed. Because the data that was just written is in the copied array that was written to, it is not immediately available. If you want to ensure the real-time can try to use the Collections. SynchronizedList or lock, etc.
Q: How does CopyOnWriteArrayList copy work?
A: Internal uses the local method System. Arraycopy to copy an array.
conclusion
Read CopyOnWriteArrayList source code to understand the principle of copy while writing. We also learned that we can use system. arrayCopy to improve the efficiency of array copying.
CopyOnWriteArrayList is also suitable for scenarios with more reads and less writes to meet final consistency, but it does not guarantee that data changes will be queried in a timely manner.