3 ms·

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 litt

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.

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.