CAS 与同步性能

CAS vs synchronized performance

我有这个问题已经有一段时间了,试图阅读大量资源并了解正在发生的事情 - 但我仍然未能很好地理解为什么事情会这样。

简单地说,我正在尝试测试 CASsynchronized 在竞争而非环境中的表现。我已经进行了这个 JMH 测试:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@State(Scope.Benchmark)
public class SandBox {

    Object lock = new Object();

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder().include(SandBox.class.getSimpleName())
                .jvmArgs("-ea", "-Xms10g", "-Xmx10g")
                .shouldFailOnError(true)
                .build();
        new Runner(opt).run();
    }

    @State(Scope.Thread)
    public static class Holder {

        private long number;

        private AtomicLong atomicLong;

        @Setup
        public void setUp() {
            number = ThreadLocalRandom.current().nextLong();
            atomicLong = new AtomicLong(number);
        }
    }

    @Fork(1)
    @Benchmark
    public long sync(Holder holder) {
        long n = holder.number;
        synchronized (lock) {
            n = n * 123;
        }

        return n;
    }

    @Fork(1)
    @Benchmark
    public AtomicLong cas(Holder holder) {
        AtomicLong al = holder.atomicLong;
        al.updateAndGet(x -> x * 123);
        return al;
    }

    private Object anotherLock = new Object();

    private long anotherNumber = ThreadLocalRandom.current().nextLong();

    private AtomicLong anotherAl = new AtomicLong(anotherNumber);

    @Fork(1)
    @Benchmark
    public long syncShared() {
        synchronized (anotherLock) {
            anotherNumber = anotherNumber * 123;
        }

        return anotherNumber;
    }

    @Fork(1)
    @Benchmark
    public AtomicLong casShared() {
        anotherAl.updateAndGet(x -> x * 123);
        return anotherAl;
    }

    @Fork(value = 1, jvmArgsAppend = "-XX:-UseBiasedLocking")
    @Benchmark
    public long syncSharedNonBiased() {
        synchronized (anotherLock) {
            anotherNumber = anotherNumber * 123;
        }

        return anotherNumber;
    }

}

结果:

Benchmark                                           Mode  Cnt     Score      Error  Units
spinLockVsSynchronized.SandBox.cas                  avgt    5   212.922 ±   18.011  ns/op
spinLockVsSynchronized.SandBox.casShared            avgt    5  4106.764 ± 1233.108  ns/op
spinLockVsSynchronized.SandBox.sync                 avgt    5  2869.664 ±  231.482  ns/op
spinLockVsSynchronized.SandBox.syncShared           avgt    5  2414.177 ±   85.022  ns/op
spinLockVsSynchronized.SandBox.syncSharedNonBiased  avgt    5  2696.102 ±  279.734  ns/op

在非共享情况下 CAS到目前为止 更快,这是我所期望的。但是在共享的情况下,事情是相反的——这是我无法理解的。我不认为这与偏向锁定有关,因为这会在线程持有锁 5 秒(AFAIK)后发生,而这不会发生,测试只是证明。

老实说,我希望只是我的测试有误,有 jmh 专业知识的人会出现并指出我这里的错误设置。

首先,您正在编写的代码是 java,它将创建 java 字节代码,该字节代码转换为不同指令集(Arm vs powerpc vs X86 ...)上的不同原子操作在不同供应商的实现中甚至在同一供应商的架构(例如 intel core 2 duo 和 skylake)之间可能表现不同。所以很难回答你的问题!

This paper 声明对于测试的 X86 架构,任何原子操作的一次执行都执行类似(CAS、Fetch 和添加、交换之间的差异非常小),而 CAS 可能会失败并且需要执行多次。但是,如果是一个线程,它永远不会失败。

This Whosebug post 状态:

Each object has a monitor associated with it. The thread that executes monitorenter gains ownership of the monitor associated with objectref. If another thread already owns the monitor associated with objectref, the current thread waits until the object is unlocked, then tries again to gain ownership. If the current thread already owns the monitor associated with objectref, it increments a counter in the monitor indicating the number of times this thread has entered the monitor. If the monitor associated with objectref is not owned by any thread, the current thread becomes the owner of the monitor, setting the entry count of this monitor to 1.

让我们看看在 CAS 情况下的必要操作:

