cmpxchg 是否在失败时写入目标缓存行？如果不是，自旋锁是否比 xchg 更好？

Question

我假设简单的自旋锁不会进入 OS 等待这个问题的目的。

我看到简单的自旋锁通常使用 lock xchg 或 lock bts 而不是 lock cmpxchg 来实现。

但是，如果期望不匹配，cmpxchg 不会避免写入值吗？那么 cmpxchg 的失败尝试不是更便宜吗？

或者cmpxchg写入数据并使其他核心的缓存行无效，即使在失败时？

这个问题和类似，但是是针对cmpxchg的，不是笼统的。

Answer 1

我做了一些测试。虽然非常综合，但在锁下做了很少的事情，并测量了竞争激烈的场景的吞吐量。

到目前为止，没有观察到 lock bts xchg 或 lock cmpxchg 之间差异的稳定影响。

然而其他的东西有一些影响：

内部 load 循环绝对有帮助，无论有无 pause
循环中的一个 pause 很有帮助，无论是否有负载循环
加载循环比暂停更有帮助
通过应用 Intel® 64 and IA-32 Architectures Optimization Reference Manual（见下文）
从负载而不是 RMW/CAS 开始具有有争议的效果：它对没有 pause 的测试很有帮助，但会降低 pause

Intel® 64 and IA-32 Architectures Optimization Reference Manual 建议使用 pause.

示例 2-4。竞争锁增加 Back-off 示例 显示基线版本：

/*******************/
/*Baseline Version */
/*******************/
// atomic {if (lock == free) then change lock state to busy}
while (cmpxchg(lock, free, busy) == fail)
{
 while (lock == busy)
 {
 __asm__ ("pause");
 }
}

和改进版本：

/*******************/
/*Improved Version */
/*******************/
int mask = 1;
int const max = 64; //MAX_BACKOFF
while (cmpxchg(lock, free, busy) == fail)
{
 while (lock == busy)
 {
   for (int i=mask; i; --i){
     __asm__ ("pause");
   }
   mask = mask < max ? mask<<1 : max;
 }
}

Windows SRWLOCK 也可能是一个很好的例子。它使用加载循环和 pause。它以互锁操作开始 lock bts 获取独占，lock cmpxchg 获取共享。即使 TryAcquireSRWLockExclusive 也只做 lock bts:

RtlTryAcquireSRWLockExclusive:
00007FFA86D71370  lock bts    qword ptr [rcx],0  
00007FFA86D71376  setae       al  
00007FFA86D71379  ret

然而，它并没有在等待版本中实现指数增长 pause。它用一个pause做一些少量的加载，然后去OS等待。

Answer 2

在大多数或所有当前的 Intel x86 处理器上，lock cmpxchg 到内存类型为 WB 且完全包含在单个 L1D 缓存行中的位置执行如下：

向 L1D 发出 lock-read 请求，使目标行处于 locked-exclusive 缓存一致性状态，并将请求的字节作为输入提供给其中一个执行端口以执行比较. （从 P6 开始支持缓存锁定。）处于锁定状态的行不能因任何原因失效或被驱逐。
执行相等性比较。
无论结果如何，向 L1D 发出一个 unlock-write 请求，这会将缓存行的状态更改为已修改并解锁该行，从而允许其他访问或一致性请求替换或使缓存行无效行。

可以使用某些性能事件或 latency-based 测量凭经验观察第一步和最后一步。一种方法是分配大量原子变量，然后在该数组的循环中执行 lock cmpxchg。 lock-read 请求类型是 RFO 请求类型之一。因此，在大多数微体系结构上可靠的 L2_TRANS.RFO 事件（或等效事件）可用于测量 L2 的 lock-read 的数量。（L2_TRANS.RFO 计算需求 RFO，因此最好关闭硬件预取器以避免 L2 中不必要的命中。这也适用于 L2_RQSTS.RFO_*。）

还有L2_TRANS.L1D_WB、L2_TRANS.L2_WB等衡量回写次数的事件。不幸的是，许多这些事件和许多微架构要么计数不足，要么计数准确，但不一定 all/only 脏缓存行写回。所以他们更难推理，而且通常不可靠。

更好的方法是在特定物理核心上的数组的一部分上执行 lock cmpxchg，然后将线程迁移到另一个物理核心（在同一 L3 共享域中）并在该部分的元素被读取（正常读取）。如果 lock cmpxchg 指令将目标行置于 M 状态，则来自同一 L3 共享域中的另一个物理核心的读取请求应该命中 L3 并且 hit-modified lock cmpxchg 被执行了。这些事件可以使用 OFFCORE_RESPONSE.DEMAND_DATA_RD.L3_HIT.HITM_OTHER_CORE（或等效项）进行计数，这在 most/all 微体系结构上是可靠的。

锁定指令是一项代价高昂的操作，原因有以下三个：(1) 需要使行处于独占状态，(2) 使行变脏（可能不必要），太多的回写会对执行产生重大影响时间，当它们最终从长时间的读取请求中窃取主内存带宽时更是如此，当写入持久内存时更是如此，以及 (3) 它们在架构上进行序列化，这使得指令位于关键路径上。

Intel有一个patent建议对最后一个进行优化，内核乐观地假设没有锁争用，并向目标线路发出推测性的正常负载。如果该线路不存在于任何其他物理内核中，则该线路将在请求内核中处于独占状态。然后，当锁定指令执行并发出 lock-read 请求时，该行有望仍处于独占状态，在这种情况下，锁定指令的总延迟将减少。我不知道是否有任何处理器实现了这种优化。如果实施，L2_TRANS.RFO 事件的数量将比锁定的行数少得多。

cmpxchg 是否在失败时写入目标缓存行？如果不是，自旋锁是否比 xchg 更好？

Does cmpxchg write destination cache line on failure? If not, is it better than xchg for spinlock?

x86

assembly

micro-optimization

compare-and-swap

cpu-cache