6 ms·

I'm just not sure what consume and the Alpha have to do with each other. Consume is an attempt to give you a lightweight load when all you want are guarantees r

I'm just not sure what consume and the Alpha have to do with each other. Consume is an attempt to give you a lightweight load when all you want are guarantees related to a dependent load. And the Alpha is the only machine I'm aware of where dependent loads don't give you any guarantees. As far as lockless algorithms go - using something like Loom for Rust greatly simplifies correctness. It has a relatively complete implementation of the C++ memory model, and will catch bizarre edge cases you'd struggle to ever replicate on a real CPU. There are also solvers for C++ that help you do similar reasoning. For _performance_, on the other hand, it's the wild west. I experimented with pairing my home grown system similar to Loom with a MESI cache simulator, testing cache behaviour with lockless algorithms banging on the same cache lines. It showed some promise, but was quite difficult to make ergonomic for the consumer.

ajross 3y ago
> I'm just not sure what consume and the Alpha have to do with each other. This seems like semantic evasion? Consume exists[1] precisely so that you can write code using the C++ memory model that works correctly on a superscalar Alpha chip (not the 21064/21164, those are in-order). Saying that it doesn't have anything to do with alpha seems really strained. If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else. [1] Again, AFAIK. Lots of folks in this thread, including you, seem to be implying that other such hardware exists. But I'm not aware of it. And my broader point is that this kind of "standards first" discussion obscures understanding.
- gpderetta 3y ago
  No, approximately nobody cares about Alpha. consume exists so that many algorithms can be implemented cheaply on ARM and POWER without requiring an expensive load-load barrier on the consumer side by relying on data dependencies. For example the Linux kernel makes use of data-dependencies to make RCU cheap on these machines. Still, in practice because of a mixture of being hard to implement[1] and x86 dominating compiler development, most compilers gave up and just implemented consume as an acquire. [1] to make consume work, compilers need to make sure that data dependencies are propagated everywhere they are needed and this is very hard. edit: also in-order machines are very much capable of the kind of reordering that require memory barriers. IIRC the lack of data dependency of alpha was a quirk due to its banked cache setup, not because of pipeline reordering. In fact data-dependences is specifically the kind of reordering that an OoO engine can't do.
  - ajross 3y ago
    > consume exists so that many algorithms can be implemented cheaply on ARM and POWER without requiring an expensive load-load barrier on the consumer side No? Those algorithms can be implemented cheaply already on every architecture BUT Alpha! You just don't use a barrier there, because none is needed. The only reason we're even talking about consume is becasue alpha exists and requires a barrier instruction on dependent loads. No alpha, no consume. QED. Again I repeat: the attempt to obscure this and pretend that features like "consume" are first class theoretic entities unconnected to hardware is IMHO really, really hurting people's ability to understand this subject. It's not like that, it's a hack. Call it a hack to support a legacy architecture and then people will understand why it's there. Pretend that all possible[1] designs for ordering synchronization would require "consume" and you'll have everyone tied up in arguments like this trying to understand what it's for. [1] Which is impossible, obviously. I do much of my day job on an architecture with an incoherent cache where NONE of these silly toys work to solve ordering issues, because they're aimed at a different layer of the stack.
    - gpderetta 3y ago
      With memory_order_acquire, you need a load-load barrier on the read side of RCU on ARM; with memory_order_consume, assuming an optimal implementation you do not. On alpha you need a barrier either way. Hence consume improves performance on ARM (and other similar architectures), but doesn't help Alpha. edit: to be more explicit, you can't formally implement RCU with relaxed + a compiler barrier, although in practice it might work most of the time.
      - tialaramex 3y ago
        I see, I think I'm never going to get this straight, so expect me to screw it up the next time I try to summarise as well, sorry.
- jcranmer 3y ago
  > Consume exists[1] precisely so that you can write code using the C++ memory model that works correctly on a superscalar Alpha chip (not the 21064/21164, those are in-order). No, you have it wrong. Consume exists so that you can write code that works correctly on all chips other than Alpha, x86, and SPARC. > If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else. That's patently false. For the semantics to work correctly, you still need to identify the memory operations that generate synchronization edges. Unannotated loads, by definition, can't generate those edges. Relaxed atomics are sufficient from a hardware perspective, but it ignores the effect of the compiler. The problem with consume--why it's never worked--is that it relies on the compiler preserving data dependencies expressed in the source language, which runs into the issue of a) defining what exactly constitutes a data dependence (hardware implementations don't exactly agree!) and b) this turns out to be a lot more difficult to do than originally anticipated. To even have a hope of being able to correctly reason about the need to not have a load barrier in these places, you need a big, flashing neon sign to the compiler saying "this is special with special semantics, please pay attention." That sign is memory_order_consume.
  - ajross 3y ago
    I don't think that's correct? Can you give an example of an algorithm on x86 or ARM that requires a consume barrier to operate correctly? It's a noop. Dependent loads on those hardware architectures do not reorder, and by definition dependent loads can't be reordered by the compiler (because you can't write time travel code that executes a load before the instruction that loads its pointer!). Consume does not AFAICT act as a memory clobber or optimization barrier to the compiler.
    - gpderetta 3y ago
      consume obviously doesn't need a barrier on arm or x86, but it still needs a source level annotation. relaxed is not enough as the compiler could otherwise break the required dependency (for example by introducing a speculation). In fact consume is in practice not implemented optimally by compilers because it is very very hard to guarantee that the data dependency is not broken in all cases. I.e. the quirks of Alpha have no bearing on the existence of consume. A different annotation between relaxed and acquire would still needed to specifically capture the semantics of data dependencies (that's the theory at least, in practice even consume and the [[carries_dependency]] annotations are not enough).

