by shihang.mai

1. LongAdder

出现的目的:AtomicLong其实性能已经很好，但是它有一个弊端，就是当高并发下，多个线程竞争一个变量，并且只有一个线程能够CAS成功，其他全部自旋。而LongAdder的思想，就是将这个竞争分散，用base值+cell数组中元素的值 = 最终值解决。

1.1 LongAdder数据结构

LongAdder数据结构.png

1.2 Cell元素定位

public void add(long x) {
        Cell[] as; long b, v; int m; Cell a;
        if ((as = cells) != null || !casBase(b = base, b + x)) {
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[getProbe() & m]) == null ||
                !(uncontended = a.cas(v = a.value, v + x)))
                longAccumulate(x, null, uncontended);
        }
    }

1. 首先会去CAS设置base的值，成功并不会去更新Cell里面的值。

2. 当CAS设置base值失败，就会通过getProbe()与数组长度-1取模，定位到某一个Cell，然后CAS设置其值。其中数组长度是2的N次方，这是为了和hashmap的作用一样。

1.3 初始化Cell数组

else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
                boolean init = false;
                try {                           // Initialize table
                    if (cells == as) {
                        Cell[] rs = new Cell[2];
                        rs[h & 1] = new Cell(x);
                        cells = rs;
                        init = true;
                    }
                } finally {
                    cellsBusy = 0;
                }
                if (init)
                    break;
            }

1. 先CAS设置cellsBusy状态位=1
2. 初始化长度为2的Cell数组，并且通过threadLocalRandomProbe&1,定位Cell位置，并设置值。
3. 将cellsBusy重新变为0

1.4 Cell数组扩容

else if (n >= NCPU || cells != as)
                   collide = false;            // At max size or stale
else if (!collide)
                   collide = true; 
else if (cellsBusy == 0 && casCellsBusy()) {
                    try {
                        if (cells == as) {      // Expand table unless stale
                            Cell[] rs = new Cell[n << 1];
                            for (int i = 0; i < n; ++i)
                                rs[i] = as[I];
                            cells = rs;
                        }
                    } finally {
                        cellsBusy = 0;
                    }
                    collide = false;
                    continue;                   // Retry with expanded table
                }

扩容条件：当前cells数组长度小于当前机器CPU核数&&在Cell上CAS失败

1. 首先通过cas设置cellsBusy状态位为1，然后将其原来数组长度扩容2倍
2. 将原来的数据复制到新的cell数组

1.5 细节的巧妙

• 线程访问分配的Cell元素有冲突后如何处理

重新计算当前线程的随机值threadLocalRandomProbe，减少下次访问cells元素时冲突的机会

• 如何保证线程操作被分配的Cell元素的原子性

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

        // Unsafe mechanics
        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 (Exception e) {
                throw new Error(e);
            }
        }
    }

Cell类有一个volatile修饰的value保证线程间的可见性，用CAS保证线程更新时的线程安全。还有@Contended防止缓存伪共享

2. LongAccumulator

LongAdder只是它的一个特例,LongAccumulator是个累加器

public LongAccumulator(LongBinaryOperator accumulatorFunction,
                      long identity) {
   this.function = accumulatorFunction;
   base = this.identity = identity;
}

@FunctionalInterface
public interface LongBinaryOperator {

/**
    * Applies this operator to the given operands.
    *
    * @param left the first operand
    * @param right the second operand
    * @return the operator result
    */
   long applyAsLong(long left, long right);
}

下面使用LongAccumulator来模拟LongAdder

public class TestLongAccumulator {

   public static void main(String[] args) {
       LongAccumulator longAccumulator = new LongAccumulator((a, b) -> {
           return a + b;
       }, 0);
       for (int i = 0; i < 1000; i++) {
           longAccumulator.accumulate(1);
           System.out.println(longAccumulator);
       }
   }
}

就是一个可以自定义行为的"累加器",其实可以做加减乘除的