Java算法-力扣leetcode-45. 跳跃游戏 II

一、java8原子类LongAdder

在Java并发���程(2)中有关于AtomicInteger的介绍. AtomicInteger通过CAS非阻塞的原子操作提升了并发性能. 但随着线程数量增大对共享资源的竞争提升,大量线程竞争失败会进入到自旋中,消耗了cpu资源.

JDK8中新增了原子类LongAdder, 弥补AtomicLong的上述缺点. AtomicInteger的缺陷在于共享资源只有一个,LongAdder的思路是将共享资源复制多份,让多个资源去被竞争.在使用的时候再把多个共享资源的数据整合计算得到真实的数据.

从原码具体看下实现

LongAdder longAdder = new LongAdder();for (int i = 0; i  
LongAdder的继承关系
 
public class LongAdder extends Striped64 implements Serializable
 
构造函数
 
public LongAdder() {}
 
add方法
 
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)  
Cell[] as这里的cells是父类定义的,cells可以理解成上边说的共享资源复制了多份.保存在一个数组中
 
transient volatile Cell[] cells;
 
Cell的定义
 

• 使用Contended修饰,避免伪共享
• 其余代码和上一章介绍的atomicInteger内存基本一致

  @sun.misc.Contended static final class Cell {    //内部维护了long类型的value    volatile long value;        //构造函数    Cell(long x) { value = x; }        //CAS操作    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;        //初始化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);        }    }}

  继续看add方法:

  • 如果cells为空, 就执行casBase
  • base也是父类定义的,是基值变量. 一开始并非不高的情况下不会创建多个副本cells. 只会对基础值base做操作.
  • casBase即熟悉的cas原子非阻塞操作

     if ((as = cells) != null || !casBase(b = base, b + x)) {

    final boolean casBase(long cmp, long val) {    return UNSAFE.compareAndSwapLong(this, BASE, cmp, val);}

    • uncontended:表示运算操作是否成功
    • m是cells的数组大小
    • a = as[getProbe() & m]是获取当前线程可操作的cell
    • 如果获取到了cell 就进行cas操作, 操作结果可能为false cas可能自旋几次会失败
    • 失败了或者没有获取到cell执行longAccumulate

      boolean uncontended = true;if (as == null || (m = as.length - 1)  
      longAccumulate的内容特别多,这里会对cells数组初始化和扩容
       
      final void longAccumulate(long x, LongBinaryOperator fn,                          boolean wasUncontended) {    //for循环前主要获取h的值。h表示当前线程的hash值 对应在cells下标                     int h;    if ((h = getProbe()) == 0) {        ThreadLocalRandom.current(); // force initialization        h = getProbe();                //true表示没有竞争        wasUncontended = true;            }        //是否需要扩容    boolean collide = false;    // True if last slot nonempty        //CAS的for循环     for (;;) {            Cell[] as; Cell a; int n; long v;        if ((as = cells) != null && (n = as.length) > 0) {                    //当前线程对应的cess是否为空            if ((a = as[(n - 1) & h]) == null) {                            //cellsBusy是标识当前是否有线程在对cells在做初始化或者扩容.                if (cellsBusy == 0) {       // Try to attach new Cell                                    创建一个Cell                    Cell r = new Cell(x);   // Optimistically create                                        //cellsBusy标识当前没有线程在对cells在做初始化或者扩容. 并将                           cellsBusy标识置为1                   if (cellsBusy == 0 && casCellsBusy()) {                        boolean created = false;                        try {               // Recheck under lock                            Cell[] rs; int m, j;                            if ((rs = cells) != null &&                                (m = rs.length) > 0 &&                                rs[j = (m - 1) & h] == null) {                                                                //将新建的cell加进数组                                rs[j] = r;                                                                created = true;                            }                        } finally {                            cellsBusy = 0;                        }                                                //创建成功了跳出循环                        if (created)                            break;                                                    //失败了就是当前位置已经有了cell继续循环                        continue;           // Slot is now non-empty                    }                }                                //获取cellsBusy标识失败                collide = false;                            }                        //上面位置已经有了cell            else if (!wasUncontended)    // CAS already known to fail                            //是否存在竞争标志设为true                wasUncontended = true;      // Continue after rehash                         //未发生锁竞争 尝试将值累加在a上             else if (a.cas(v = a.value, ((fn == null) ? v + x :                                         fn.applyAsLong(v, x))))                //尝试成功                                         break;                                            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