Memory Ordering in CPUs

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.

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.

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. 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). 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.

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.

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. 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.

Footnotes

1. Reordering of loads/stores originating on the same core is also a concern on out-of-order CPUs, and in fact the primary one. A key source of complexity in OoO designs is pretending instructions executed by the same hardware thread execute in program order, even when they don’t. However, this is true in every OoO design and completely independent of CPU memory models, which are concerned with event ordering between multiple agents, not with how the event stream originating from a single agent comes to be.
2. I write “potential” ordering violations because this tracking is usually conservative in multiple ways. It must correctly flag all pairs of accesses that actually contend, but it doesn’t harm correctness if some non-contending accesses are flagged as a potential ordering violation as well. This will decrease performance if it happens too often, but implementers can adjust that dial to suit their target trade-offs.
3. Again, some distinction based on type of machine and things like memory type. In-order machines without a cache (or uncached memory accesses on machines with a cache) actually follow the memory model to the letter, and this is indeed slow, but speed is not the goal in these scenarios. In-order machines with caches frequently have some mild speculation around this, if only to get things like exclusive cache line reservations in the pipe a bit earlier. And on out-of-order machines, aggressive instruction reordering and speculation are table stakes.
4. Some CPUs like Apple Silicon can be optionally put in a HW TSO mode. This gives a number for the performance impact of TSO (often quoted as around 7%), but it comes with a big asterisk, namely, “the performance impact of TSO in that particular implementation”. Apple Silicon is still an ARM CPU core, designed to run AArch64 code and (presumably) tuned on AArch64 traces, where typically most loads/stores are relaxed. There is no reason to assume that Apple Silicon cores are designed to have the best possible TSO performance. They are ARM cores first and foremost, and the algorithms and internal data structures used are going to be tuned for typical ARM workloads. HW TSO in these CPUs exists to aid Rosetta (i.e. x86 emulation). It is much faster (and, presumably, more power-efficient) than emulating TSO in software would be, as emulators like FEX have to do when no HW TSO exists. But it’s still a compatibility feature, not the main mode of operation the CPU is designed on. Actual x86s are going to make different implementation choices with different trade-offs.