public final int updateAndGet(IntUnaryOperator updateFunction) {
    int prev, next;
    do {
        prev = get();
        next = updateFunction.applyAsInt(prev);
    } while (!compareAndSet(prev, next));
    return next;
}

取x,乘x,cas on x,检查cas是否成功

现在这在非满足情况下是有效的,因为需要的操作数量最少。但是如果缓存行被争用,它就不是很有效,因为所有线程都在积极旋转,而大多数线程都失败了。此外,我记得使用原子操作在竞争的高速缓存线上旋转非常昂贵。

现在同步中的重要部分是:

If another thread already owns the monitor associated with objectref, the current thread waits until the object is unlocked

这取决于这个等待是如何实现的。

synchronized 方法可以在获取监视器失败后让线程随机休眠一段时间,而且可以通过简单的读取来代替使用原子操作来检查监视器是否空闲(这是更快,但我找不到 link 来证明这一点)。

我敢打赌,synchronized 中的等待是以一种聪明的方式实现的,并针对与上述方法之一或类似方法发生争用的情况进行了优化,因此在争用的情况下它会更快。

权衡是在非竞争情况下速度较慢。

我还是承认我没有证据

主要的误解是假设您正在比较“CASsynchronized”。鉴于复杂的 JVM 如何实现 synchronized,您正在比较使用 AtomicLong 的基于 CAS 的算法的性能与用于实现 CAS 的基于算法的性能 synchronized.

类似于Lock,对象监视器的内部信息基本上包括一个int状态,告诉它是否已被拥有以及嵌套的频率,对当前所有者线程的引用和等待能够获取它的线程队列。昂贵的方面是等待队列。将线程放入队列,将其从线程调度中移除,并最终在当前所有者释放监视器时将其唤醒,这些操作可能会花费大量时间。

但是,在没有竞争的情况下,当然不涉及等待队列。获取监视器由一个 CAS 组成,用于将状态从“无主”(通常为零)更改为“拥有,获得一次”(猜测典型值)。如果成功,线程可以继续执行关键操作,然后是释放,这意味着只需写入具有必要内存可见性的“无主”状态,并唤醒另一个被阻塞的线程(如果有的话)。

由于等待队列是更昂贵的东西,即使在竞争情况下,实现通常也会尝试通过执行一些旋转来避免它,在回退到排队线程之前进行多次重复 CAS 尝试.如果所有者的关键操作像单个乘法一样简单,则监视器很可能已经在纺纱阶段被释放。请注意,synchronized 是“不公平的”,允许旋转线程立即继续,即使已经有排队的线程等待更长时间。

如果比较 synchronized(lock){ n = n * 123; } 在不涉及排队时与 al.updateAndGet(x -> x * 123); 执行的基本操作,您会发现它们大致相同。主要区别在于 AtomicLong 方法会在争用时重复乘法,而对于 synchronized 方法,如果在旋转期间没有取得任何进展,则存在被放入队列的风险。

但是 synchronized 允许 lock coarsening for code repeatedly synchronizing on the same object, which might be relevant for a benchmark loop calling the syncShared method. Unless there’s also a way to fuse multiple CAS updates of an AtomicLong, this can give synchronized a dramatic advantage. (See also this article 涵盖上面讨论的几个方面)

请注意,由于 synchronized 的“不公平”性质,创建比 CPU 内核多得多的线程不一定是问题。在最好的情况下,“线程数减去核心数”线程最终进入队列,永远不会醒来,而其余线程在旋转阶段成功,每个核心一个线程。但同样,CPU 核心上的非 运行 线程不能降低 AtomicLong 更新的性能,因为它们既不能使其他线程的当前值无效,也不能使失败 CAS 尝试。

在任何一种情况下,当 CAS 对非共享对象的成员变量执行时或对非共享对象执行 synchronized 时,JVM 可能会检测到操作的局部性质并省略大部分的相关费用。但这可能取决于几个微妙的环境方面。


底线是原子更新和 synchronized 块之间没有简单的决定。随着更昂贵的操作,事情变得更加有趣,这可能会增加线程在 synchronized 的竞争情况下排队的可能性,这可能使在原子更新的竞争情况下必须重复操作变得可以接受.

请注意,CAS 可以为您提供比同步块更细粒度的排序(非)保证,尤其是 java-9 varhandles 提供与 C++ 一致的排序选项11内存模型。

