Memory ordering in CPUs

CPU 中的内存排序

I frequently see statements about differences between strongly ordered architectures (like x86 or SPARC) and weakly ordered architectures (like ARM or RISC-V), with the confident assertion that weakly ordered machines are inherently much more scalable than strongly ordered ones. 我经常看到关于强序架构（如 x86 或 SPARC）与弱序架构（如 ARM 或 RISC-V）之间差异的讨论，其中常伴随着一种自信的断言：弱序机器在本质上比强序机器具有更好的可扩展性。

The key misconception is the implicit assumption that CPUs of all stripes actually obey their memory model for every memory access. They, emphatically, do not. They promise to behave as if they did. There’s a world of difference in that seemingly minor distinction. 这里的一个关键误区在于隐含的假设，即所有类型的 CPU 在进行每次内存访问时都严格遵守其内存模型。事实并非如此。它们只是承诺表现得“好像”遵守了规则一样。在这个看似微小的区别背后，有着天壤之别。

To be clear, some CPU cores actually obey the architectural memory ordering rules to the letter. But this kind of behavior is usually limited to tiny cores or microcontrollers, frequently without a cache. Basically everything else (and that includes bigger in-order designs!) cuts some corners. 需要明确的是，确实有一些 CPU 内核会严格遵守架构定义的内存排序规则。但这种行为通常仅限于微型内核或微控制器，且往往不带缓存。除此之外，几乎所有的设计（包括大型的顺序执行设计！）都会采取一些变通手段。

Specifically, they normally implement memory ordering optimistically. It is assumed that most loads access data that hasn’t been modified by another core recently (nor has any modifications in-flight) and that most stores are not contended. If all data is loaded from memory that hasn’t changed from the time the instruction first entered the pipeline to the time it commits, you can execute them in any order (and out-of-order CPUs do exactly that). 具体来说，它们通常以乐观的方式实现内存排序。系统假设大多数加载操作访问的数据在近期内没有被其他内核修改（也没有正在进行的修改），且大多数存储操作不存在竞争。如果所有数据在指令进入流水线到提交期间都没有发生变化，那么你可以以任何顺序执行它们（乱序执行 CPU 正是这样做的）。

If stores aren’t contended (meaning no two CPUs want to write to the same cache line around the same time), and nobody is going to look at the results, they likewise can be reordered freely. And that is exactly what most CPUs do, most of the time. 如果存储操作不存在竞争（意味着没有两个 CPU 同时想要写入同一个缓存行），且没有其他进程会读取这些结果，那么它们同样可以被自由重排序。而这正是大多数 CPU 在绝大多数时间里所做的事情。

Of course, sometimes, these ordering rules make a difference, otherwise we wouldn’t have them in the first place. But this only matters when accesses are contended: when someone else modified the memory we’re interested in (or at least the cache line that contained it) in between us actually performing the memory access, and that memory access instruction committing, which is the point late in the instruction pipeline when the instruction becomes “official” and its state changes externally visible. 当然，有时这些排序规则确实会产生影响，否则我们根本不需要它们。但这仅在访问存在竞争时才重要：即当我们执行内存访问与该指令提交（指令流水线后期，指令变得“正式”且其状态对外可见的时刻）之间，有其他主体修改了我们关注的内存（或至少是包含该内存的缓存行）。

Pre-commit, instructions can be rolled back if we discover there was a problem, and contention is one of these problems (alongside things like exceptions/traps, interrupts, and mispredicted branches). Therefore, the real implementation is more like a “trust, but verify” approach: we assume that almost all memory accesses are uncontended almost all the time, and this governs how instructions execute. 在提交之前，如果我们发现存在问题，指令是可以回滚的，而竞争就是这类问题之一（此外还有异常/陷阱、中断和分支预测错误等）。因此，实际的实现更像是一种“信任但验证”的方法：我们假设几乎所有的内存访问在绝大多数时间里都是无竞争的，并以此指导指令的执行。

However, we keep around just enough metadata to discover potential memory ordering violations after the fact. When they are detected, the offending instructions can’t commit, the program state is rolled back to just before they executed, and then they are re-tried. This is how everyone does it, weakly ordered or not. 然而，我们会保留足够的元数据，以便在事后发现潜在的内存排序违规。一旦检测到违规，违规指令将无法提交，程序状态会回滚到执行前，然后重新尝试。无论是否为弱序架构，大家都是这样做的。

