你好,我是看山。
书接上文,上次聊了聊 在多线程中使用 ArrayList 会发生什么,这次我们说说平时常用的列表:Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList。
Vector
Vector
是在 JDK 1.0 提供的,虽然没有被标记Deprecated
,但是事实上已经没人使用了。主要原因是性能差,且不符合需求。
从源码可以看出(这里不贴源码了),Vector
是基于数组实现,几乎在所有操作方法上,都用synchronized
关键字实现方法同步,这种同步方式可以对单一操作进行加锁,比如多个线程同时执行add
会同步阻塞执行,但是多线程执行add
和remove
时,就不会阻塞了。
但是,大部分需要对队列加锁的场景,是想对整个队列加锁,而不仅仅是对单一操作加锁。也就是说,Vector
和我们的期望不同,但是又额外增加了同步操作带来的性能开销。所以,不是必须使用的场景,都可以使用ArrayList
代替,即使是多线程情况下需要同步队列,也可以使用CopyOnWriteArrayList
和SynchronizedList
代替。
ArrayList
ArrayList
是在 JDK 1.1 提供的,作为Vector
的继任者(ArrayList
实现方式与Vector
几乎完全相同),ArrayList
把方法上的synchronized
全部去掉了,完全没有实现同步,是非线程安全的。
它的非线程安全,还体现在迭代器的快速失败上。在使用方法iterator
和listIterator
创建迭代器之后,如果还对原来的ArrayList
队列进行修改(add 或 remove),迭代器迭代的时候就会报ConcurrentModificationException
异常。从源码可以看出,迭代器在迭代过程中,会检查队列中修改次数modCount
与创建迭代器时落下的修改次数快照expectedModCount
是否相等,相等表示没有修改过,代码如下:
private class Itr implements Iterator<E> {
// 这段代码是从 ArrayList 中摘取的
// 只留下检查方法,略过其他代码,有兴趣的可以从源码中查看
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
第三点是在多线程场景中,添加元素可能会丢失数据,或者发生数组越界异常,在多线程中使用 ArrayList 会发生什么 有详细描述,这里就不赘述了。
SynchronizedList
SynchronizedList
是Collections
的静态内部类,使用Collections.synchronizedList()
静态方法创建,是一个通过组合List
类实现的封装实现。它的大多数方法通过synchronized (mutex){...}
代码块同步方式,因为加锁对象mutex
是队列对象中定义的相同对象,所以对mutex
加锁时,可以在多线程之间实现阻塞。但是这种实现方式和Vector
在方法上加锁没有本质的区别,所以Vector
存在的困境,SynchronizedList
依然存在。
ArrayList
中存在的迭代器快速失败情况,依然存在,正如下面源码中的注释:想要使用迭代器,需要用户手动实现同步。
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
// 代码摘自 Collections,省略很多代码
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public ListIterator<E> listIterator() {
return list.listIterator(); // Must be manually synched by user
}
public ListIterator<E> listIterator(int index) {
return list.listIterator(index); // Must be manually synched by user
}
}
手动同步的时候需要注意,既然我们关注的全局同步,在迭代器设置同步的时候,要保证锁定对象与add
等方法中对象相同。这个在后续补充说明,这里就不展开了。
CopyOnWriteArrayList
CopyOnWriteArrayList
是从 JDK 1.5 开始提供的,先看看add
方法的源码:
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
// 代码摘自 CopyOnWriteArrayList,省略很多代码
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 boolean addAll(Collection<? extends E> c) {
Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
if (cs.length == 0)
return false;
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (len == 0 && cs.getClass() == Object[].class)
setArray(cs);
else {
Object[] newElements = Arrays.copyOf(elements, len + cs.length);
System.arraycopy(cs, 0, newElements, len, cs.length);
setArray(newElements);
}
return true;
} finally {
lock.unlock();
}
}
private E get(Object[] a, int index) {
return (E) a[index];
}
/**
* {@inheritDoc}
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
return get(getArray(), index);
}
}
可以看到,CopyOnWriteArrayList
借助ReentrantLock
实现同步,在synchronized
优化之前,ReentrantLock
性能高于synchronized
。CopyOnWriteArrayList
也是通过数组实现的,但是在数组前面增加了volatile
关键字,实现了多线程情况下数组的可见性,更加安全。更重要的一点是,CopyOnWriteArrayList
在add
添加元素的时候,实现方式是重建数组对象,替换原来的数组引用。与ArrayList
的扩容方式相比,减少了空间,但是也增加了赋值数组的性能开销。在get
获取元素的时候,没有任何锁,直接数据返回。
CopyOnWriteArrayList
的迭代器时通过COWIterator
实现的,调用iterator
方法时,将当前队列中数组的快照赋值到迭代器中的数组引用上。如果原来的队列发生修改,队列中数组会指向别的引用,而迭代器中的数组不会发生变化,所以在多线程执行过程中,通过迭代器遍历数组,也可以修改队列中的数据。这种方式保障线程安全的同时,也可能会出现数据不一致的情况,只能是使用的使用多注意了。
static final class COWIterator<E> implements ListIterator<E> {
/** 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;
}
}
对比 CopyOnWriteArrayList 和 SynchronizedList
CopyOnWriteArrayList
和SynchronizedList
都实现了同步,实现方式上采用的是不同策略,各自的侧重点不同。
CopyOnWriteArrayList
侧重于读写分离,发生数据写操作(add
或remove
)时,会加锁,各个线程阻塞执行,执行过程会创建数据副本,替换对象引用;如果同时有读操作(get
或iterator
),读操作读取的是老数据,或者成为历史数据快照,或者成为缓存数据。这会造成读写同时发生时,数据不一致的情况,但是数据最终会一致。这种方式与数据库读写分离模式几乎相同,很多特性可以类比。
SynchronizedList
侧重数据强一致,也就是说当发生数据写操作(add
或remove
)时,会加锁,各个线程阻塞执行,而且也会通过相同的锁阻塞get
操作。
从CopyOnWriteArrayList
和SynchronizedList
两种不同事项方式,可以推断CopyOnWriteArrayList
在写少读多的场景中执行效率高,SynchronizedList
的读写操作效率很均衡,所以在写多读多、写多读少的场景执行效率都会高于CopyOnWriteArrayList
。借用网上的测试结果:
文末总结
synchronized
关键字在 JDK 8 之前性能比较差,可以看到 JDK1.5 之后实现的同步代码,很多是通过ReentrantLock
实现的。- 多线程场景中除了需要考虑同步外,还需要考虑数据可见性,可以通过
volatile
关键字实现。 ArrayList
完全没有同步操作,是非线程安全的CopyOnWriteArrayList
和SynchronizedList
属于线程安全队列CopyOnWriteArrayList
实现读写分离,适合场景是写少读多的场景SynchronizedList
要求数据强一致,是队列全局加锁方式,读操作也会加锁Vector
只是在迭代器遍历性能很差,如果不考虑全局锁定队列,单纯读操作和单独写操作性能与SynchronizedList
相差不大。
参考
- Why is Java Vector (and Stack) class considered obsolete or deprecated?
- CopyOnWriteArrayList 与 Collections.synchronizedList 的性能对比
- Collections.synchronizedList 、CopyOnWriteArrayList、Vector 介绍、源码浅析与性能对比
推荐阅读
你好,我是看山,公众号:看山的小屋,10 年老猿,开源贡献者。游于码界,戏享人生。
个人主页:https://www.howardliu.cn
个人博文:认识 Java 中的队列:Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList
CSDN 主页:http://blog.csdn.net/liuxinghao
CSDN 博文:认识 Java 中的队列:Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList