LongAdder 和 Striped64

简介

LongAdder是Java8新增的一个原子操作类，主要用于高并发下的long类型计数和累加操作。LongAdder使用一个或多个变量的总和来维护计数器的值，并且在多线程竞争下，这个变量集可以动态增长。 **

LongAdder与AtomicLong

**LongAdder与AtomicLong相比：**在没有并发的情况下，两者具有相似的特征；但是在高并发情况下，LongAdder的效率明显高于AtomicLong，但是会使用更多的空间。

先来看下AtomicLong为什么在高并发下效率会比较低。AtomicLong在自增的时候会调用Unsage#getAndAddLong()方法，该方法在cas失败时会进行自旋，直至成功。在高并发下，cas失败的几率非常高，会浪费大量的时间，也就降低了效率。

//sun.misc.Unsafe#getAndAddLong
public final long getAndAddLong(Object o, long offset, long delta) {
    long v;
    do {
        v = getLongVolatile(o, offset);
    } while (!compareAndSwapLong(o, offset, v, v + delta));
    return v;
}

那么LongAdder是如何做到高效率的呢？相对于AtomicLong的单个value计数，LongAdder在并发下，会使用一个Cell数组（并且可以动态扩容）来帮助计数，即使用多个value，不同的线程可以在不同的Cell上进行计数，从而减少了线程竞争，提高了并发效率。本质是使用空间换时间的思想。

LongAdder与Striped64

LongAdder的实现主要依赖于Striped64类，Striped64是Java8中新增的用来支持累加器的并发组件，Striped64的设计思路是在竞争激烈的时候尽量分散竞争，在实现上，Striped64维护了一个base变量和一个Cell数组，计数线程会首先试图更新base变量，如果成功则退出计数，否则会认为当前竞争是很激烈的，那么就会通过Cell数组来分散计数，Striped64根据线程来计算哈希，然后将不同的线程分散到不同的Cell数组的index上，然后这个线程的计数内容就会保存在该Cell的位置上面。

Cell类

先来看一下上文提到的Cell类，可以看到，Cell类只定义了一个value字段和cas方法，相当于一个简易版的AtomicLong类。 ps: Contended注解目的是为了防止变量的伪共享。

@sun.misc.Contended static final class Cell {
    volatile long value;
    Cell(long x) { value = x; }
    final boolean cas(long cmp, long val) {
        return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
    }

    private static final sun.misc.Unsafe UNSAFE;
    private static final long valueOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> ak = Cell.class;
            valueOffset = UNSAFE.objectFieldOffset
                (ak.getDeclaredField("value"));
        } //省略catch
    }
}

Striped64类

成员变量

核心方法

LongAdder#add

先看一下LongAdder是怎么使用Striped64的成员变量以及方法来进行累加的。调用到Striped64#longAccumulate方法的情况：

cells为空，但是casBase失败了，说明base的累加发生了竞争，则需要longAccumulate方法初始化cells。
cells不为空，但是本次线程对应的cell为空，则通过longAccumulate方法创建cell。
cells不为空，本次线程对应的cell也不为空，但是对该cell的cas操作失败了，则通过longAccumulate方法重新计算hash并重试，或对cells数组进行扩容

Striped64#longAccumulate

接下来看一下Striped64#longAccumulate方法的具体实现。

LongAdder和AtomicLong性能对比

如上图所示，测试了单线程、多线程下，2000ms时间内，AtomicLong和LongAdder的累加数量。结果如下所示：

other

代码