Shulou(Shulou.com)06/02 Report--

This article mainly explains "what are the hidden knowledge points in CopyOnWriteArrayList". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn what are the hidden knowledge points in CopyOnWriteArrayList.

Thread safe List

There is more than one thread-safe List in Java. In addition to today's protagonist CopyOnWriteArrayList, there are also Vector classes and SynchronizedList classes, which are thread-safe List collections. Before introducing CopyOnWriteArrayList, let's briefly introduce the other two.

If you try to look at their source code, you will find something wrong. Concurrent collections are all in the java.util.concurrent package. Why are the Vector class and SynchronizedList class in the java.util package?

Indeed, the two thread-safe List and thread-safe HashTable are the same, are relatively simple and rough implementation, directly add the synchronized keyword to achieve, and regardless of additions, deletions, changes and queries, all add, even the get method is no exception, yes, it is so rough.

The get method of the Vector class:

/ / get operation in Vector added synchronizedpublic synchronized E get (int index) {if (index > = elementCount) throw new ArrayIndexOutOfBoundsException (index); return elementData (index);}

The ge t method of the SynchronizedList class:

Public E get (int index) {synchronized (mutex) {return list.get (index);}}

Students may wish to think about it, in fact, there is a reason to add a synchronization mechanism to the get method, although the efficiency is reduced, but the written data can be queried immediately, which also ensures the strong consistency of the data. In addition, the above description of synchronized's simplicity and rudeness is not accurate, because in higher versions of JDK, synchronized can already automatically adjust the granularity of locks according to runtime conditions, which will be mentioned again in the introduction of CopyOnWriteArrayList later.

CopyOnWriteArrayList

In the JDK concurrent package, CopyOnWriteArrayList is currently the only concurrent collection of List. The rough implementation of Vector and SynchronizdList is briefly introduced above, and since there is also CopyOnWriteArrayList, it must be different from the above two. As the only concurrent List, how is it different?

Before we explore the implementation of CopyOnWriteArrayList, we might as well think about how you would implement a thread-safe List if it were you.

How to ensure thread safety when reading and writing simultaneously?

Should the data be strongly consistent? Is the data reflected immediately after reading and writing updates?

What is the capacity for initialization and expansion?

Do you want to ensure the consistency of the data over time? Does the Fail-Fast mechanism need to be introduced?

From the class name, we can roughly guess the implementation idea of the CopyOnWriteArrayList class: Copy-On-Write, that is, the write-time replication strategy; the ArrayList at the end indicates that the data is stored in an array. When adding and deleting elements, first make a copy of the existing data array, then add and delete all on this copy array, and then replace the original data array with a new array after the operation is completed. This completes the update operation.

But there must be a problem with this way of copying when writing, because each update replaces the old array with a new array, and if it happens that a thread is reading the data at the time of the update, then you are reading the old data in the old array. In fact, this is also the idea of read-write separation, giving up the strong consistency of data in exchange for performance improvement.

Analyze the source code (JDK8)

As mentioned above, the idea of CopyOnWriteArrayList is to copy at write time, read-write separation, and it maintains an array decorated with volatile to store element data.

/ * The array, accessed only via getArray/setArray. * / private transient volatile Object [] array

There are many methods in the CopyOnWriteArrayList class, which will not be introduced here. The following will analyze several commonly used methods. After understanding these methods, you can basically grasp the implementation principle of CopyOnWriteArrayList.

Constructor function

CopyOnWriteArrayList has a total of three constructors, one is a no-parameter construction, and directly initializes the array length to 0; the other two pass a collection or array as parameters, and then directly extract the elements from the collection or array and assign values to the array maintained internally by CopyOnWriteArrayList.

