基于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

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

完全lock cmpxchg完成（成功或失败）意味着该核心上的缓存行现在处于修改（或者可能只是独占？）状态，因此现在是重试的最佳时机。

无锁原子的实际用例通常不会出现非常激烈的竞争，否则您通常应该使用操作系统辅助的睡眠/唤醒的回退。

（但是如果存在争用，则 ed 指令会进行硬件仲裁；在高度争用的情况下，我不知道核心是否有可能在再次丢失缓存行之前lock执行第二条ed 指令。但希望是的。 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如果比较失败，则更新其第一个参数，因此您不需要在循环内进行另一个加载。

#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 重试中时，这才有意义。

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