性能文章>实现一个比LongAdder更高性能的计数器有多难?>

实现一个比LongAdder更高性能的计数器有多难?原创

348419

强悍的LongAdder

LongAdder是jdk8引入的适用于统计场景的线程安全的计数器。

在此之前,实现一款线程安全的计数器要么加锁,要么使用AtomicLong,加锁性能必然很差,AtomicLong性能要好很多,但是在高并发、多线程下,也显得吃力。于是就有了LongAdder,LongAdder有两个重要的方法:addsum,add是线程安全的加,sum是返回结果,之所以叫sum是因为LongAdder通过分段的思想维护了一组变量,多线程并发更新时被散列到不同的变量上执行,减少冲突,所以最后获取返回值是将这些变量求和。通过这点也能看出sum获取的结果是不准确的,所以它只适用于统计场景,如果要获取精确的返回值,还是得用AtomicLong,性能和准确不可兼得。

通过JMH测试LongAdder、AtomicLong以及加锁的计数器的性能,感受一下LongAdder的强大。(如无特殊说明,本文后续JMH测试均以此为标准:fork1进程,4线程,预热2次,正式测量2次,测试机器4核,完整代码已上传github,文末有地址)

    private final AtomicLong atomicLong = new AtomicLong();
private final LongAdder longAdder = new LongAdder();
private long counter = 0;

public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(LongAdderTest.class.getSimpleName())
.forks(1)
.threads(4)
.warmupIterations(2)
.measurementIterations(2)
.mode(Mode.Throughput)
.syncIterations(false)
.build();

new Runner(opt).run();
}

@Benchmark
public void testAtomic() {
atomicLong.incrementAndGet();
}

@Benchmark
public void testLongAdder() {
longAdder.increment();
}

@Benchmark
public synchronized void testLockAdder() {
counter++;
}

运行后

Benchmark                          Mode  Cnt          Score   Error  Units
LongAdderTest.testAtomic thrpt 2 73520672.658 ops/s
LongAdderTest.testLockAdder thrpt 2 23456856.867 ops/s
LongAdderTest.testLongAdder thrpt 2 300013067.345 ops/s

可以看到LongAdder和另外两种实现完全不在一个量级上,性能及其恐怖。既然知道LongAdder的大致原理,那我们能不能实现一个MyLongAdder,保证写入线程安全的同时,性能比肩甚至超越LongAdder呢?

AtomicLong分段(V0)

性能优化中很多都是依靠LongAdder这种分段的方式,如ConcurrentHashMap就是采用分段锁,于是我们也实现一个V0版本的MyLongAdder

public class MyLongAdderV0 {

private final int coreSize;
private final AtomicLong[] counts;

public MyLongAdderV0(int coreSize) {
this.coreSize = coreSize;
this.counts = new AtomicLong[coreSize];
for (int i = 0; i < coreSize; i++) {
this.counts[i] = new AtomicLong();
}
}

public void increment() {
int index = (int) (Thread.currentThread().getId() % coreSize);
counts[index].incrementAndGet();
}
}

使用一个AtomicLong数组,线程执行时,按线程id散列开,coreSize这里期望是cpu核数,和LongAdder、AtomicLong对比一下看看(测试代码省略,后同)

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testAtomic thrpt 2 73391661.579 ops/s
LongAdderTest.testLongAdder thrpt 2 309539056.885 ops/s
LongAdderTest.testMyLongAdderV0 thrpt 2 83737867.380 ops/s

emmm,V0性能仅仅比AtomicLong好一点点,跟LongAdder还是不在一个量级上,难道是数组不够大?将coreSize作为参数,测试一下 4, 8, 16, 32的情况,我测试了好几次,每次结果都不一样但又差不多在一个量级(偶尔会上亿),无法总结结果与coreSize的关系,这里给出其中一组