The difference between memory models, then, is not that machines with strong memory models perform every memory access according to the memory model rules and machines with weak models do not. It’s that, in the event of contention (i.e., for our purposes, an external agent such as another core modifying memory that an in-flight instruction has accessed), strongly ordered machines are more likely to report a conflict (and retry) than weakly ordered machines are. 因此，内存模型之间的区别不在于强序机器严格遵守规则而弱序机器不遵守。区别在于，当发生竞争时（即对于我们而言，有外部代理如另一个内核修改了正在执行的指令所访问的内存），强序机器比弱序机器更有可能报告冲突（并进行重试）。

Furthermore, contention is the slow case everywhere anyway. Weakly ordered machines do enjoy some benefits in this regard, but it doesn’t tend to get you very far in practice (or at least I’ve never seen a big benefit from it in real workloads). My personal mantra for multi-threaded code is to contend less, not contend faster. Your mileage may vary. 此外，无论在哪种架构下，竞争都是导致性能下降的原因。弱序机器在这方面确实享有一定优势，但在实践中这并不能带来太大的提升（至少在实际工作负载中，我从未见过它带来显著的好处）。我个人对于多线程代码的座右铭是：减少竞争，而不是追求更快的竞争处理。当然，你的体验可能会有所不同。

The big distinction between strongly and weakly ordered machines ends up being not that the former executes all memory operations strictly in order and the latter does not, but rather that the former needs to keep enough metadata for every in-flight memory operation to check if there are ordering violations, whereas the latter deals mostly with relaxed loads/stores that only need to be ordered with respect to memory barriers. 强序机器和弱序机器之间的巨大区别最终不在于前者严格按顺序执行所有内存操作而后者不是，而在于前者需要为每一个正在执行的内存操作保留足够的元数据以检查是否存在排序违规，而后者主要处理松散的加载/存储，仅需在内存屏障处保持顺序即可。

It also means that in case of contention, weakly ordered machines have more memory access orderings that are legal (and hence OK to retire) than strongly ordered machines do. These things for sure constrain the implementation, and the cost of memory models like x86s TSO is non-zero, but it’s a lot more nuanced than “x86s and SPARCs have to perform all memory operations in order, ARM and RISC-V CPUs don’t”. There is a cost, but measuring it is not straightforward. 这也意味着在发生竞争时，弱序机器比强序机器拥有更多合法的（因此可以提交的）内存访问排序方式。这些因素确实限制了实现，像 x86 的 TSO 这样的内存模型成本也并非为零，但这比“x86 和 SPARC 必须按顺序执行所有内存操作，而 ARM 和 RISC-V 不需要”这种说法要复杂得多。成本确实存在，但衡量它并不简单。

Moreover, as an empirical data point, we now have server systems with hundreds of CPUs, both in weakly ordered (mostly ARM) and strongly ordered (mostly x86) varieties. Both of these exhibit, broadly, the same characteristics: they do well on “shared nothing” type workloads, tend towards NUMA setups that are rather finicky to use well, and actual contention choke points will completely ruin your day. 此外，作为一个经验数据点，我们现在拥有拥有数百个 CPU 的服务器系统，既有弱序（主要是 ARM）也有强序（主要是 x86）的变体。两者在很大程度上表现出相同的特征：它们在“无共享”类型的工作负载上表现良好，倾向于使用难以调优的 NUMA 设置，并且实际的竞争瓶颈会彻底毁掉你的性能。

Mostly, my main takeaway from dealing with machines with tons of cores is that, as ever, the bleeding edge is a miserable place to be and you’ll have a much better time dealing with setups that have maybe half the number of CPU cores per socket than whatever the current max you can buy off the shelf has. 总的来说，我处理多核机器的主要心得是：一如既往，追求最前沿的技术往往是痛苦的。如果你选择每插槽核心数约为当前市售最大值一半的配置，你的日子会好过得多。

That’s not to say there’s no difference. There obviously is. But the rhetoric around the topic suggests that CPUs with weak memory models should perform much better (or at least be much more power-efficient) in heavily multi-threaded workloads on many-core CPUs, and that’s not been my experience. It feels more along the lines of differences between CPU uArchs from different vendors with different strengths and weaknesses than it does like a bright-line distinction between one approach that scales and another that doesn’t. 这并不是说两者没有区别。显然是有区别的。但围绕这个话题的言论暗示，弱内存模型 CPU 在多核 CPU 的重度多线程工作负载中应该表现更好（或至少更节能），但这并非我的经验。这更像是不同厂商 CPU 微架构在优缺点上的差异，而不是一种“可扩展”与“不可扩展”之间的界限分明的区别。