乐趣区

关于java:源码分析CopyOnWriteArrayList-中的隐藏的知识你Get了吗

前言

本觉 CopyOnWriteArrayList 过于简略,寻思看名字就能晓得外部的实现逻辑,所以没有写这篇文章的想法,最近又认真看了下 CopyOnWriteArrayList 的源码实现,大体逻辑没有意外,不过还是发现很多有意思的中央,固留此篇文章分享之。

看完这篇文章你会理解到:

  • CopyOnWriteArrayList 的实现原理,扩容机制。
  • CopyOnWriteArrayList 的读写拆散,弱一致性。
  • CopyOnWriteArrayList 的性能如何。
  • CopyOnWriteArrayList 批改元素时,为什么雷同值也要从新赋值(作者 Doug Lea 这么写都是有情理的)。
  • CopyOnWriteArrayList 在高版本 JDK 的实现有什么不同,为什么。

<!– more –>

线程平安 List

在 Java 中,线程平安的 List 不止一个,除了明天的配角 CopyOnWriteArrayList 之外,还有 Vector 类和 SynchronizedList 类,它们都是线程平安的 List 汇合。在介绍 CopyOnWriteArrayList 之前,先简略介绍下另外两个。

如果你尝试你查看它们的源码,你会发现有点不对头,并发汇合不都是在 java.util.concurrent 包中嘛,为什么Vector 类和 SynchronizedList 类 这两个是在 java.util 包里呢?

的确是这样的,这两个线程平安的 List 和线程平安的 HashTable 是一样的,都是比较简单粗犷的实现形式,间接办法上减少 synchronized 关键字实现的,而且不论增删改查,通通加上,即便是 get 办法也不例外,没错,就是这么粗犷。

Vector 类的 get 办法:

// Vector 中的 get 操作增加了 synchronized
public synchronized E get(int index) {if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

SynchronizedList 类的 ge t 办法:

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

同学无妨思考一下,其实在 get 办法上增加同步机制也是有起因的,尽管升高了效率,然而能够让写入的数据立刻能够被查问到,这也保障了数据的强一致性。另外下面对于 synchronized 简略粗犷的形容也是不够精确的,因为在高版本的 JDK 中,synchronized 曾经能够依据运行时状况,主动调整锁的粒度,前面介绍 CopyOnWriteArrayList 时会再次讲到。

CopyOnWriteArrayList

在 JDK 并发包中,目前对于 List 的并发汇合,只有 CopyOnWriteArrayList 一个。下面简略介绍了 Vector 和 SynchronizdList 的粗犷实现,既然还有 CopyOnWriteArrayList,那么它肯定是和下面两种是有区别的,作为惟一的并发 List,它有什么不同呢?

在探索 CopyOnWriteArrayList 的实现之前,咱们无妨先思考一下,如果是你,你会怎么来实现一个线程平安的 List。

  1. 并发读写时该怎么保障线程平安呢?
  2. 数据要保障强一致性吗?数据读写更新后是否立即体现?
  3. 初始化和扩容时容量给多少呢?
  4. 遍历时要不要保证数据的一致性呢?须要引入 Fail-Fast 机制吗?

通过类名咱们大抵能够猜测到 CopyOnWriteArrayList 类的实现思路:Copy-On-Write, 也就是写时复制策略;开端的 ArrayList 示意数据寄存在一个数组里。在对元素进行增删改时,先把现有的数据数组拷贝一份,而后增删改都在这个拷贝数组上进行,操作实现后再把原有的数据数组替换成新数组。这样就实现了更新操作。

然而这种写入时复制的形式必定会有一个问题,因为每次更新都是用一个新数组替换掉老的数组,如果不巧在更新时有一个线程正在读取数据,那么读取到的就是老数组中的老数据。其实这也是 读写拆散 的思维,放弃数据的强一致性来换取性能的晋升

剖析源码 (JDK8)

下面曾经说了,CopyOnWriteArrayList 的思维是 写时复制 读写拆散,它的外部保护着一个应用 volatile 润饰的数组,用来寄存元素数据。

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

CopyOnWriteArrayList 类中办法很多,这里不会一一介绍,上面会剖析其中的几个罕用的办法,这几个办法了解后根本就能够把握 CopyOnWriteArrayList 的实现原理。

构造函数

CopyOnWriteArrayList 的构造函数一共有三个,一个是无参结构,间接初始化数组长度为 0;另外两个传入一个汇合或者数组作为参数,而后会把汇合或者数组中的元素间接提取进去赋值给 CopyOnWriteArrayList 外部保护的数组。

// 间接初始化一个长度为 0 的数组
public CopyOnWriteArrayList() {setArray(new Object[0]);
}
// 传入一个汇合,提取汇合中的元素赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(Collection<? extends E> 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);
}
// 传入一个数组,数组元素提取后赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(E[] toCopyIn) {setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