Benchmark                        (coreSize)   Mode  Cnt          Score   Error  Units
LongAdderTest.testMyLongAdderV0 4 thrpt 2 62328997.667 ops/s
LongAdderTest.testMyLongAdderV0 8 thrpt 2 124725716.902 ops/s
LongAdderTest.testMyLongAdderV0 16 thrpt 2 84718415.566 ops/s
LongAdderTest.testMyLongAdderV0 32 thrpt 2 85321816.442 ops/s

猜想是因为依赖了线程的id,分散的不够均匀导致,而且还有一个有意思的情况,有时候V0居然比AtomicLong的性能还低。

取模优化(V1)

注意到V0里面有一个取模的操作,这个操作可能比较耗时,可能会导致V0的性能甚至不如单个AtomicLong,可以通过移位操作来代替,但代替的前提是coreSize必须为2的n次方,如2,4,8,16(我们假定后续coreSize只取2的n次方),V1版本的代码如下:

public class MyLongAdderV1 {

private final int coreSize;
private final AtomicLong[] counts;

public MyLongAdderV1(int coreSize) {
this.coreSize = coreSize;
this.counts = new AtomicLong[coreSize];
for (int i = 0; i < coreSize; i++) {
this.counts[i] = new AtomicLong();
}
}

public void increment() {
int index = (int) (Thread.currentThread().getId() & (coreSize - 1));
counts[index].incrementAndGet();
}

}

测试一下性能

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 312683635.190 ops/s
LongAdderTest.testMyLongAdderV0 thrpt 2 60641758.648 ops/s
LongAdderTest.testMyLongAdderV1 thrpt 2 100887869.829 ops/s

性能稍微好了一点,但是跟LongAdder比还是差了一大截

消除伪共享(V2)

在cpu面前内存太慢了,所以cpu有**缓存 L3,L2,L1。L1最接近cpu,速度也最快,cpu查找的顺序是先L1,再L2,再L3,最后取不到会去内存取。通常来说每个缓存由很多缓存行组成,缓存行通常是64个字节,java的long是8字节,因此一个缓存行可以缓存8个long变量。如果多个核的线程在操作同一个缓存行中的不同变量数据,那么就会出现频繁的缓存失效,即使在代码层面看这两个线程操作的数据之间完全没有关系。这种不合理的资源竞争情况学名伪共享(False Sharing),会严重影响机器的并发执行效率。

在V1中,AtomicLong中有一个value,每次incrementAndGet会改变这个value,同时AtomicLong是一个数组,数组的内存地址也是连续的,这样就会导致相邻的AtomicLong的value缓存失效,其他线程读取这个value就会变得很慢。优化的方法就是填充AtomicLong,让每个AtomicLong的value相互隔离,不要相互影响。

通常填充缓存行有如下几种方式:

  • (1)java8可以在类属性上使用 @sun.misc.Contended,jvm参数需要指定 -XX:-RestrictContended
  • (2)使用继承的方式在类的属性前后插入变量实现,这里举一个通过继承来实现的,如果不用继承,这些填充的无用变量会被编译器优化掉,当然也可以通过数组来构造填充,这里就不多说。
abstract class RingBufferPad {
protected long p1, p2, p3, p4, p5, p6, p7;
}

abstract class RingBufferFields<E> extends RingBufferPad {
protected long value;
}

public final class RingBuffer<E> extends RingBufferFields<E> {
protected long p1, p2, p3, p4, p5, p6, p7;
}

我们直接用java8的@sun.misc.Contended来对V1进行优化

public class MyLongAdderV2 {

private static class AtomicLongWrap {
@Contended
private final AtomicLong value = new AtomicLong();
}

private final int coreSize;
private final AtomicLongWrap[] counts;

public MyLongAdderV2(int coreSize) {
this.coreSize = coreSize;
this.counts = new AtomicLongWrap[coreSize];
for (int i = 0; i < coreSize; i++) {
this.counts[i] = new AtomicLongWrap();
}
}

public void increment() {
int index = (int) (Thread.currentThread().getId() & (coreSize - 1));
counts[index].value.incrementAndGet();
}

}

执行后神奇的情况出现了

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 272733686.330 ops/s
LongAdderTest.testMyLongAdderV2 thrpt 2 307754425.667 ops/s

