6 ms·

Are memory ordering semantics a mess? I implemented simulators for x86, ARM and C++ memory models and the documentation for all three was fantastic. What's par

Are memory ordering semantics a mess? I implemented simulators for x86, ARM and C++ memory models and the documentation for all three was fantastic. What's part of it is a mess? I'm also not sure I understand your point about physical machines. Surely what we care about are the guarantees each platform gives. There are plenty of cases where the documented worst case is worse than you'll ever be able to replicate - for now. Sticking to the contract means you're safe on next year's machines, too.

ajross 3y ago
To be glib, the part that answers the question "Who needs consume and why is it there?". As pointed out, Chen answers this incorrectly in the linked article. An upthread poster pointed out (correctly, though they skipped the justification) that Alpha needs this, but was then corrected (incorrectly, AFAICT, though I'm willing to be educated) that this feature was not for Alpha. To be more serious: anyone who's ever tried to implement a lockless algorithm knows how hard this stuff is even if you have a clear and unambiguous set of tools to use to do it. And the C++ memory model is, as mentioned, kinda ambiguous. At the end of the day, in practice these problems are solved on real hardware with real tools that look like "MFENCE" or "DSB" (either directly, or because you're reading the generated assembly trying to figure out how it's going wrong). That's exactly the opposite of the way a good abstraction is supposed to work.
- reitzensteinm 3y ago
  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.

ajross 3y ago

To be glib, the part that answers the question "Who needs consume and why is it there?". As pointed out, Chen answers this incorrectly in the linked article. An upthread poster pointed out (correctly, though they skipped the justification) that Alpha needs this, but was then corrected (incorrectly, AFAICT, though I'm willing to be educated) that this feature was not for Alpha. To be more serious: anyone who's ever tried to implement a lockless algorithm knows how hard this stuff is even if you have a clear and unambiguous set of tools to use to do it. And the C++ memory model is, as mentioned, kinda ambiguous. At the end of the day, in practice these problems are solved on real hardware with real tools that look like "MFENCE" or "DSB" (either directly, or because you're reading the generated assembly trying to figure out how it's going wrong). That's exactly the opposite of the way a good abstraction is supposed to work.

reitzensteinm 3y ago
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.