构造函数是实例创立时调用的,没有线程平安问题,所以构造方法都是简略的赋值操作,没有非凡的逻辑解决。

新增元素

元素新增依据入参的不同有好几个,然而原理都是一样的,所以上面只贴出了 add(E e) 的实现形式,是通过一个 ReentrantLock 锁保障线程平安的。

/**
 * 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 e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加锁
    try {Object[] elements = getArray(); // 获取数据数组
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); // 拷贝一个数据数组,长度 +1
        newElements[len] = e; // 退出新元素
        setArray(newElements); // 用新数组替换掉老数组
        return true;
    } finally {lock.unlock();
    }
}

具体步骤:

  1. 加锁,获取目前的数据数组开始操作(加锁保障了同一时刻只有一个线程进行减少 / 删除 / 批改操作)。
  2. 拷贝目前的数据数组,且长度减少一。
  3. 新数组中放入新的元素。
  4. 用新数组替换掉老的数组。
  5. finally 开释锁。

因为每次 add 时容量只减少了 1,所以每次减少时都要创立新的数组进行数据复制,操作实现后再替换掉老的数据,这必然会升高数据新增时候的性能。上面通过一个简略的例子测试 CopyOnWriteArrayList、Vector、ArrayList 的新增和查问性能。

public static void main(String[] args) {CopyOnWriteArrayList<Object> 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; i++) {list.add(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(list.getClass().getName() + ".size=" + list.size() + ",add 耗时:" + (end - start) + "ms");
}
public static void get(List list) {long start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {Object object = list.get(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(list.getClass().getName() + ".size=" + list.size() + ",get 耗时:" + (end - start) + "ms");
}

从测得的后果中能够看到 CopyOnWriteArrayList 的新增耗时最久,其次是加锁的 Vector(Vector 的扩容默认是两倍)。而在获取时最快的是线程不平安的 ArrayList,其次是 CopyOnWriteArrayList,而 Vector 因为 Get 时加锁,性能最低。

java.util.concurrent.CopyOnWriteArrayList.size=100000,add 耗时:2756ms
java.util.Vector.size=100000,add 耗时:4ms
java.util.ArrayList.size=100000,add 耗时:3ms
java.util.concurrent.CopyOnWriteArrayList.size=100000,get 耗时:4ms
java.util.Vector.size=100000,get 耗时:5ms
java.util.ArrayList.size=100000,get 耗时:2ms

批改元素

批改元素和新增元素的思维是统一的,通过 ReentrantLock 锁保障线程安全性,实现代码也比较简单,原本不筹备写进来的,然而在看源码时发现一个十分有意思的中央,看上面的代码。

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();
    }
}

通过源码能够看到在批改元素前会先比拟批改前后的值是否相等,而在相等的状况下,仍旧 setArray(elements); 这就很微妙了,到底是为什么呢?想理解其中的起因须要理解下 volatile 的特殊作用,通过上面这个代码例子阐明。

// initial conditions
int nonVolatileField = 0;
CopyOnWriteArrayList<String> list = /* a single String */

// Thread 1
nonVolatileField = 1;                 // (1)
list.set(0, "x");                     // (2)

// Thread 2
String s = list.get(0);               // (3)
if (s == "x") {int localVar = nonVolatileField;  // (4)
}
// 例子来自:https://stackoverflow.com/questions/28772539/why-setarray-method-call-required-in-copyonwritearraylist

要想了解例子中的非凡之处,首先你要晓得 volatile 能够避免指令重排,其次要理解 happens-before 机制。说简略点就是它们能够保障代码的执行前后程序。

比方下面例子中的代码,1 会在 2 之前执行,3 会在 4 之前执行,这都没有疑难。还有一条是 volatile 润饰的属性写会在读之前执行,所以 2 会在 3 之前执行。而执行程序还存在传递性。所以最终 1 会在 4 之前执行。这样 4 获取到的值就是步骤 1 为 nonVolatileField 赋的值。如果 CopyOnWriteArrayList 中的 set 办法内没有为雷同的值进行 setArray,那么下面说的这些就都不存在了。