ajross 3y ago

> I'm just not sure what consume and the Alpha have to do with each other. This seems like semantic evasion? Consume exists[1] precisely so that you can write code using the C++ memory model that works correctly on a superscalar Alpha chip (not the 21064/21164, those are in-order). Saying that it doesn't have anything to do with alpha seems really strained. If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else. [1] Again, AFAIK. Lots of folks in this thread, including you, seem to be implying that other such hardware exists. But I'm not aware of it. And my broader point is that this kind of "standards first" discussion obscures understanding.

gpderetta 3y ago
No, approximately nobody cares about Alpha. consume exists so that many algorithms can be implemented cheaply on ARM and POWER without requiring an expensive load-load barrier on the consumer side by relying on data dependencies. For example the Linux kernel makes use of data-dependencies to make RCU cheap on these machines. Still, in practice because of a mixture of being hard to implement[1] and x86 dominating compiler development, most compilers gave up and just implemented consume as an acquire. [1] to make consume work, compilers need to make sure that data dependencies are propagated everywhere they are needed and this is very hard. edit: also in-order machines are very much capable of the kind of reordering that require memory barriers. IIRC the lack of data dependency of alpha was a quirk due to its banked cache setup, not because of pipeline reordering. In fact data-dependences is specifically the kind of reordering that an OoO engine can't do.
- ajross 3y ago
  > consume exists so that many algorithms can be implemented cheaply on ARM and POWER without requiring an expensive load-load barrier on the consumer side No? Those algorithms can be implemented cheaply already on every architecture BUT Alpha! You just don't use a barrier there, because none is needed. The only reason we're even talking about consume is becasue alpha exists and requires a barrier instruction on dependent loads. No alpha, no consume. QED. Again I repeat: the attempt to obscure this and pretend that features like "consume" are first class theoretic entities unconnected to hardware is IMHO really, really hurting people's ability to understand this subject. It's not like that, it's a hack. Call it a hack to support a legacy architecture and then people will understand why it's there. Pretend that all possible[1] designs for ordering synchronization would require "consume" and you'll have everyone tied up in arguments like this trying to understand what it's for. [1] Which is impossible, obviously. I do much of my day job on an architecture with an incoherent cache where NONE of these silly toys work to solve ordering issues, because they're aimed at a different layer of the stack.
  - gpderetta 3y ago
    With memory_order_acquire, you need a load-load barrier on the read side of RCU on ARM; with memory_order_consume, assuming an optimal implementation you do not. On alpha you need a barrier either way. Hence consume improves performance on ARM (and other similar architectures), but doesn't help Alpha. edit: to be more explicit, you can't formally implement RCU with relaxed + a compiler barrier, although in practice it might work most of the time.
    - tialaramex 3y ago
      I see, I think I'm never going to get this straight, so expect me to screw it up the next time I try to summarise as well, sorry.
jcranmer 3y ago
> Consume exists[1] precisely so that you can write code using the C++ memory model that works correctly on a superscalar Alpha chip (not the 21064/21164, those are in-order). No, you have it wrong. Consume exists so that you can write code that works correctly on all chips other than Alpha, x86, and SPARC. > If alpha didn't exist then consume wouldn't exist and people would be writing these as unconstrained/normal loads because that works everywhere else. That's patently false. For the semantics to work correctly, you still need to identify the memory operations that generate synchronization edges. Unannotated loads, by definition, can't generate those edges. Relaxed atomics are sufficient from a hardware perspective, but it ignores the effect of the compiler. The problem with consume--why it's never worked--is that it relies on the compiler preserving data dependencies expressed in the source language, which runs into the issue of a) defining what exactly constitutes a data dependence (hardware implementations don't exactly agree!) and b) this turns out to be a lot more difficult to do than originally anticipated. To even have a hope of being able to correctly reason about the need to not have a load barrier in these places, you need a big, flashing neon sign to the compiler saying "this is special with special semantics, please pay attention." That sign is memory_order_consume.
- ajross 3y ago
  I don't think that's correct? Can you give an example of an algorithm on x86 or ARM that requires a consume barrier to operate correctly? It's a noop. Dependent loads on those hardware architectures do not reorder, and by definition dependent loads can't be reordered by the compiler (because you can't write time travel code that executes a load before the instruction that loads its pointer!). Consume does not AFAICT act as a memory clobber or optimization barrier to the compiler.
  - gpderetta 3y ago
    consume obviously doesn't need a barrier on arm or x86, but it still needs a source level annotation. relaxed is not enough as the compiler could otherwise break the required dependency (for example by introducing a speculation). In fact consume is in practice not implemented optimally by compilers because it is very very hard to guarantee that the data dependency is not broken in all cases. I.e. the quirks of Alpha have no bearing on the existence of consume. A different annotation between relaxed and acquire would still needed to specifically capture the semantics of data dependencies (that's the theory at least, in practice even consume and the [[carries_dependency]] annotations are not enough).