4 ms·

I don't think that's a distinctive explanation, though (i.e. "memory accesses were reordered" covers it already). On common architectures, from one core itself

by anyfoo 4y ago

I don't think that's a distinctive explanation, though (i.e. "memory accesses were reordered" covers it already). On common architectures, from one core itself it never looks like the memory accesses were reordered. From other cores, it may look like that. If there weren't any caches of any sort, there would not be any observable "memory reordering", unless the same core would observe it as well, which breaks sequential consistency (the guarantee to observe any memory access in program order). (And if I'm not missing anything, reordering memory accesses would be pretty useless without caches anyway.)

firstlink 4y ago
> "memory accesses were reordered" covers it already There are valid weak executions which correspond to no "reordered" memory access pattern at all. This theory can only take you 95% of the way, but that makes it far worse than a theory which only works for 5% of cases.
- anyfoo 4y ago
  Can you elaborate? Genuinely curious.
  - firstlink 4y ago
    I don't want to try to recreate an exact code example on the fly (I'd surely get it wrong). But, there's [C++, rust, etc] code which uses seqcst and acquire/release together to set up this scenario: There are some memory operations on one location using acquire and release, call two effects that happen in some order A and B. Another location is manipulated using seqcst instructions with effects C1, C2, .... We are interested in possible executions where a certain thread observes a sequence of effects C... which is only consistent with A occurring before B. It turns out that it's possible to set this up so that those operations C still don't create a happens-before edge between A and B, and therefore it would be legal for a particular compiler+weakly ordered cpu not to forward the effect A to the operation B. This contradicts any theory based not only on a global total order (which is already more easily ruled out), but even on each thread having a local total order in which it observes all other threads' operations on multiple memory locations. Setting aside that without a code sample my explanation lacks a punch line: If you "believe" the memory reordering explanation, then this is patent nonsense. If you "believe" the actual acq/rel semantics in the relevant specifications, then it's obvious (albeit unintuitive). The problem is, this behavior really can happen, and it may not be that uncommon in complex systems where it is very hidden. Reasoning about these systems using the memory reordering theory will yield results which contradict actual executions on actual compiler/CPU combinations.
    - anyfoo 4y ago
      Indeed a bit difficult without an actual example. OP was alluding that caches and hierarchical memory in general are distinct from „memory reordering“. If I understand correctly, you are saying that the situations you have in mind are indeed a result of caches/hierarchical memory, but cannot be modeled as memory access reordering?
      - firstlink 4y ago
        > situations you have in mind are indeed a result of caches/hierarchical memory, but cannot be modeled as memory access reordering Well yes, but actually no. I mean, my point is that they can't be (correctly!) modeled as memory access reordering. But one doesn't have to and shouldn't appeal to caches. Recent ISAs (aarch64, risc-v) and recent languages (C++11, C<whatever it is now>, rust) are both defined based on acquire-release semantics: both hardware and software engineers have decided this is the common set of requirements we want to use. For software programmers to attempt to reason about cache hierarchies is not only unnecessary, it would also potentially be just as wrong as memory reordering if the design of new microarchitectures changes. But as long as those new uarches conform to existing ISAs, and/or are targeted by existing languages, then the acq-rel model will not change out from under you. So it is the only one that should be used. Indeed, the memory reordering theory seems to originate from this same kind of appeal to microarchitecture which are now out of date, i.e. whatever the first multiprocessing x86 cores did.
pajko 4y ago
Caches might be coherent, meaning that the masters might look into each others' content without any flushing. That was cool when I was working on DMA-heavy code on a MIPS CPU. However it's not just about caches, but write buffers also. "Modern" GPUs play tricks with memory accesses by combining them and certain CPUs use this feature to combine byte accesses to word accesses, reorder accesses sequentially in a short span, and eliminate redundant stores/loads. Sometimes it helps quite much on performance, but hurts concurrency pretty much. 10% of the code was a call to the au_sync() macro to flush the write buffer... followed by some more instructions to flush the cache, in case it was required.

by anyfoo 4y ago

firstlink 4y ago

> "memory accesses were reordered" covers it already There are valid weak executions which correspond to no "reordered" memory access pattern at all. This theory can only take you 95% of the way, but that makes it far worse than a theory which only works for 5% of cases.

anyfoo 4y ago
Can you elaborate? Genuinely curious.
- firstlink 4y ago
  I don't want to try to recreate an exact code example on the fly (I'd surely get it wrong). But, there's [C++, rust, etc] code which uses seqcst and acquire/release together to set up this scenario: There are some memory operations on one location using acquire and release, call two effects that happen in some order A and B. Another location is manipulated using seqcst instructions with effects C1, C2, .... We are interested in possible executions where a certain thread observes a sequence of effects C... which is only consistent with A occurring before B. It turns out that it's possible to set this up so that those operations C still don't create a happens-before edge between A and B, and therefore it would be legal for a particular compiler+weakly ordered cpu not to forward the effect A to the operation B. This contradicts any theory based not only on a global total order (which is already more easily ruled out), but even on each thread having a local total order in which it observes all other threads' operations on multiple memory locations. Setting aside that without a code sample my explanation lacks a punch line: If you "believe" the memory reordering explanation, then this is patent nonsense. If you "believe" the actual acq/rel semantics in the relevant specifications, then it's obvious (albeit unintuitive). The problem is, this behavior really can happen, and it may not be that uncommon in complex systems where it is very hidden. Reasoning about these systems using the memory reordering theory will yield results which contradict actual executions on actual compiler/CPU combinations.
  - anyfoo 4y ago
    Indeed a bit difficult without an actual example. OP was alluding that caches and hierarchical memory in general are distinct from „memory reordering“. If I understand correctly, you are saying that the situations you have in mind are indeed a result of caches/hierarchical memory, but cannot be modeled as memory access reordering?
    - firstlink 4y ago
      > situations you have in mind are indeed a result of caches/hierarchical memory, but cannot be modeled as memory access reordering Well yes, but actually no. I mean, my point is that they can't be (correctly!) modeled as memory access reordering. But one doesn't have to and shouldn't appeal to caches. Recent ISAs (aarch64, risc-v) and recent languages (C++11, C<whatever it is now>, rust) are both defined based on acquire-release semantics: both hardware and software engineers have decided this is the common set of requirements we want to use. For software programmers to attempt to reason about cache hierarchies is not only unnecessary, it would also potentially be just as wrong as memory reordering if the design of new microarchitectures changes. But as long as those new uarches conform to existing ISAs, and/or are targeted by existing languages, then the acq-rel model will not change out from under you. So it is the only one that should be used. Indeed, the memory reordering theory seems to originate from this same kind of appeal to microarchitecture which are now out of date, i.e. whatever the first multiprocessing x86 cores did.

pajko 4y ago

Caches might be coherent, meaning that the masters might look into each others' content without any flushing. That was cool when I was working on DMA-heavy code on a MIPS CPU. However it's not just about caches, but write buffers also. "Modern" GPUs play tricks with memory accesses by combining them and certain CPUs use this feature to combine byte accesses to word accesses, reorder accesses sequentially in a short span, and eliminate redundant stores/loads. Sometimes it helps quite much on performance, but hurts concurrency pretty much. 10% of the code was a call to the au_sync() macro to flush the write buffer... followed by some more instructions to flush the cache, in case it was required.