为了解决高并发下多线程对一个变量CAS争夺失败后进行自旋而造成的降低并发性能问题，LongAdder在内部维护多个Cell元素(一个动态的Cell数组)来分担对单个变量进行争夺的开销。
下面围绕以下话题从源码角度来分析LongAdder的实现:
1.LongAdder 的结构是怎样的
LongAdder类继承自Striped64类，在Striped64内部维护着三个变量。
LongAdder的真是值是base的值与cell数组里面所有cell元素中value值的累加。
1⃣️base是个基础值，默认为0。
2⃣️cellsBusy用来实现自旋锁，状态值只有0和1。
3⃣️cells 动态Cell数组。
cell的构造很简单，其内部维护了一个被声明为volatile的变量。
@jdk.internal.vm.annotation.Contended static final class Cell
volatile long value;
2.当前线程应该访问cell数组里面的哪一个cell元素
当前线程访问cells数组中的哪个cell是通过 getProbe() & m 进行计算的，m是数组长度减1
3.如何初始化cell数组
cellBusy为0表示cells数组还未初始化或扩容，为1 表示cells数组在被初始化或扩容，初始化cells数组元素个数为2，然后用h&1计算当前线程应该访问cell数组的哪个位置，然后标示数组已经被初始化完，最后重置cellsbusy标记为0。
4.cell数组如何扩容
当cells的元素个数小于当前及其cpu的个数并且当前多个线程访问cells中同一个元素，从而导致冲突使其中一个线程cas失败才会进行扩容操作扩容先通过cas设置标示为cellsbusy为1才开始扩容，将容量扩充为之前的2倍，并辅助cell元素到扩容数组
5.线程访问分配的cell元素有冲突后如何处理
当前线程调用add方法并根据当前线程的随机数threadLocalRandomProbe和cells元素个数计算到要访问的cell元素下标，若发现对应下标元素的值为null， 则新增一个cell元素到cells数组，在新增至数组前竞争标示设置cellsbusy为1，若果cas失败的线程重新计算当前线程的随机值以减少下次访问cells元素时的冲突机会
6.如何保证线程操作被分配的cell元素的原子性
cas函数通过CAS操作，保证了当前线程更新时被分配的cell元素中value值的原子性
final boolean cas(long cmp,long val) {
return VALUE.compareAndSet(this, cmp, val);
}
private static final VarHandleVALUE;
static {
try {
MethodHandles.Lookup l = MethodHandles.lookup();
VALUE = l.findVarHandle(Cell.class,"value",long.class);
}catch (ReflectiveOperationException e) {
throw new ExceptionInInitializerError(e);
}
}
源码：
public void add(long x) {
Cell[] cs;long b, v;int m; Cell c;
if ((cs =cells) !=null || !casBase(b =base, b + x)) {
boolean uncontended =true;
if (cs ==null || (m = cs.length -1) <0 ||
(c = cs[getProbe() & m]) ==null ||
!(uncontended = c.cas(v = c.value, v + x)))
longAccumulate(x,null, uncontended);
}
}
final void longAccumulate(long x, LongBinaryOperator fn,
boolean wasUncontended) {
// 初始化当前线程的变量 threadLocalRandonProbe的值
int h;
if ((h = getProbe()) == 0) {
ThreadLocalRandom.current(); // 强制初始化
h = getProbe();
wasUncontended = true;
}
boolean collide = false; // 如果最后一个插槽非空则为真
done: for (;;) {
Cell[] cs; Cell c; int n; long v;
// (7)
if ((cs = cells) != null && (n = cs.length) > 0) {
// (8)
if ((c = cs[(n - 1) & h]) == null) {
if (cellsBusy == 0) { // 尝试附加新的Cell
Cell r = new Cell(x); // 乐观地创造
if (cellsBusy == 0 && casCellsBusy()) {
try { // 锁定下重新检查
Cell[] rs; int m, j;
if ((rs = cells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
break done;
}
} finally {
cellsBusy = 0;
}
continue; // 插槽现在非空
}
}
collide = false;
}
else if (!wasUncontended) // 已知CAS会失败
wasUncontended = true; // 重新哈希后继续
// 当前cell存在，则执行cas设置(9)
else if (c.cas(v = c.value,
(fn == null) ? v + x : fn.applyAsLong(v, x)))
break;
// 当前cell数组元素个数大于cpu个数(10)
else if (n >= NCPU || cells != cs)
collide = false; // 最大尺寸或陈旧 stale
// 是否有冲突(11)
else if (!collide)
collide = true;
// 如果当前元素个数没有达到cpu个数并且有冲突则扩容(12)
else if (cellsBusy == 0 && casCellsBusy()) {
try {
if (cells == cs)// 除非过时，否则扩展表格
// 12。1
cells = Arrays.copyOf(cs, n << 1);
} finally {
// 12。2
cellsBusy = 0;
}
// 12。3
collide = false;
continue; // 使用扩展表重试
}
// （13）为了能够找到一个空闲的cell，重新计算hash值，xorshift算法生成随机数
h = advanceProbe(h);
}
// 初始化cell数组(14)
// cellBusy为0表示cells数组还未初始化或扩容
// 为1 表示cells数组在被初始化或扩容 casCellsBusy cas设置标示为1
else if (cellsBusy == 0 && cells == cs && casCellsBusy()) {
try { // 初始化表
if (cells == cs) {
// 14.1
Cell[] rs = new Cell[2];
// 14.2
rs[h & 1] = new Cell(x);
cells = rs;
break done;
}
} finally {
// 14.3
cellsBusy = 0;
}
}
// 退回使用base
else if (casBase(v = base,
(fn == null) ? v + x : fn.applyAsLong(v, x)))
break done;
}
}
小结：该内通过内部cells数组分担了高并发下多线程同时对一个原子变量进行更新时的竞争量，让多个线程可以同时对cells数组里面的元素进行并行的更新操作。另外数组元素cell使用了@sum.misc.Contended注解进行修饰，这避免了cells数组内多个原子变量被放入同一个缓存行，也就是避免了伪共享，这对性能也是一个提升。
