基于 compare_exchange 的循环是否受益于暂停？

Question

在基于 CAS 的循环中，例如下面的循环，在 x86 上使用暂停是否有益？

void atomicLeftShift(atomic<int>& var, int shiftBy)
{
    While(true) {
        int oldVal = var;
        int newVal = oldVal << shiftBy;
         if(var.compare_exchange_weak(oldVal, newVal));
             break;
        else
            _mm_pause();
    }
}

Answer 1

不，我不这么认为。这不是旋转等待。 它不是在等待另一个线程存储 0 或其他东西。在 lock cmpxchg 失败后立即重试确实有意义，而不是休眠 ~100 个周期（在 Skylake 和更高版本上）或~5 个周期（在早期的 Intel CPU 上）。

对于 lock cmpxchg 完全完成（成功或失败）意味着缓存行现在在 this 核心上处于已修改（或者可能只是独占？）状态，所以现在是再试一次的最佳时机。

无锁原子的真实用例通常不会竞争激烈，否则你通常应该使用回退到OS辅助sleep/wake.

（但如果存在争用，则会对 locked 指令进行硬件仲裁；在竞争激烈的情况下，我不知道内核是否有可能执行第二个 lock在再次丢失缓存行之前编辑指令。但希望是。）

lock cmpxchg 不会虚假地失败，所以实际的活锁是不可能的：至少有一个核心会通过让其 CAS 在这样的算法中取得成功来取得进展，对于每个核心都有一个回合。在 LL/SC 架构上，compare_exchange_weak 可能会虚假地失败，因此到非 x86 的可移植性可能需要关心活锁，具体取决于实现细节，但我认为即使如此也不太可能。（当然 _mm_pause 仅适用于 x86。）

使用 pause 的另一个原因是在离开自旋等待循环时避免内存顺序错误推测，该自旋等待循环以只读方式旋转以等待看到锁已解锁，然后再尝试以原子方式声明它。（这比在 xchg 或 lock cmpxchg 上旋转并让所有等待的线程都在高速缓存行上进行重击要好。）

但这在这里又不是问题，因为重试循环已经包含 lock cmpxchg，这是一个完整的障碍以及原子 RMW，所以我认为这避免了内存顺序错误推测。

特别是如果您有效/正确地编写循环以在重试时使用 cmpxchg 失败的加载结果，从循环 中删除 var 的纯加载。

这是从 CAS 原语构造任意原子操作的规范方法。 compare_exchange_weak 如果比较失败则更新它的第一个 arg，因此您不需要在循环内进行其他加载。

#include <atomic>

int atomicLeftShift(std::atomic<int>& var, int shiftBy)
{
    int expected = var.load(std::memory_order_relaxed);
    int desired;
    do {
        desired = expected << shiftBy;
    } while( !var.compare_exchange_weak(expected, desired) );  // seq_cst
    return desired;
}

在 Godbolt 编译器资源管理器上用 clang7.0 -O3 for x86-64 编译到这个 asm：

atomicLeftShift(std::atomic<int>&, int):      
    mov     ecx, esi
    mov     eax, dword ptr [rdi]        # pure load outside the loop

.LBB0_1:                              # do {
    mov     edx, eax
    shl     edx, cl                     # desired = expected << count
    lock            cmpxchg dword ptr [rdi], edx   # eax = implicit expected, updated on failure
    jne     .LBB0_1                   # } while(!CAS)
    mov     eax, edx                  # return value
    ret

重试循环中唯一的内存访问是 lock cmpxchg，它不会受到内存顺序错误推测的影响。出于这个原因，不需要 pause。

简单的退避延迟也不需要 pause，除非您有很多争用并且想让一个线程连续对同一个共享变量执行多项操作以增加吞吐量。即在 cmpxchg 失败的罕见情况下让其他线程退出。

这个只有才有意义，如果一个线程在同一个变量上连续执行多个原子操作是正常的（或者在同一个缓存行中，如果你有假 -共享问题），而不是将更多操作放入一次 CAS 重试中。

这在实际代码中可能很少见，但在合成微基准测试中很常见，在该基准测试中，您让多个线程反复敲打共享变量，中间没有其他工作。

基于 compare_exchange 的循环是否受益于暂停？

Does compare_exchange based loop benefit from pause?

c++

x86

atomic

compare-and-swap

c++11