3 ms·

[Disclaimer: I wrote Rosetta 2 and determined the spec for Apple's TSO mode, so I am obviously biased.] Giesen's article comes off as well-meaning cope from an

[Disclaimer: I wrote Rosetta 2 and determined the spec for Apple's TSO mode, so I am obviously biased.] Giesen's article comes off as well-meaning cope from an x86 fan. A relaxed memory model really does give you some performance. Another memory model flaw here in x86 is more architectural, which is that every instruction with the LOCK prefix is essentially a full barrier (of course, x86 could have provided different instructions while still being under TSO). In programs that make heavy usage of atomic reference counting, this actually helps quite a bit. I would probably put that performance benefit in the single digit percentage range like my sibling comment, which may not seem like much to a SW engineer but is actually pretty serious in CPU microarchitecture. It also helps to be stacked with other architectural advantages over x86, e.g. fixed-length instructions, 32 GPRs (which Intel copied in APX), LDP/STP (which Intel also copied in APX), etc. One of the old arguments from TSO enjoyers was that TSO helps avoid concurrency bugs that people would accidentally introduce, but this was before the C++ memory model propagated throughout the programming world. Nowadays, I think people generally conceptualize memory consistency in terms of acquire/release anyways, so why not use a CPU architecture that uses the same model?

spijdar 8d ago
Do you think there would be any worthwhile gains from relaxing address-dependent load ordering, like on Alpha/AXP? Or was that just a lot of extra pain for little reward?
- cwzwarich 8d ago
  Fun fact: ARM actually has relaxed address dependencies for non-temporal loads, although I don't know if too many implementations of ARM take advantage of this relaxation. I think it is an interesting question. During the Alpha's lifetime as a non-hobbyist architecture, this decision was pretty much universally derided, but this was in the prehistoric eras of concurrent memory models, where people were just trying their best with a mix of C code, intrinsics, uses of `volatile` sprinkled around to hopefully disable optimizations, and inline assembly. When the C++11 memory model came around, they tried to integrate dependency ordering with `memory_order_consume`, and this famously failed, along with every attempt to fix it. I believe the plan is now for C++ (and later C?) to add special-cased RCU primitives. The relaxation makes sense in the abstract. As evidenced from the `memory_order_consume` saga, compiler optimizations regularly violate dependency ordering anyways, so in the strictest sense you can't really rely on it. Of course, that doesn't stop people from "knowing" what their compilers will do in such a situation, but that strategy has become a worse one as the years have passed. I would feel better about the whole situation if there was a good greenfield design for a low-level PL that incorporates explicit dependency ordering. I think it's less clear where the potential HW benefit is in a contemporary CPU. The obvious answer is value prediction, but any CPU performing value prediction has to deal with so many other microarchitectural conditions that can invalidate its speculation decisions that it's not clear this minor one is a huge burden. Of course, people who love TSO might make the same argument, i.e. that it's not a huge burden to snoop cache traffic and invalidate loads (although this is only the load half of TSO, not the store half). I know an Alpha architect who argued that Alpha was right for this decision. I even knew a Transmeta architect who argued for implementing sequential consistency in HW (as Transmeta and derived CPUs actually did). In practice, microarchitectural structures have capacity/throughput limitations, and there are implementations and complexities that only come up in a real design, so everything needs to be evaluated in the context of a real project. I personally think the sweet spot falls to the weaker side of TSO, which also happens to be near the memory consistency model of the low-level languages we're using anyways.
  - cogman10 8d ago
    > and this famously failed, along with every attempt to fix it. What was the cause of failure? I see that it is now deprecated which surprises me. It was my understanding that large portions of this were taken from the Java memory model and in the JVM, it seems to have been pretty successful. Is it because the compilers themselves refused to respect it?
    - jcranmer 8d ago
      The C/C++ memory model starts with Java's data-race free memory model, but makes data races fully UB. Atomics are introduced into C/C++ that allows fine-grained definition of synchronization, with four different models of atomics: sequentially-consistent (equivalent to Java's volatile), release-acquire, release-consume, and relaxed (which are not synchronizing and are therefore closer to a defined data race than proper atomics). The Java 5 memory model doesn't have the concept of atomics, except that volatile variables act like C/C++ sequentially-consistent atomics. Relaxed atomics took a couple of tries to specify, and still have a known out-of-thin-air hole that people are still struggling to solve. But the problem with relaxed atomics is that the practical operational semantics are pretty clear, but the formal model is quite tricky for various reasons. Sequentially-consistent matches the model that most people naively think is going on in hardware (execute a single instruction at a time from a random thread). Release-acquire is a slight relaxation of that model that works well most of the time; the main difference between sequentially-consistent and release-acquire is that release-acquire requires you to specifically release and acquire on the same memory location to get the synchronization, whereas sequentially-consistent synchronizes across different memory locations. Since most multithreaded code tends to have a concept of something like a lock or mutex that is guarding access to a particular region of memory, release-acquire is usually sufficient. Release-consume is supposed to be release-acquire, but only for data-dependent loads of the consume. This is the only part of the memory model that has really failed, and that's because compilers cannot really guarantee preservation of data dependence in the optimizer. (This also comes up with pointer provenance, FWIW).
    - cwzwarich 8d ago
      As my sibling comment from jcranmer points out, it was only `memory_order_consume` that failed outright. The other aspects of the C++ memory model mostly worked out, at least after revision. I believe the last attempt to come up with a comprehensive new proposal was P0190 (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0190r4.pdf https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p01...), which reduced the ordering-imposing dependencies in the model to essentially just be pointer dependencies (which does eliminate some legitimately useful cases, e.g. stealing bits from pointers). The paper mentions the unresolved problem of control dependencies from compiler knowledge of pointer equality, which is intertwined with the pointer provenance discussions from around the same time. I would like to see the basic concept realized in another language some day.
crest 8d ago
Does any other architecture allow split cacheline atomic operations across sockets?
- cwzwarich 8d ago
  I don't think any other architecture ever supported it.
adrian_b 8d ago
In my opinion, conceptualizing memory consistency in terms of acquire/release is wrong and it confuses many programmers. One problem is that 2 kinds of ordered loads and stores are not enough, 4 kinds are needed. Some algorithms need not only load-acquire and store-release, but also a store that is guaranteed to be executed before all subsequent stores and a load that is guaranteed to be executed after all previous loads. These properties are the opposite of those provided by load-acquire and store-release. Except for x86 where any loads and stores behave like this, the other popular ISAs do not have such loads and stores, so stronger than necessary instructions must be used, i.e. load barriers and store barriers. Moreover, the instruction that is named a load barrier in the Arm ISA is not a load barrier, but a stronger barrier, but it must be used instead of a load barrier as no better alternative exists. Besides the fact that not only load-acquire and store-release, but also other 2 ordered loads and stores are needed, a much more serious problem is that load-acquire is not the instruction that is really needed. I have never seen any useful algorithm where load-acquire is the correct instruction to use. In all algorithms, what you want is not an instruction, but a loop that compares memory repeatedly, waiting for some condition to be fulfilled. The 4 most frequent kinds of loops that are needed are wait-for-not-equal, wait-for-equal, wait-for-even and wait-for-zero. These loops may execute a load-acquire, but that is not the desired behavior. What you really need are 2 kinds of barriers, one inside the loop and one immediately after the loop. The internal barrier must prevent the CPU from speculatively executing many future loop instances beyond the conditional jump that terminates the loop body, as it normally does. On x86-64, the instruction PAUSE provides such a barrier. On Aarch64, I suspect that a load-acquire instruction does inhibit this kind of speculative execution, despite the fact that this behavior is not documented. Otherwise, a CPU executing this kind of loop would waste a lot of energy and resources. The barrier after such a loop must prevent speculative memory accesses beyond it. The semantics of load-acquire are not really needed, because all such loads are done in a loop and the memory accesses that follow the loop cannot be executed before such a load, due to the control dependency created by the conditional jump that follows the load. Nonetheless, while normal execution is impossible, the CPU can execute speculatively any loads following the loop and only this speculative execution can break the acquire semantics. Therefore what you really need is a speculation barrier after the loop, not an acquire barrier, whose behavior is provided automatically by the loop, even without any instruction with acquire semantics. On x86-64, if a loop is terminated by an unconditional jump, it is said that such a jump blocks the speculative accesses beyond it. This is why the examples provided by Intel in its optimization manual about how to write this kind of acquire loop show loops terminated with unconditional jumps, even if this makes the loops longer, as otherwise the unconditional jump could have been eliminated by moving the conditional jump at the end of the loop. On x86-64, an alternative to unconditional jumps is the LFENCE instruction, which is a barrier for speculative memory accesses. The so-called load-acquire instruction of Arm might also implement the textbook behavior of load-acquire, of ordering the memory accesses, despite the fact that this behavior is always superfluous, but it must also have the undocumented behavior of being a speculation barrier for memory accesses, otherwise the Arm CPUs would have been very inefficient. However, dedicated speculation barriers of the 2 kinds needed inside the loop and outside the loop would have been more efficient than a load-acquire instruction.

spijdar 8d ago

Do you think there would be any worthwhile gains from relaxing address-dependent load ordering, like on Alpha/AXP? Or was that just a lot of extra pain for little reward?

cwzwarich 8d ago
Fun fact: ARM actually has relaxed address dependencies for non-temporal loads, although I don't know if too many implementations of ARM take advantage of this relaxation. I think it is an interesting question. During the Alpha's lifetime as a non-hobbyist architecture, this decision was pretty much universally derided, but this was in the prehistoric eras of concurrent memory models, where people were just trying their best with a mix of C code, intrinsics, uses of `volatile` sprinkled around to hopefully disable optimizations, and inline assembly. When the C++11 memory model came around, they tried to integrate dependency ordering with `memory_order_consume`, and this famously failed, along with every attempt to fix it. I believe the plan is now for C++ (and later C?) to add special-cased RCU primitives. The relaxation makes sense in the abstract. As evidenced from the `memory_order_consume` saga, compiler optimizations regularly violate dependency ordering anyways, so in the strictest sense you can't really rely on it. Of course, that doesn't stop people from "knowing" what their compilers will do in such a situation, but that strategy has become a worse one as the years have passed. I would feel better about the whole situation if there was a good greenfield design for a low-level PL that incorporates explicit dependency ordering. I think it's less clear where the potential HW benefit is in a contemporary CPU. The obvious answer is value prediction, but any CPU performing value prediction has to deal with so many other microarchitectural conditions that can invalidate its speculation decisions that it's not clear this minor one is a huge burden. Of course, people who love TSO might make the same argument, i.e. that it's not a huge burden to snoop cache traffic and invalidate loads (although this is only the load half of TSO, not the store half). I know an Alpha architect who argued that Alpha was right for this decision. I even knew a Transmeta architect who argued for implementing sequential consistency in HW (as Transmeta and derived CPUs actually did). In practice, microarchitectural structures have capacity/throughput limitations, and there are implementations and complexities that only come up in a real design, so everything needs to be evaluated in the context of a real project. I personally think the sweet spot falls to the weaker side of TSO, which also happens to be near the memory consistency model of the low-level languages we're using anyways.
- cogman10 8d ago
  > and this famously failed, along with every attempt to fix it. What was the cause of failure? I see that it is now deprecated which surprises me. It was my understanding that large portions of this were taken from the Java memory model and in the JVM, it seems to have been pretty successful. Is it because the compilers themselves refused to respect it?
  - jcranmer 8d ago
    The C/C++ memory model starts with Java's data-race free memory model, but makes data races fully UB. Atomics are introduced into C/C++ that allows fine-grained definition of synchronization, with four different models of atomics: sequentially-consistent (equivalent to Java's volatile), release-acquire, release-consume, and relaxed (which are not synchronizing and are therefore closer to a defined data race than proper atomics). The Java 5 memory model doesn't have the concept of atomics, except that volatile variables act like C/C++ sequentially-consistent atomics. Relaxed atomics took a couple of tries to specify, and still have a known out-of-thin-air hole that people are still struggling to solve. But the problem with relaxed atomics is that the practical operational semantics are pretty clear, but the formal model is quite tricky for various reasons. Sequentially-consistent matches the model that most people naively think is going on in hardware (execute a single instruction at a time from a random thread). Release-acquire is a slight relaxation of that model that works well most of the time; the main difference between sequentially-consistent and release-acquire is that release-acquire requires you to specifically release and acquire on the same memory location to get the synchronization, whereas sequentially-consistent synchronizes across different memory locations. Since most multithreaded code tends to have a concept of something like a lock or mutex that is guarding access to a particular region of memory, release-acquire is usually sufficient. Release-consume is supposed to be release-acquire, but only for data-dependent loads of the consume. This is the only part of the memory model that has really failed, and that's because compilers cannot really guarantee preservation of data dependence in the optimizer. (This also comes up with pointer provenance, FWIW).
  - cwzwarich 8d ago
    As my sibling comment from jcranmer points out, it was only `memory_order_consume` that failed outright. The other aspects of the C++ memory model mostly worked out, at least after revision. I believe the last attempt to come up with a comprehensive new proposal was P0190 (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0190r4.pdf https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p01...), which reduced the ordering-imposing dependencies in the model to essentially just be pointer dependencies (which does eliminate some legitimately useful cases, e.g. stealing bits from pointers). The paper mentions the unresolved problem of control dependencies from compiler knowledge of pointer equality, which is intertwined with the pointer provenance discussions from around the same time. I would like to see the basic concept realized in another language some day.