居然V2版本比LongAdder还快!但这是真的吗?为此,我多测试了几组,分别在线程数为8时

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 260909722.754 ops/s
LongAdderTest.testMyLongAdderV2 thrpt 2 215785206.276 ops/s

线程数为16时:

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 307269737.067 ops/s
LongAdderTest.testMyLongAdderV2 thrpt 2 185774540.302 ops/s

发现随着线程数的增加,V2的性能越来越低,但LongAdder纹丝不动,不得不佩服写jdk的大佬。

改进hash算法

V0到V2版本均使用了线程id作为hash值来散列到不同的槽点,线程id生成后不会改变,这样就会导致每次执行的测试可能结果都不太一样,如果比较聚焦,性能必然会很差,当线程数增多后必然会造成更多的冲突,有没有更好的hash算法?

  • 尝试hashCode

java的每个对象都有一个hashCode,我们使用线程对象的hashCode来散列试试,版本V3关键改动如下

public void increment() {
int index = Thread.currentThread().hashCode() & (coreSize - 1);
counts[index].incrementAndGet();
}

结果如下

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 277084413.669 ops/s
LongAdderTest.testMyLongAdderV3 thrpt 2 103351246.650 ops/s

性能似乎不尽如人意。

  • 尝试随机数

当然使用Random当然不行,用性能更好的ThreadLocalRandom,V4版本关键改动如下

  public void increment() {
counts[ThreadLocalRandom.current().nextInt(coreSize)].value.incrementAndGet();
}

结果如下

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 292807355.101 ops/s
LongAdderTest.testMyLongAdderV4 thrpt 2 95200307.226 ops/s

性能也上不去,猜想是因为生成随机数比较耗时。

  • 冲突时重新计算hash

为了优化V4版本,参考了LongAdder,算是一个黑科技,生成一个随机数存在Thread对象中,可以看一下Thread类,刚好有这个变量

/** Probe hash value; nonzero if threadLocalRandomSeed initialized */
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;

但是这个变量是不对外开放,只能通过反射(性能太差)或者UNSAFE来取,它在 ThreadLocalRandomSeed 中被初始化,发生冲突时重新生成并修改它(生成的方法可以参考ThreadLocalRandomSeed),也是通过UNSAFE可以搞定。既然要在冲突时重新hash,那必须能检测出冲突,AtomicLong就不能用incrementAndGet了,使用AtomicLong的compareAndSet方法,返回false时代表有冲突,冲突时重新hash,并用incrementAndGet兜底,保证一定能成功。如此一来,既可以均匀地散列开,也能保证随机数生成的效率。V5版本代码如下

public class MyLongAdderV5 {

private static sun.misc.Unsafe UNSAFE = null;
private static final long PROBE;
static {

try {
// 反射获取unsafe
Field f = Unsafe.class.getDeclaredField("theUnsafe");
f.setAccessible(true);
UNSAFE = (Unsafe) f.get(null);
} catch (Exception e) {

}

try {
Class<?> tk = Thread.class;
PROBE = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomProbe"));
} catch (Exception e) {
throw new Error(e);
}
}

static final int getProbe() {
// 获取thread的threadLocalRandomProbe属性值
return UNSAFE.getInt(Thread.currentThread(), PROBE);
}

static final int advanceProbe(int probe) {
// 重新生成随机数并写入thread对象
probe ^= probe << 13; // xorshift
probe ^= probe >>> 17;
probe ^= probe << 5;
UNSAFE.putInt(Thread.currentThread(), PROBE, probe);
return probe;
}

private static class AtomicLongWrap {
@Contended
private final AtomicLong value = new AtomicLong();
}

private final int coreSize;
private final AtomicLongWrap[] counts;

public MyLongAdderV5(int coreSize) {
this.coreSize = coreSize;
this.counts = new AtomicLongWrap[coreSize];
for (int i = 0; i < coreSize; i++) {
this.counts[i] = new AtomicLongWrap();
}
}

public void increment() {

int h = getProbe();

int index = getProbe() & (coreSize - 1);
long r;
if (!counts[index].value.compareAndSet(r = counts[index].value.get(), r + 1)) {
if (h == 0) {
// 初始化随机数
ThreadLocalRandom.current();
h = getProbe();
}
// 冲突后重新生成随机数
advanceProbe(h);
// 用getAndIncrement来兜底
counts[index].value.getAndIncrement();
}
}

}

