如何在x86处理器上实现“锁定操作”的添加？

Question

我最近在32核Skylake Intel处理器上对std::atomic::fetch_add和std::atomic::compare_exchange_strong进行了基准测试。并不出乎意料（根据我听到的有关fetch_add的传说），fetch_add几乎比compare_exchange_strong可伸缩性高一个数量级。从程序的反汇编代码来看，std::atomic::fetch_add使用lock add实现，而std::atomic::compare_exchange_strong使用lock cmpxchg实现（https://godbolt.org/z/qfo4an）。

是什么让intel多核处理器上的lock add如此快？据我所知，两种指令的速度都受到缓存行争用的影响，并且为了以顺序一致的方式执行两种指令，执行CPU必须将该行以独占或修改模式拉入自己的核心中（来自MESI）。那么处理器如何内部优化fetch_add呢？

---

这是基准测试代码的简化版本。对于compare_exchange_strong基准测试来说，没有load+CAS循环，只有一个在原子变量上进行compare_exchange_strong的输入变量，该变量会不断地被线程和迭代所改变。因此，这只是在多个CPU竞争下比较指令吞吐量的比较。

- Curious

---

你应该展示你的基准测试代码，因为问题往往就出在这里。请注意，即使没有使用LOCK前缀，你仍会遇到相同的缓存争用问题，因为CPU需要将缓存行写入内存，对于任何小于整个缓存行宽度的写操作都是如此。 - Ross Ridge

@RossRidge已经编辑了问题，并附上了基准测试代码。 - Curious

你能发布实际的循环反汇编代码和实际数字（迭代次数/秒）吗？ - rustyx

你并没有真正对 fetch_add() 进行基准测试。因为你没有使用被获取的值，编译器将其优化为原子的“不获取，只添加”，而你所测试的是这个“不获取，只添加”的性能。 - Brendan

您可以将锁定的指令视为对内存互斥量的获取：即内存访问系统可以锁定的最小内存系统部分上的互斥量。它的工作方式保证不会发生死锁，并且该锁不必是乐观的（它永远不需要被取消）。 - curiousguy

@Brendan：lock xadd 大概只是多了几个 uops，本质上并没有什么不同。但是说得好，这也是 OP 可以测试的另一件事情。 - Peter Cordes

Answer 1

lock add 和 lock cmpxchg 本质上都是以相同的方式工作，通过在微代码指令的持续时间内保持该缓存行处于已修改状态。('int num'的num++可以是原子操作吗？)。根据Agner Fog的指令表，lock cmpxchg 和 lock add的微操作数非常相似。 (尽管lock add稍微简单一些)。 Agner的吞吐量数字是针对未争用的情况，其中变量保留在一个核心的L1d缓存中。缓存失误可能会导致uop重放，但我没有看到任何理由期望显着差异。

你声称没有使用load+CAS或重试循环。但是你是否只计算了成功的CAS或其他操作？在x86上，每个CAS（包括失败的）几乎与lock add具有相同的成本。(当所有线程都在同一个原子变量上进行操作时，由于使用了过期的expected值，你会得到许多CAS失败。这不是CAS重试循环的常见用例)。

或者你的CAS版本实际上是从原子变量中进行纯负载以获取expected值吗？这可能会导致内存顺序错误。

由于你在问题中没有完整的代码，所以我只能猜测，并且无法在我的桌面上尝试它。你甚至没有任何性能计数器结果或类似的东西;有许多离核心内存访问的性能事件，例如mem_inst_retired.lock_loads等事件可以记录执行的lock指令数量。

使用lock add，每次一个核心获得缓存行的所有权时，它都会成功地进行增量。核心只等待访问该行的HW仲裁，而不是等待另一个核心获取该行，然后因为它有一个过期的值而无法增加。

---

很可能硬件仲裁可以对待锁的添加和比较交换（lock add和lock cmpxchg）进行不同的处理，例如，让一个核心长时间保持对该行的控制权，以执行几个lock add指令。

你是这个意思吗？

---

或者你在微基准测试方法上出现了一些重大故障，比如在开始计时之前没有进行预热循环以将CPU频率从空闲状态提高？或者可能有些线程提前完成并让其他线程以较少的争用运行？

- Peter Cordes

---

在一个NUMA系统中，由于核心是分散的，锁/比较交换操作的开销会很大吗？ - undefined

@foool: 内核间延迟确实较高，因此争用的成本更高。而且可能有更多的内核都可能争夺同一缓存行的所有权。但是一旦一个内核独占地拥有了一个缓存行，一切都一样；不受争用的原子操作不需要与核外通信，缓存行只需保持在MESI Modified状态。 - undefined

顺便说一句，再看一下这个问题，如果他们是在讨论用于模拟fetch_add的CAS重试循环的成功率，那么10倍的结果可能是有道理的，因为对于没有硬件支持的操作（比如使用返回值的fetch_or），编译器确实需要使用CAS重试循环，或者当你手动想要实现自己的原子RMW操作时，比如原子右移或原子清除最低位的设置。 - undefined

谢谢您的回复，我应该更具体地提问。NUMA节点是否会锁定远程NUMA节点的共享缓存行，以实现对共享值的原子更新？处理器间的争用成本应该高于核间的成本。 - undefined

@foool: NUMA系统仍然具有缓存一致性。一个核心不需要告诉其他核心它正在锁定该行，它只需要延迟响应MESI请求以共享或使该行无效，直到完成为止，因为当该核心处于独占或修改状态时，其他核心甚至无法读取该行。有关本答案第一句的更多详细信息，请参阅在特定情况下递增int是否有效原子操作？（存在非缓存一致的NUMA系统（共享内存集群），但我们不在不同节点之间运行线程。） - undefined

Answer 2

要想以顺序一致性的方式执行这两个指令，执行CPU必须以独占或修改模式（来自MESI）将该行拉入自己的核心中。但是，即使您愿意放弃这些指令的“顺序一致性”（或甚至放弃读写的通常获取和释放保证），为了执行任何一条指令并保证在多个CPU上并发执行不会丢失增量，您都需要这样做。任何锁定指令有效地在内存部分上强制执行互斥，以足以保证原子性。因为在操作期间没有其他核心可以访问该内存范围，所以原子性得到了简单地保证。对于英特尔多核处理器而言，锁定添加指令之所以更快，是因为在这些情况下，我预计时间上的任何微小差异都很关键，并且进行负载加比较（或比较-负载加比较-负载...）可能会改变时序，从而失去机会，就像使用互斥锁的代码在存在重度争用时可能具有广泛不同的效率，并且访问模式的小改变会改变互斥锁的归属方式一样。

- curiousguy