如果您想做的只是从多个线程中保留一些统计数据,那么具有最宽松内存排序的读取-计算-更新循环 (plain read; plain and weak CAS) 可能在弱排序平台上表现更好,因为它不需要任何障碍,如果在 LL/SC 之上实现,cas 将不必进行浪费的内部循环。此外,它还将为 JIT 提供更多自由来重新排序围绕这些原子的指令。 compareAndExchange 可以消除循环重复的额外读取。

另一个复杂因素是您衡量绩效的方式。所有的实现都应该有进度保证,即即使在竞争中至少有一个可以一次完成。所以原则上你可能会在多个线程上浪费 CPU 周期试图同时更新你的变量,但在第 99 个百分位延迟的测量上仍然更好,因为原子操作不会诉诸于取消调度线程,并且在最坏的情况下更糟延迟,因为它们不公平。因此,仅测量平均值可能无法说明全部情况。

您应该阅读、重新阅读并接受@Holger 的出色回答,因为它提供的见解比来自一个开发人员工作站的一组基准数据更有价值。

我调整了您的基准测试,使它们更加统一,但如果您阅读@Holger 的回答,您就会明白为什么这不是一个非常有用的测试。我将包括我的更改和我的结果只是为了展示结果如何从一台机器(或一个 JRE 版本)到另一台机器。

首先,我的基准测试版本:

@State(Scope.Benchmark)
public class SandBox {
    public static void main(String[] args) throws RunnerException {
        new Runner(
            new OptionsBuilder().include(SandBox.class.getSimpleName())
                                .shouldFailOnError(true)
                                .mode(Mode.AverageTime)
                                .timeUnit(TimeUnit.NANOSECONDS)
                                .warmupIterations(5)
                                .warmupTime(TimeValue.seconds(5))
                                .measurementIterations(5)
                                .measurementTime(TimeValue.seconds(5))
                                .threads(-1)
                                .build()
        ).run();
    }

    private long number = 0xCAFEBABECAFED00DL;
    private final Object lock = new Object();
    private final AtomicLong atomicNumber = new AtomicLong(number);

    @Setup(Level.Iteration)
    public void setUp() {
        number = 0xCAFEBABECAFED00DL;
        atomicNumber.set(number);
    }

    @Fork(1)
    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public long casShared() {
        return atomicNumber.updateAndGet(x -> x * 123L);
    }

    @Fork(1)
    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public long syncShared() {
        synchronized (lock) {
            return number *= 123L;
        }
    }

    @Fork(value = 1, jvmArgsAppend = "-XX:-UseBiasedLocking")
    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public long syncSharedNonBiased() {
        synchronized (lock) {
            return number *= 123L;
        }
    }
}

然后是我的第一批结果:

# VM version: JDK 1.8.0_60, VM 25.60-b23

Benchmark                    Mode  Cnt     Score     Error  Units
SandBox.casShared            avgt    5   976.215 ± 167.865  ns/op
SandBox.syncShared           avgt    5  1820.554 ±  91.883  ns/op
SandBox.syncSharedNonBiased  avgt    5  1996.305 ± 124.681  ns/op

回想一下,您看到 synchronized 在激烈的竞争中脱颖而出。在我的工作站上,原子版本表现更好。如果您使用我的基准测试版本,您会看到什么结果?如果它们有很大的不同,我一点也不会感到惊讶。

这是 运行 几个月前 Java 9 EA 版本的另一组:

# VM version: JDK 9-ea, VM 9-ea+170

Benchmark                    Mode  Cnt     Score     Error  Units
SandBox.casShared            avgt    5   979.615 ± 135.495  ns/op
SandBox.syncShared           avgt    5  1426.042 ±  52.971  ns/op
SandBox.syncSharedNonBiased  avgt    5  1649.868 ±  48.410  ns/op

这里的差别不大。在主要 JRE 版本之间看到差异并不少见,但谁能说您在次要版本中也不会看到它们?

一天结束时,结果很接近。很接近。 synchronized 的性能自早期 Java 版本以来已经取得了长足的进步。如果您不编写 HFT 算法或其他难以置信 延迟敏感的东西,您应该更喜欢最容易证明正确 的解决方案。通常比无锁算法和数据结构更容易推理 synchronized 。如果您无法证明 您的应用程序 存在可衡量的差异,那么您应该使用 synchronized