`

从LongAdder 看更高效的无锁实现

 
阅读更多

接触到AtomicLong的原因是在看guava的LoadingCache相关代码时,关于LoadingCache,其实思路也非常简单清晰:用模板模式解决了缓存不命中时获取数据的逻辑,这个思路我早前也正好在项目中使用到。

言归正传,为什么说LongAdder引起了我的注意,原因有二:
1. 作者是Doug lea ,地位实在举足轻重。
2. 他说这个比AtomicLong高效。
我们知道,AtomicLong已经是非常好的解决方案了,涉及并发的地方都是使用CAS操作,在硬件层次上去做 compare and set操作。效率非常高。
 
因此,我决定研究下,为什么LongAdder比AtomicLong高效。
首先,看LongAdder的继承树:
la1
 
继承自Striped64,这个类包装了一些很重要的内部类和操作。稍候会看到。
正式开始前,强调下,我们知道,AtomicLong的实现方式是内部有个value 变量,当多线程并发自增,自减时,均通过cas 指令从机器指令级别操作保证并发的原子性。
 
再看看LongAdder的方法:
la2
 
 
怪不得可以和AtomicLong作比较,连API都这么像。我们随便挑一个API入手分析,这个API通了,其他API都大同小异,因此,我选择了add这个方法。事实上,其他API也都依赖这个方法。
 
la3
 
LongAdder中包含了一个Cell 数组,Cell是Striped64的一个内部类,顾名思义,Cell 代表了一个最小单元,这个单元有什么用,稍候会说道。先看定义:
 
la4
 
Cell内部有一个非常重要的value变量,并且提供了一个CAS更新其值的方法。
回到add方法:
la3
这里,我有个疑问,AtomicLong已经使用CAS指令,非常高效了(比起各种锁),LongAdder如果还是用CAS指令更新值,怎么可能比AtomicLong高效了? 何况内部还这么多判断!!!
 
这是我开始时最大的疑问,所以,我猜想,难道有比CAS指令更高效的方式出现了? 带着这个疑问,继续。
第一if 判断,第一次调用的时候cells数组肯定为null,因此,进入casBase方法:
la5
 
原子更新base没啥好说的,如果更新成功,本地调用开始返回,否则进入分支内部。
什么时候会更新失败? 没错,并发的时候,好戏开始了,AtomicLong的处理方式是死循环尝试更新,直到成功才返回,而LongAdder则是进入这个分支。
 
分支内部,通过一个Threadlocal变量threadHashCode 获取一个HashCode对象,该HashCode对象依然是Striped64类的内部类,看定义:
 
la6
 
有个code变量,保存了一个非0的随机数随机值。
 
回到add方法:
la3
 
拿到该线程相关的HashCode对象后,获取它的code变量,as[(n-1)h] 这句话相当于对h取模,只不过比起取摸,因为是 与 的运算所以效率更高。
 
计算出一个在Cells 数组中当先线程的HashCode对应的 索引位置,并将该位置的Cell 对象拿出来更新cas 更新它的value值。
 
当然,如果as 为null 并且更新失败,才会进入retryUpdate方法。
 
 
看到这里我想应该有很多人明白为什么LongAdder会比AtomicLong更高效了,没错,唯一会制约AtomicLong高效的原因是高并发,高并发意味着CAS的失败几率更高, 重试次数更多,越多线程重试,CAS失败几率又越高,变成恶性循环,AtomicLong效率降低。
 
那怎么解决? LongAdder给了我们一个非常容易想到的解决方案: 减少并发,将单一value的更新压力分担到多个value中去,降低单个value的 “热度”,分段更新!!!
 
  这样,线程数再多也会分担到多个value上去更新,只需要增加cell就可以降低 value的 “热度”  AtomicLong中的 恶性循环不就解决了吗? cells 就是用来存储这个 “段”的,每个段又叫做cell, cell中的value 就是存放更新值的, 这样,当我需要总数时,把cells 中的value都累加一下不就可以了么!!
 
当然,聪明之处远远不仅仅这里,在看看add方法中的代码,casBase方法可不可以不要,直接分段更新,上来就计算 索引位置,然后更新value?
答案是不好,不是不行,因为,casBase操作等价于AtomicLong中的cas操作,要知道,LongAdder中分段更新这样的处理方式是有坏处的,分段操作必然带来空间上的浪费,可以空间换时间,但是,能不换就不换,要空间时间都节约~! 所以,casBase操作保证了在低并发时,不会立即进入分支做分段更新操作,因为低并发时,casBase操作基本都会成功,只有并发高到一定程度了,才会进入分支,所以,Doug Lead对该类的说明是: 低并发时LongAdder和AtomicLong性能差不多,高并发时LongAdder更高效!
 
la7
 
但是,Doung Lea 还是没这么简单,聪明之处还没有结束……
 
虽然如此,retryUpdate中做了什么事,也基本略知一二了,因为cell中的value都更新失败(说明该索引到这个cell的线程也很多,并发也很高时) 或者cells数组为空时才会调用retryUpdate,
 
因此,retryUpdate里面应该会做两件事:
1. 扩容,将cells数组扩大,降低每个cell的并发量,同样,这也意味着cells数组的rehash动作。
2. 给空的cells变量赋一个新的Cell数组。
 
是不是这样呢? 继续看代码:
代码比较长,变成文本看看,为了方便大家看if else 分支,对应的  { } 我在括号后面用分支XXX 标注出来
 
可以看到,这个时候Doug Lea才愿意使用死循环保证更新成功~!
因为进入这个方法的几率已经非常低了。
 
final void retryUpdate(long x, HashCode hc, boolean wasUncontended) {
      int h = hc.code;
      boolean collide = false;                // True if last slot nonempty
      for (;;) {
          Cell[] as; Cell a; int n; long v;
          if ((as = cells) != null && (n = as.length) > 0) {// 分支1
              if ((a = as[(n - 1) & h]) == null) {
                  if (busy == 0) {            // Try to attach new Cell
                      Cell r = new Cell(x);   // Optimistically create
                      if (busy == 0 && casBusy()) {
                          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) {
                                  rs[j] = r;
                                  created = true;
                              }
                          } finally {
                              busy = 0;
                          }
                          if (created)
                              break;
                          continue;           // Slot is now non-empty
                      }
                  }
                  collide = false;
              }
              else if (!wasUncontended)       // CAS already known to fail
                  wasUncontended = true;      // Continue after rehash
              else if (a.cas(v = a.value, fn(v, x)))
                  break;
              else if (n >= NCPU || cells != as)
                  collide = false;            // At max size or stale
              else if (!collide)
                  collide = true;
              else if (busy == 0 && casBusy()) {
                  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 {
                      busy = 0;
                  }
                  collide = false;
                  continue;                   // Retry with expanded table
              }
              h ^= h << 13;                   // Rehash                 h ^= h >>> 17;
              h ^= h << 5;
          }
          else if (busy == 0 && cells == as && casBusy()) {//分支2
              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 {
                  busy = 0;
              }
              if (init)
                  break;
          }
          else if (casBase(v = base, fn(v, x)))
              break;                          // Fall back on using base
      }
      hc.code = h;                            // Record index for next time
  }
分支2中,为cells为空的情况,需要new 一个Cell数组。
分支1分支中,略复杂一点点:
注意,几个分支中都提到了busy这个方法,这个可以理解为一个CAS实现的锁,只有在需要更新cells数组的时候才会更新该值为1,如果更新失败,则说明当前有线程在更新cells数组,当前线程需要等待。重试。
回到分支1中,这里首先判断当前cells数组中的索引位置的cell元素是否为空,如果为空,则添加一个cell到数组中。
否则更新 标示冲突的标志位wasUncontended 为 true ,重试。
否则,再次更新cell中的value,如果失败,重试。
。。。。。。。一系列的判断后,如果还是失败,下下下策,reHash,直接将cells数组扩容一倍,并更新当前线程的hash值,保证下次更新能尽可能成功。

可以看到,LongAdder确实用了很多心思减少并发量,并且,每一步都是在”没有更好的办法“的时候才会选择更大开销的操作,从而尽可能的用最最简单的办法去完成操作。追求简单,但是绝对不粗暴。

————————————————分割线——————————————————————-

昨天在coolshell    投稿后 (文章在这里) 和左耳朵耗子简单讨论了下,发现左耳朵耗子对读者思维的引导还是非常不错的,在第一次发现这个类后,对里面的实现又提出了更多的问题,引导大家思考,值得学习,赞一个~

我们 发现的问题有这么几个:

1. jdk 1.7中是不是有这个类?
我确认后,结果如下:    jdk-7u51版本上 上还没有  但是jdk-8u20 版本上已经有了。代码基本一样 ,增加了对double类型的支持和删除了一些冗余的代码。

2. base有没有参与汇总?
base在调用intValue等方法的时候是会汇总的:

LA10
3. base的顺序可不可以调换?
左耳朵耗子,提出了这么一个问题: 在add方法中,如果cells不会为空后,casBase方法一直都没有用了?

因此,我想可不可以调换add方法中的判断顺序,比如,先做casBase的判断,结果是 不调换可能更好,调换后每次都要CAS一下,在高并发时,失败几率非常高,并且是恶性循环,比起一次判断,后者的开销明显小很多,还没有副作用。因此,不调换可能会更好。

4. AtomicLong可不可以废掉?
我的想法是可以废掉了,因为,虽然LongAdder在空间上占用略大,但是,它的性能已经足以说明一切了,无论是从节约空的角度还是执行效率上,AtomicLong基本没有优势了,具体看这个测试(感谢coolshell读者Lemon的回复):http://blog.palominolabs.com/2014/02/10/java-8-performance-improvements-longadder-vs-atomiclong/

 

原文地址: http://coolshell.cn/articles/11454.html

分享到:
评论

相关推荐

    无锁队列Disruptor超详细教程

    Disruptor通过Sequence、Sequencer和Sequence Barrier实现无锁操作,确保在高并发下仍能保持低延迟。 #### (3) 依赖关系管理 Disruptor使用Sequence Barrier来管理消费者和生产者间的依赖,以及消费者间的依赖。它...

    Java并发工具类LongAdder原理实例解析

    LongAdder的实现原理图可以分为三个部分:Cells数组、基值变量base和sum()方法。Cells数组用于存储多个线程的操作结果,基值变量base用于存储初始值,sum()方法用于将所有Cell数组中的value和base累加作为返回值。 ...

    JDK8中新增的原子性操作类LongAdder详解

    在实际应用中,LongAdder可以用来实现各种原子性操作,例如计数器、分布式锁、统计数据等等。 LongAdder的使用非常简单,只需要创建一个LongAdder对象,然后使用其提供的方法来进行原子性操作。 例如,使用...

    Java Atomic类及线程同步新机制原理解析

    Atomic类提供了一种无锁的方式来实现线程安全的操作。Atomic类使用CAS(Compare-And-Swap)操作来实现原子操作。CAS操作是一种原子操作,用于比较并交换变量的值。 为什么使用Atomic类? 使用Atomic类可以避免使用...

    java多线程自增效率比较及原理解析

    - **LongAdder**: 性能最佳,这得益于其高效的分段累加机制。 #### 四、结论 通过上述分析和实验结果可以看出,在多线程环境下进行自增操作时,应优先考虑使用`LongAdder`。对于需要更高灵活性的场景,则可以选择`...

    LongAdder源码解读

    通过对代码的流程分析,一步一步拆解,将源码解读变得简单

    不同并发场景下LongAdder与AtomicLong如何选择.zip

    计算机技术、IT咨询、人工智能AI理论介绍,学习参考资料计算机技术、IT咨询、人工智能AI理论介绍,学习参考资料计算机技术、IT咨询、人工智能AI理论介绍,学习参考资料计算机技术、IT咨询、人工智能AI理论介绍,学习...

    Disruptor应用实例

    通过使用LongAdder等无锁算法,Disruptor避免了传统锁机制带来的性能瓶颈。此外,它采用Sequence机制,确保了生产者与消费者之间的顺序一致性,避免了数据竞争。 2. **环形缓冲区的工作流程** 生产者通过一个叫做...

    《阿里巴巴Java工作手册》学习笔记

    6. **LongAdder**:对于计数器操作,`LongAdder`是一种更高效的替代方案,尤其是在JDK 8及更高版本中。 通过上述总结,《阿里巴巴Java工作手册》不仅提供了实用的编程指南,还分享了许多高级技巧,对于希望提升自己...

    Java并发编程包中atomic的实现原理示例详解

    LongAdder的实现原理是通过CAS乐观锁保证原子性,通过自旋保证当次修改的最终修改成功。在竞争不激烈的时候,所有线程都是通过CAS对同一个变量(Base)进行修改,当竞争激烈的时候,会将根据当前线程哈希到对于Cell...

    jdk1.8.rar

    8. **并发改进**:包括Fork/Join框架的优化,更高效的并发数据结构,如LongAdder和DoubleAdder,以及改进的并发工具类。 9. **String和StringBuilder优化**:新增了一些方法,如`join()`和`repeat()`,使得字符串...

    guava,google项目名称、集合、缓存、原语支持、并发库、公共注释、字符串处理、i/o。美国石油学会.zip

    2. 缓存:Guava提供了一个高效的本地缓存实现,使得我们可以快速地存储和检索数据。开发者可以自定义缓存的大小、过期策略,以及在缓存项被移除时的回调函数,从而在内存管理上具有更大的灵活性。 3. 原语支持:...

    jdkapi1.8.zip

    9. **新的反射API**:JDK 1.8对反射API也做了改进,如`MethodHandle`和`MethodType`,提供了更高效且类型安全的反射机制。 10. **枚举的常量工厂方法**:枚举类可以定义静态工厂方法来创建其实例,增强了枚举的灵活...

    jdk8安装包,方便java开发者

    8. **新的数值类型`LongAdder`和`DoubleAdder`**:这些类提供了线程安全的计数器,相比于`synchronized`修饰的`AtomicLong`,它们在高并发环境下性能更优。 9. **并行流(Parallel Streams)**:Stream API支持并行...

    多线程并发技术

    例如,LongAdder是一个线程安全的累加器,它在高并发的情况下,相比于传统的AtomicInteger提供了更高的性能。这是因为LongAdder在内部使用了分段数组来分散热点,从而减少了高并发下的竞争程度。此外,...

    JDK8 中文帮助文档(jdk api 1.8 google.CHM)

    **JDK8中文帮助文档详解** JDK8(Java Development Kit 8)是Java编程语言的一个重要版本,它带来了许多重大的...通过深入理解和熟练运用这些知识点,开发者能够更好地利用JDK8的功能,编写出高效、简洁的Java代码。

    中文版jdk1.8的API.rar

    API(Application Programming Interface)是Java平台提供的一系列预先定义好的类和方法,程序员可以调用这些类和方法来实现特定功能,而无需从零开始编写所有代码。在JDK 1.8的API中,我们可以找到以下关键知识点:...

    jdk-8u181-windows-x64.rar

    4. **默认方法**:接口在Java 8中新增了默认方法,这使得接口可以提供默认实现,而不必强制实现类覆盖该方法。这对于扩展接口功能非常有用,同时也保持了向后兼容性。 5. **日期和时间API**:Java 8中引入了全新的...

    jdk api 1.8_google.CHM

    4. **新内建类型**:引入了`int`的窄化版本`byte`和`short`,以及新的数值类型`java.lang.LongAdder`,提供了高并发场景下的性能提升。 5. **类型推断增强**:编译器在编译时能更好地推断泛型的实际类型,简化了...

    官方java8规范-jls8.rar

    《Java语言规范,Java SE 8版》是Java开发者的重要参考文档,它详细...对于开发者来说,深入理解和掌握Java 8的新特性,将有助于编写出更高效、更优雅的代码。阅读《Java语言规范,Java SE 8版》是掌握这些知识的关键。

Global site tag (gtag.js) - Google Analytics