结果如下

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 274131797.300 ops/s
LongAdderTest.testMyLongAdderV5 thrpt 2 298402832.456 ops/s

效果还可以,试试8线程:

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 324982482.774 ops/s
LongAdderTest.testMyLongAdderV5 thrpt 2 290476796.289 ops/s

16线程:

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 291180444.998 ops/s
LongAdderTest.testMyLongAdderV5 thrpt 2 282745610.470 ops/s

32线程:

Benchmark                         Mode  Cnt          Score   Error  Units
LongAdderTest.testLongAdder thrpt 2 294237473.396 ops/s
LongAdderTest.testMyLongAdderV5 thrpt 2 301187346.873 ops/s

果然这个方法很牛皮,无论在多少个线程下都能稳如🐶。

总结

实现一款超越LongAdder性能的多线程计数器非常难,折腾了两天也只是达到和LongAdder相当的性能,其中对性能影响最大的几个改动点是

  • 分段:基础优化,一般人都能想到
  • 取模优化:也比较基础
  • 消除伪共享:这个优化提升很大
  • hash算法:这条保证了稳定性,无论多少线程都是最高吞吐量

其中前三条比较常规,第四条可以算得上是黑科技



请先登录,再评论

hash算法这个黑科技感觉有适用条件

5月前

为你推荐

字符串字面量长度是有限制的
前言 偶然在一次单元测试中写了一个非常长的字符串字面量。 正文 在一次单元测试中,我写了一个很长的字符串字面量,大概10万个字符左右,编译时,编译器给出了异常告警 `java: constant
多次字符串相加一定要用StringBuilder而不用-吗?
今天在写一个读取Java class File并进行分析的Demo时,偶然发现了下面这个场景(基于oracle jdk 1.8.0_144): ``` package test; public c
如何通过反射获得方法的真实参数名(以及扩展研究)
前段时间,在做一个小的工程时,遇到了需要通过反射获得方法真实参数名的场景,在这里我遇到了一些小小的问题,后来在部门老大的指导下,我解决了这个问题。通过解决这个问题,附带着我了解到了很多新的知识,我觉得
高吞吐、低延迟 Java 应用的 GC 优化实践
本篇原文作者是 LinkedIn 的 Swapnil Ghike,这篇文章讲述了 LinkedIn 的 Feed 产品的 GC 优化过程,虽然文章写作于 April 8, 2014,但其中的很多内容和
「每日五分钟,玩转 JVM」:久识你名,初居我心
聊聊 JVMJVM,一个熟悉又陌生的名词,从认识Java的第一天起,我们就会听到这个名字,在参加工作的前一两年,面试的时候还会经常被问到JDK,JRE,JVM这三者的区别。JVM可以说和我们是老朋友了
据说99.99%的人都会答错的类加载的问题
概述首先还是把问题抛给大家,这个问题也是我厂同学在做一个性能分析产品的时候碰到的一个问题。 同一个类加载器对象是否可以加载同一个类文件多次并且得到多个Class对象而都可以被java层使用吗请仔细注意
Java多线程——并发测试
编写并发程序时候,可以采取和串行程序相同的编程方式。唯一的难点在于,并发程序存在不确定性,这种不确定性会令程序出错的地方远比串行程序多,出现的方式也没有固定规则。那么如何在测试中,尽可能的暴露出这些问
Java多线程知识小抄集(一)
本文主要整理笔者遇到的Java多线程的相关知识点,适合速记,故命名为“小抄集”。本文没有特别重点,每一项针对一个多线程知识做一个概要性总结,也有一些会带一点例子,习题方便理解和记忆。 1.interr