/ / directly initialize an array of length 0 public CopyOnWriteArrayList () {setArray (new Object [0]);} / / pass in a collection, extract the elements in the collection and assign values to the CopyOnWriteArrayList array public CopyOnWriteArrayList (Collection c) {Object [] es; if (c.getClass () = = CopyOnWriteArrayList.class) es = ((CopyOnWriteArrayList) c) .getArray (); else {es = c.toArray () If (c.getClass ()! = java.util.ArrayList.class) es = Arrays.copyOf (es, es.length, Object [] .class);} setArray (es);} / / pass in an array, and the array elements are extracted and assigned to the CopyOnWriteArrayList array public CopyOnWriteArrayList (E [] toCopyIn) {setArray (Arrays.copyOf (toCopyIn, toCopyIn.length, Object [] .class);}

The constructor is called when the instance is created, and there is no thread safety problem, so the constructor is a simple assignment operation and there is no special logic processing.

New element

There are several new elements according to the different input parameters, but the principle is the same, so the following only shows the implementation of add (E e), which ensures thread safety through a ReentrantLock lock.

/ * Appends the specified element to the end of this list. * * @ param e element to be appended to this list * @ return {@ code true} (as specified by {@ link Collection#add}) * / public boolean add (E) {final ReentrantLock lock = this.lock; lock.lock (); / / locked try {Object [] elements = getArray (); / / get data array int len = elements.length; Object [] newElements = Arrays.copyOf (elements, len + 1) / / copy a data array with length + 1 newElements [len] = e; / / add a new element setArray (newElements); / / replace the old array return true;} finally {lock.unlock ();}} with the new array.

Specific steps:

Lock, get the current data array to start the operation (locking ensures that only one thread adds / deletes / modifies at a time).

Copy the current data array and increase its length by one.

Put new elements in the new array.

Replace the old array with the new array.

Finally releases the lock.

Since the capacity increases by only 1 per add, a new array is created for data replication each time, and the old data is replaced after the operation is completed, which will inevitably degrade the performance when the data is added. Here is a simple example to test the new and query performance of CopyOnWriteArrayList, Vector, and ArrayList.

Public static void main (String [] args) {CopyOnWriteArrayList copyOnWriteArrayList = new CopyOnWriteArrayList (); Vector vector = new Vector (); ArrayList arrayList = new ArrayList (); add (copyOnWriteArrayList); add (vector); add (arrayList); get (copyOnWriteArrayList); get (vector); get (arrayList);} public static void add (List list) {long start = System.currentTimeMillis (); for (int I = 0; I < 100000) System.currentTimeMillis +) {list.add (I);} long end = System.currentTimeMillis (); System.out.println (list.getClass (). GetName () + ".size =" + list.size () + ", add time:" + (end-start) + "ms");} public static void get (List list) {long start = System.currentTimeMillis (); for (int I = 0; I < list.size ()) Long end +) {Object object = list.get (I);} long end = System.currentTimeMillis (); System.out.println (list.getClass (). GetName () + ".size =" + list.size () + ", get time:" + (end-start) + "ms");}

From the measured results, we can see that the addition of CopyOnWriteArrayList takes the longest time, followed by locked Vector (the default capacity expansion of Vector is twice as long). The fastest acquisition is thread-unsafe ArrayList, followed by CopyOnWriteArrayList, and Vector has the lowest performance because Get is locked.

Java.util.concurrent.CopyOnWriteArrayList.size=100000,add time: 2756msjava.util.Vector.sizekeeper 100000add time: 4msjava.util.ArrayList.sizeyard 100000dadadd time: 3msjava.util.concurrent.CopyOnWriteArrayList.sizeyard 100000get get time: 4msjava.util.Vector.sizekeeper 100000get time: 5msjava.util.ArrayList.sizelisting 100000time get

The idea of modifying elements and adding elements is consistent, through the ReentrantLock lock to ensure thread safety, the implementation of the code is relatively simple, originally did not intend to write in, but in looking at the source code to find a very interesting place, look at the following code.

Public E set (int index, E element) {final ReentrantLock lock = this.lock; lock.lock (); / / locked try {Object [] elements = getArray (); / / get the old array E oldValue = get (elements, index); / / get the specified location element if (oldValue! = element) {/ / whether the old and new elements are equal, int len = elements.length Object [] newElements = Arrays.copyOf (elements, len); / / copy the old array newElements [index] = element; / / assign a new value setArray (newElements) at the specified location; / / replace the old array} else {/ / Not quite a no-op; ensures volatile write semantics setArray (elements) / / here comes the interesting part} return oldValue;} finally {lock.unlock ();}}

From the source code, you can see that before modifying the element, the values before and after the modification will be compared to see if the values are equal, but in the case of equality, it is still setArray (elements); this is wonderful, why on earth is it? To understand why, you need to understand the special role of volatile, as illustrated by the following code example.

/ / initial conditionsint nonVolatileField = 0PostCopyOnWriteArrayList list = / * a single String * / / Thread 1nonVolatileField = 1; / / (1) list.set (0, "x"); / / (2) / / Thread 2String s = list.get (0); / / (3) if (s = "x") {int localVar = nonVolatileField / / (4)} / / example from: https://stackoverflow.com/questions/28772539/why-setarray-method-call-required-in-copyonwritearraylist

To understand the special features of the example, first you need to know that volatile prevents rearrangement of instructions, and secondly, you need to understand the happens-before mechanism. To put it simply, they can ensure the order before and after the execution of the code.

For example, in the code in the above example, there is no doubt that 1 will be executed before 2 and 3 before 4. Another is that volatile-modified attribute writes are performed before reading, so 2 is executed before 3. On the other hand, the execution order is also transitive. So eventually 1 will be executed before 4. So the value obtained by 4 is the value assigned to nonVolatileField in step 1. If there is no setArray for the same value in the set method in CopyOnWriteArrayList, none of the above will exist.

Delete element

There are three ways to delete elements in remove. Here we only look at the public E remove (int index) method, and the principles are similar.

Public E remove (int index) {final ReentrantLock lock = this.lock; lock.lock (); / / locked try {Object [] elements = getArray (); / / get the data array int len = elements.length; E oldValue = get (elements, index); / / get the element to be deleted int numMoved = len-index-1 If (numMoved = = 0) / / whether to end setArray (Arrays.copyOf (elements, len-1)); / / data array minus the last element else {Object [] newElements = new Object [len-1]; / / copy the elements before and after the data to be deleted to the new array System.arraycopy (elements, 0, newElements, 0, index). System.arraycopy (elements, index + 1, newElements, index, numMoved); setArray (newElements); / / replace the old array} return oldValue;} finally {lock.unlock (); / / unlock}} with the new array

The code is simple: use the ReentrantLock exclusive lock to ensure thread safety of the operation, then copy the remaining array elements to the new array after deleting the element, replace the old array with the new array to complete the element deletion, and finally release the lock to return.

Get element

Gets the element with subscript index, and throws an IndexOutOfBoundsException exception if the element does not exist.

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

First of all, we can see that there is no locking operation here, and getting the element at the specified location is divided into two steps:

GetArray () gets the data array.

Get (Object [] a, int index) returns the element at the specified location.

It is likely that a thread updates the array after the completion of the first step and before the execution of step 2. From the above analysis, we know that the update will generate a new array, and we have already obtained the old array in the first step, so we are still doing get on the old array, that is, the update result of another thread is not valid for our current get. This is also the weak consistency problem mentioned above.

Weak consistency of iterators List list = new CopyOnWriteArrayList (); list.add ("www.wdbyte.com"); list.add ("unread code"); Iterator iterator = list.iterator (); list.add ("java"); while (iterator.hasNext ()) {String next = iterator.next (); System.out.println (next);}

Now the element www.wdbyte.com and unread code have been added to the List, and after getting the iterator object, the new element java has been added, and you can see that the traversal results do not report an error or output java. That is, after getting the iterator object, the update of the element is not visible.

Www.wdbyte.com unread code

Why is that? Start with the implementation of CopyOnWriteArrayList's iterator () method.

Public Iterator iterator () {return new COWIterator (getArray (), 0);} static final class COWIterator implements ListIterator {/ * Snapshot of the array * / private final Object [] snapshot; / * * Index of element to be returned by subsequent call to next. * / private int cursor; private COWIterator (Object [] elements, int initialCursor) {cursor = initialCursor; snapshot = elements;}.

You can see that when getting the iterator, getArray () first gets the data array and passes it to the COWIterator constructor, and then assigns the value to the snapshot attribute in COWIterator. Combined with the above analysis results, you can know that each update will generate a new array, while the old array is still used here, so the update operation is not visible, that is, the weak consistency mentioned many times above.

New edition change

The above source code analysis is based on JDK 8. While writing the article, I took a look at whether the implementation of the new version has changed, and there is really a big change, mainly reflected in the way of adding locks. Perhaps it is because JVM later introduced the strategy of upgrading synchronized locks, which has improved the performance of synchronized a lot, so it replaced the old ReentrantLock locks with synchronized locks.

New:

Public boolean add (E e) {synchronized (lock) {Object [] es = getArray (); int len = es.length; es = Arrays.copyOf (es, len + 1); es [len] = e; setArray (es); return true;}}

Modify:

Public E set (int index, E element) {synchronized (lock) {Object [] es = getArray (); E oldValue = elementAt (es, index); if (oldValue! = element) {es = es.clone (); es [index] = element;} / / Ensure volatile write semantics even when oldvalue = = element setArray (es); return oldValue;}} Summary

Through the above analysis, we can get the following summary about CopyOnWriteArrayList.

CopyOnWriteArrayList uses read-write separation and write-time replication to achieve thread safety and weak consistency.

CopyOnWriteArrayList has poor write performance because it expands the replication array each time it is written.

When CopyOnWriteArrayList modifies an element, in order to ensure volatile semantics, it will reassign the value even if there is no change to the element.

In the high-end version of JDK, thanks to the synchronized lock upgrade strategy, CopyOnWriteArrayList uses synchronized to add locks.

At this point, I believe you have a deeper understanding of "what are the hidden knowledge points in CopyOnWriteArrayList?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.