JUCシリーズ-CopyOnWriteArrayListソース分析
12156 ワード
java.util.concurrent.CopyOnWriteArrayListは、同期リストの代わりに使用され、場合によってはより良い同時性能を提供し、反復中に容器をロックまたは複製する必要はない.同様に、CopyOnWriteArraySetは、同期Setの代わりに機能する.「書き込み時レプリケーション(Copy-On-Write)」コンテナのスレッドセキュリティは、事実上可変でないオブジェクトを正しくパブリッシュすれば、オブジェクトにアクセスする際にさらなる同期を必要としないことです.変更するたびに、新しいコンテナのコピーが作成され、再パブリッシュされ、可変性が実現されます.
CopyOnWriteArrayList公式docの説明は以下の通りです.
A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot"style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.
All elements are permitted, including null. Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread.
次に、*JDK 1を結合する.7**ソースコードを使用して、CopyOnWriteArrayListの内部実装メカニズムを解析します.
public class CopyOnWriteArrayList
implements List, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
/** The lock protecting all mutators */
transient final ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private volatile transient Object[] array;
/**
* Gets the array. Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
return array;
}
/**
* Sets the array.
*/
final void setArray(Object[] a) {
array = a;
}
/**
*
*/
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
/**
* Collection
*/
public CopyOnWriteArrayList(Collection extends E> c) {
Object[] elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
setArray(elements);
}
}
CopyOnWriteArrayList内部のarray配列は**volatile**によって修飾され、array配列のメモリ可視性を保証することができる.あるスレッドがarray配列を変更すると、他のスレッドはすぐに見ることができるので、CopyOnWriteArrayListのすべての読み取り操作はロックされず、ソースコードは以下の通りである.
/** Read **/
/**
*
*/
public E get(int index) {
return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
/**
*
*/
public int size() {
return getArray().length;
}
/**
*
*/
public boolean isEmpty() {
return size() == 0;
}
/**
*
*/
public boolean contains(Object o) {
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length) >= 0;
}
/**
*
*/
public int indexOf(Object o) {
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length);
}
public int indexOf(E e, int index) {
Object[] elements = getArray();
return indexOf(e, elements, index, elements.length);
}
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
Object[] elements = getArray();
return lastIndexOf(o, elements, elements.length - 1);
}
public int lastIndexOf(E e, int index) {
Object[] elements = getArray();
return lastIndexOf(e, elements, index);
}
private static int lastIndexOf(Object o, Object[] elements, int index) {
if (o == null) {
for (int i = index; i >= 0; i--)
if (elements[i] == null)
return i;
} else {
for (int i = index; i >= 0; i--)
if (o.equals(elements[i]))
return i;
}
return -1;
}
**volatile**は可視性を保証することができるが、原子性を保証することはできない.CopyOnWriteArrayListのすべての修正操作はReentrantLockロックによって任意の時点で1つのスレッドだけがCopyOnWriteArrayListを修正できることを保証する必要がある.ReentrantLock内部実装については、JUCシリーズ-ReentrantLockソースコード解析を参照してください.
CopyOnWriteArrayListのいくつかの重要な修正操作のソースコードは以下の通りです.
/** Write **/
/**
*
*/
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
/**
*
*/
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
/**
*
*/
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+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);
} finally {
lock.unlock();
}
}
/**
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
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);
}
return oldValue;
} finally {
lock.unlock();
}
}
/**
*
*/
public boolean remove(Object o) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (len != 0) {
// Copy while searching for element to remove
// This wins in the normal case of element being present
int newlen = len - 1;
Object[] newElements = new Object[newlen];
for (int i = 0; i < newlen; ++i) {
if (eq(o, elements[i])) {
// found one; copy remaining and exit
for (int k = i + 1; k < len; ++k)
newElements[k-1] = elements[k];
setArray(newElements);
return true;
} else
newElements[i] = elements[i];
}
// special handling for last cell
if (eq(o, elements[newlen])) {
setArray(newElements);
return true;
}
}
return false;
} finally {
lock.unlock();
}
}
/**
*
* @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
* ({@code{fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
*/
private void removeRange(int fromIndex, int toIndex) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
throw new IndexOutOfBoundsException();
int newlen = len - (toIndex - fromIndex);
int numMoved = len - toIndex;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, newlen));
else {
Object[] newElements = new Object[newlen];
System.arraycopy(elements, 0, newElements, 0, fromIndex);
System.arraycopy(elements, toIndex, newElements,
fromIndex, numMoved);
setArray(newElements);
}
} finally {
lock.unlock();
}
}
/**
*
*/
public boolean addIfAbsent(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
// Copy while checking if already present.
// This wins in the most common case where it is not present
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = new Object[len + 1];
for (int i = 0; i < len; ++i) {
if (eq(e, elements[i]))
return false; // exit, throwing away copy
else
newElements[i] = elements[i];
}
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
すべての修正操作は、
lock.lock();によってロックされ、修正が完了するとsetArray(newElements);によって新しいarray配列が発行され、最後にlock.unlock();によってロックが解放される必要があることがわかります.シーンの適用
明らかに、コンテナを変更するたびに下位配列がコピーされ、特にコンテナの規模が大きい場合、一定のオーバーヘッドが必要になります.[書き込み時コピー](Copy On Write)コンテナは、反復操作が修正操作よりはるかに多い場合にのみ使用します.たとえば、イベント通知システムでは、通知の配布時に登録済みリスナーチェーンテーブルを反復し、各リスナーを呼び出す必要があります.ほとんどの場合、イベント通知を受信する操作よりも、イベントリスナーの登録とログアウトの操作がはるかに少ないです.