删除元素

remove 删除元素办法一共有三个,这里只看public E remove(int index) 办法,原理都是相似的。

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(); // 解锁
    }
}

代码还是很简略的,应用 ReentrantLock 独占锁保障操作的线程安全性,而后应用删除元素后的残余数组元素拷贝到新数组,应用新数组替换老数组实现元素删除,最初开释锁返回。

获取元素

获取下标为 index 的元素,如果元素不存在,会抛出IndexOutOfBoundsException 异样。

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];
}

首先看到这里是没有任何的加锁操作的,而获取指定地位的元素又分为了两个步骤:

  1. getArray() 获取数据数组。
  2. get(Object[] a, int index) 返回指定地位的元素。

很有可能在第一步执行实现之后,步骤二执行之前,有线程对数组进行了更新操作。通过下面的剖析咱们晓得更新会生成一个新的数组,而咱们第一步曾经获取了老数组,所以咱们在进行 get 时仍旧在老数组上进行,也就是说 另一个线程的更新后果没有对咱们的本次 get 失效 。这也是下面提到的 弱一致性 问题。

迭代器的弱一致性

List<String> list = new CopyOnWriteArrayList<>();
list.add("www.wdbyte.com");
list.add("未读代码");

Iterator<String> iterator = list.iterator();
list.add("java");
while (iterator.hasNext()) {String next = iterator.next();
    System.out.println(next);
}

当初 List 中增加了元素 www.wdbyte.com未读代码,在拿到迭代器对象后,又增加了新元素 java , 能够看到遍历的后果没有报错也没有输入 java。也就是说拿到迭代器对象后,元素的更新不可见。

www.wdbyte.com
未读代码

这是为什么呢?要先从 CopyOnWriteArrayList 的 iterator() 办法的实现看起。

public Iterator<E> iterator() {return new COWIterator<E>(getArray(), 0);
}
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;
    }
......

能够看到在获取迭代器时,先 getArray() 拿到了数据数组 而后传入到 COWIterator 结构器中,接着赋值给了 COWIterator 中的 snapshot 属性,联合下面的剖析后果,能够晓得每次更新都会产生新的数组,而这里应用的仍旧是老数组,所以更新操作不可见,也就是下面屡次提到的 弱一致性

新版变动

下面的源码剖析都是基于 JDK 8 进行的。写文章时顺便看了下新版的实现形式有没有变动,还真的有挺大的扭转,次要体现在加锁的形式上,或者是因为 JVM 起初引入了 synchronized 锁降级策略,让 synchronized 性能有了不少晋升,所以用了 synchronized 锁替换了老的 ReentrantLock 锁。

新增:

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;
    }
}

批改:

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;
    }
}

总结

通过下面的剖析,失去上面几点对于 CopyOnWriteArrayList 的总结。

  1. CopyOnWriteArrayList 采纳读写拆散,写时复制形式实现线程平安,具备弱一致性。
  2. CopyOnWriteArrayList 因为每次写入时都要扩容复制数组,写入性能不佳。
  3. CopyOnWriteArrayList 在批改元素时,为了保障 volatile 语义,即便元素没有任何变动也会从新赋值,
  4. 在高版 JDK 中,得益于 synchronized 锁降级策略,CopyOnWriteArrayList 的加锁形式采纳了 synchronized。

参考:

  1. Why setArray() method call required in CopyOnWriteArrayList.

https://stackoverflow.com/que…

  1. What does volatile do?

http://www.cs.umd.edu/~pugh/j…

JDK 源码剖析系列文章

  1. 汇合 – 最通俗易懂的 HashMap 源码剖析解读
  2. 汇合 – 还不懂 ConcurrentHashMap?这份源码剖析理解一下
  3. 汇合 – ArrayList 和 LinkedList 如何实现的?我看你还有机会!

最初的话

文章曾经收录在 Github.com/niumoo/JavaNotes,欢送 Star 和指教。更有一线大厂面试点,Java 程序员须要把握的外围常识等文章,也整顿了很多我的文字,欢送 Star 和欠缺,心愿咱们一起变得优良。

文章有帮忙能够点个「」或「 分享 」,都是反对,我都喜爱!
文章每周继续更新,要实时关注我更新的文章以及分享的干货,能够关注「未读代码」公众号或者我的博客。

退出移动版