Striped64 学习
Striped64 学习
很长一段时间,不知道Striped64这个类的存在,当然,还是由于对并发包不了解的缘故。在大概了解了一下之后,才知道,原来这是一个并发计数组件,这个类很有意思,在这里学习总结一下。
简单介绍
Striped64是在java8中新增的用于支持累加器的并发组件(和LongAdder、DoubleAdder一起增加的一个抽象内部类),它支持在并发环境下计数,其设计思想是避免线程激烈竞争时引起的开销和异常,通过分散竞争的方式(允许不超过CPU核心数个线程同时执行)实现最大效率。
在Striped64内部维护了3个重要操作变量,分别是:cells(Cell类型的数组)、base(基础计数器)、cellsBusy(Cell数组状态值)。Cell对象内部维护了一个计数值value,用来记录线程局部计数值。
计数核心过程为:
- 根据当前线程来计算一个哈希值,根据算法(hashCode & (length - 1))取模定位到该线程被分散到的Cell数组中的位置;
- 如果Cell数组还没有被创建,那么就去获取cellBusy这个状态值,如果获取成功,则初始化Cell数组,初始容量为2,初始化完成之后将x(计数增值)包装到一个Cell,哈希计算之后分散到相应的index上。如果获取cellBusy失败,那么会试图将x(计数增值)累计到base上,更新失败会重试(自旋)直到成功。
- 如果Cell数组已经被初始化过了,那么就根据线程的哈希值分散到一个Cell数组元素上,获取这个位置上的Cell并且赋值给一个变量,如果该值为null,说明该位置还没有被初始化,那么在竞争cellBusy变量成功后初始化,如果不为null,说明该位置上的值是当前线程的,更新该计数值。
- 如果Cell数组的大小已经最大了(大于等于CPU的数量),那么就需要重新计算哈希,来重新分散当前线程到另外一个Cell位置上再走一遍该方法的逻辑,否则就需要对Cell数组进行扩容(2倍大小于原数组),然后将原来的计数内容迁移过去。由于Cell里面保存的是计数值,所以扩容后没有必要做其他处理,直接根据index将旧的Cell数组内容复制到新的Cell数组中。
- 最后将base值和cells中各个Cell的value值进行累加,即为最终计数结果。
源码分析
核心变量
1 | /** CPU核心数,用来控制Cells数组大小 */ |
内部类Cell
关于注解@sun.misc.Contended:来避免伪共享。原理是在使用此注解的对象或字段的前后各增加128字节大小的padding,使用2倍于大多数硬件缓存行的大小来避免相邻扇区预取导致的伪共享冲突。
什么是伪共享:当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行(缓存行是2的整数幂个连续字节,一般为32-256个字节,最常见的缓存行大小是64个字节),就会无意中影响彼此的性能。
1 | // 该类是基于AtomicLong的变体,仅支持原始访问和CAS |
xorshift 伪随机数生成函数
1 | // 同一个线程根据上一次的hashcode通过xorshift函数再次生成随机数后, |
longAccumulate方法
1 | // x 元素 |
doubleAccumulate方法是从longAccumulate方法拷贝的,除了类型部分,代码逻辑一致,拷贝的目的是为了减少由于复用引起的类型转换开销。
java8中,LongAdder和DoubleAdder类都实现了Striped64类,且分别使用到了longAccumulate方法和doubleAccumulate方法。在使用上,由于LongAdder用到了Striped64类似分散竞争的思想,因此在效率上要比AtomicLong类更高。
以下为LongAdder中,主要方法的实现,DoubleAdder中的实现类似。
1 | public void add(long x) { |
Striped64的设计思路在java8的ConcurrentHashMap中size的大小更新也有体现,使用类似的方式实现。
- 本文链接: https://acehjm.github.io/2020/01/08/Striped64学习/
- 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!