crest 8d ago

Does any other architecture allow split cacheline atomic operations across sockets?

cwzwarich 8d ago
I don't think any other architecture ever supported it.

adrian_b 8d ago

In my opinion, conceptualizing memory consistency in terms of acquire/release is wrong and it confuses many programmers. One problem is that 2 kinds of ordered loads and stores are not enough, 4 kinds are needed. Some algorithms need not only load-acquire and store-release, but also a store that is guaranteed to be executed before all subsequent stores and a load that is guaranteed to be executed after all previous loads. These properties are the opposite of those provided by load-acquire and store-release. Except for x86 where any loads and stores behave like this, the other popular ISAs do not have such loads and stores, so stronger than necessary instructions must be used, i.e. load barriers and store barriers. Moreover, the instruction that is named a load barrier in the Arm ISA is not a load barrier, but a stronger barrier, but it must be used instead of a load barrier as no better alternative exists. Besides the fact that not only load-acquire and store-release, but also other 2 ordered loads and stores are needed, a much more serious problem is that load-acquire is not the instruction that is really needed. I have never seen any useful algorithm where load-acquire is the correct instruction to use. In all algorithms, what you want is not an instruction, but a loop that compares memory repeatedly, waiting for some condition to be fulfilled. The 4 most frequent kinds of loops that are needed are wait-for-not-equal, wait-for-equal, wait-for-even and wait-for-zero. These loops may execute a load-acquire, but that is not the desired behavior. What you really need are 2 kinds of barriers, one inside the loop and one immediately after the loop. The internal barrier must prevent the CPU from speculatively executing many future loop instances beyond the conditional jump that terminates the loop body, as it normally does. On x86-64, the instruction PAUSE provides such a barrier. On Aarch64, I suspect that a load-acquire instruction does inhibit this kind of speculative execution, despite the fact that this behavior is not documented. Otherwise, a CPU executing this kind of loop would waste a lot of energy and resources. The barrier after such a loop must prevent speculative memory accesses beyond it. The semantics of load-acquire are not really needed, because all such loads are done in a loop and the memory accesses that follow the loop cannot be executed before such a load, due to the control dependency created by the conditional jump that follows the load. Nonetheless, while normal execution is impossible, the CPU can execute speculatively any loads following the loop and only this speculative execution can break the acquire semantics. Therefore what you really need is a speculation barrier after the loop, not an acquire barrier, whose behavior is provided automatically by the loop, even without any instruction with acquire semantics. On x86-64, if a loop is terminated by an unconditional jump, it is said that such a jump blocks the speculative accesses beyond it. This is why the examples provided by Intel in its optimization manual about how to write this kind of acquire loop show loops terminated with unconditional jumps, even if this makes the loops longer, as otherwise the unconditional jump could have been eliminated by moving the conditional jump at the end of the loop. On x86-64, an alternative to unconditional jumps is the LFENCE instruction, which is a barrier for speculative memory accesses. The so-called load-acquire instruction of Arm might also implement the textbook behavior of load-acquire, of ordering the memory accesses, despite the fact that this behavior is always superfluous, but it must also have the undocumented behavior of being a speculation barrier for memory accesses, otherwise the Arm CPUs would have been very inefficient. However, dedicated speculation barriers of the 2 kinds needed inside the loop and outside the loop would have been more efficient than a load-acquire instruction.