6 ms·

C++ Memory Model: Migrating from x86 to ARM (2021)

151 points by signa11 3y ago

samsquire 3y ago
I've been using "sfence" memory barrier to enforce visibility in my programs on amd64/x86_64. It's good to know that my programs might need to be adjusted. Chris Wellons [1] has an interesting post about using an explicit __ATOMIC_RELEASE and then __ATOMIC_ACQUIRE to tell thread sanitizer that there is definitely a happens-before relationship between threads. [1]: https://nullprogram.com/blog/2022/10/03/ https://nullprogram.com/blog/2022/10/03/ I have an idea: I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! My understanding is that memory_order_seq_cst or _ATOMIC_SEQ_CST in gcc C means all atomic operations in the same thread happens sequentially from the perspective of other threads. This whitepaper ("How to miscompile programs with “benign” data races") discusses more about compiler optimisations breaking data races. [2]: https://www.usenix.org/legacy/event/hotpar11/tech/final_files/Boehm.pdf https://www.usenix.org/legacy/event/hotpar11/tech/final_file...
- gpderetta 3y ago
  > I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! that would be just a queue, right?
  - samsquire 3y ago
    A queue is part of an event loop solution but I'm thinking from the perspective of Erlang, Smalltalk and Dbus and distributed objects communication. Rust async semantics is pretty hard and difficult to define and understand, there is pinning, runtimes, async/await state machines and awaiting and polling and type system interactions. It's all to create a protocol that allows for concurrency and parallelism that is also safe. It seems the cache coherency protocol IS what we're looking for, which is safe happens before relationships and no data races.
    - u320 3y ago
      Rust async semantics are complex because they need to support resumable computations on a single C-style stack. It has nothing to do with concurrency, which was already supported, but at the cost of multiple stacks (either green threads at one point or OS threads). Futures just happen to be a very prominent example of resumable computations. Generator functions is another.
    - gpderetta 3y ago
      I'm not sure how cache coherency would help here. Cache coherency is specifically about keeping cache coherent (i.e. not stale) in shared memory systems. It is not applicable to pure message passing systems. Also cache coherency per se it has little to say about sequencing and happens-before. That's the job of the memory model built on top (again, still for shared memory). At an higher level still, the general idea of consistency is of course applicable to both shared memory concurrency and message passing concurrency. Maybe consistency models is what you are thinking about? Alternatively, maybe you want to implement shared-memory on top of message passing. In this case cache coherency is definitely applicable, but I'm not sure how amenable are common cache coherency protocols to be implemented in software (but it is certainly possible, and probably what some RDMA system do).
      - samsquire 3y ago
        I'm not an expert but here's my intuition. The L1 cache is very fast and each core has its own 32 kilobytes or so cache. If we could send between L1 caches of cores then couldn't we have latency below 100 nanoseconds?
        gpderetta 3y ago
        You can already have sub 100ns latency on core-to-core communication on some common machines. And yes, thank if the magic of bus snooping the transfer can in practice happen cache to cache, although counterintuitively it is not necessarily what you want for message queues.
    - toast0 3y ago
- nick_ 3y ago
  > I have an idea: I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! If I'm understanding you correctly, this is exactly what I've wanted for a while. Let me use the cached values of things when I want, and let me read and write from/to RAM when I want. Those calls imply the load/store order semantics (I think?).
  - bcrosby95 3y ago
    This sounds like volatile in Java, and while sometimes useful it is still a minor part of writing concurrent code. In particular, once you read the value is potentially stale. If you write to something based upon it you now have a race condition.
- KMag 3y ago
  > I have an idea: I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! That's generally what you get with RCU/lockfree data structures.
weinzierl 3y ago
This is a very approachable, yet detailed, introduction to a difficult topic. I wish I had it when I first got into this. Another good resource for me was Mara Bos' book "Rust Atomics and Locks". It is primarily a Rust book , but I found the concise and reduced to the essentials explanations of memory ordering really helpful.
- sumtechguy 3y ago
  I had this one ARM platform that was absolutely unforgiving on any sort of memory shenanigans that x86 lets you get away with. Read too much data... fault. Too little... fault. Unaligned memory... fault. Really had to go thru the code and make sure anything like that was removed or properly done (curse you sprintf).
  - KMag 3y ago
    I remember Netscape Navigator getting SIGBUS on Solaris SPARC machines once or twice a week. Presumably this was due to most development being done on systems that allowed unaligned memory operations. Architectures that allow unaligned memory operations should at least have some sampling mechanism to record the instruction addresses causing misaligned operations, for both portability and performance improvement of codebases.
    - sumtechguy 3y ago
      while probably true NN was wildly crashy anyway.
deutschepost 3y ago
Gotta love those full phonescreen popups if I want a chat with their sales team. No. And if I would it wouldn’t be over a chat window on a website.
layer8 3y ago
Is there a quick explanation why data races are UB in the C++ MM but not in the Java MM? Famously, Java’s String::hashCode implementation makes use of the Racy Single-Check Idiom, so this is a core functionality on all supported platforms. What is the cost of Java guaranteeing defined behavior here? Or is it just that it would be costly on some non-mainstream platforms not supported by Java but supported by C++?
- bluGill 3y ago
  Data races are generally UB because to make them defined you have to implement some form of locking on all use which is CPU expensive. With a good architecture you can make those data races impossible in the first place in most cases (not all, but most) and this is considered best practice in general: even when there is no data race, it is difficult to reason about all the possible states of your system when data is shared across threads. As such C++ has decided that data races as UB is the correct thing: in most cases the data race doesn't actually exist - the compiler just doesn't have enough information to prove it doesn't exist. When there is an exception you do have to manually add something to your code to force the synchronization, but hopefully that is rare, and when it happens you want to audit that code more anyway. I don't know how Java does data races, but often the language doesn't actually prevent data races the way you want it to. That is A=something; B=SomethingEles; can ensure A is updated before B, but will it ensure that either both A and B are both updated or neither are - which may be what you really need, and of course if you don't need that guarantee having it will slow down code that needs A until B is updated even though it doesn't care.
  - layer8 3y ago
    If you look up the Racy Single-Check Idiom, the point is to have defined behavior without any additional cost (aside from possible duplicate initialization). No locking, and not even volatile. At least on x86 it effectively comes for free.
    - bluGill 3y ago
      On X86 a lot of cases where C++ has UB the behavior could be considered fully defined since there is no optimization the compiler can do based on it being undefined and x86 guarantees memory order. On ARM you get no such guarantees and it isn't free.
NobodyNada 3y ago
For a more in depth introduction to the topic with a lot of practical code examples, I highly recommend Herb Sutter’s excellent talk: Part 1 https://www.youtube.com/watch?v=A8eCGOqgvH4 https://www.youtube.com/watch?v=A8eCGOqgvH4 Part 2 https://www.youtube.com/watch?v=KeLBd2EJLOU https://www.youtube.com/watch?v=KeLBd2EJLOU

151 points by signa11 3y ago

I've been using "sfence" memory barrier to enforce visibility in my programs on amd64/x86_64. It's good to know that my programs might need to be adjusted. Chris Wellons [1] has an interesting post about using an explicit __ATOMIC_RELEASE and then __ATOMIC_ACQUIRE to tell thread sanitizer that there is definitely a happens-before relationship between threads. [1]: https://nullprogram.com/blog/2022/10/03/ https://nullprogram.com/blog/2022/10/03/ I have an idea: I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! My understanding is that memory_order_seq_cst or _ATOMIC_SEQ_CST in gcc C means all atomic operations in the same thread happens sequentially from the perspective of other threads. This whitepaper ("How to miscompile programs with “benign” data races") discusses more about compiler optimisations breaking data races. [2]: https://www.usenix.org/legacy/event/hotpar11/tech/final_files/Boehm.pdf https://www.usenix.org/legacy/event/hotpar11/tech/final_file...

gpderetta 3y ago
> I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! that would be just a queue, right?
- samsquire 3y ago
  A queue is part of an event loop solution but I'm thinking from the perspective of Erlang, Smalltalk and Dbus and distributed objects communication. Rust async semantics is pretty hard and difficult to define and understand, there is pinning, runtimes, async/await state machines and awaiting and polling and type system interactions. It's all to create a protocol that allows for concurrency and parallelism that is also safe. It seems the cache coherency protocol IS what we're looking for, which is safe happens before relationships and no data races.
  - u320 3y ago
    Rust async semantics are complex because they need to support resumable computations on a single C-style stack. It has nothing to do with concurrency, which was already supported, but at the cost of multiple stacks (either green threads at one point or OS threads). Futures just happen to be a very prominent example of resumable computations. Generator functions is another.
  - gpderetta 3y ago
    I'm not sure how cache coherency would help here. Cache coherency is specifically about keeping cache coherent (i.e. not stale) in shared memory systems. It is not applicable to pure message passing systems. Also cache coherency per se it has little to say about sequencing and happens-before. That's the job of the memory model built on top (again, still for shared memory). At an higher level still, the general idea of consistency is of course applicable to both shared memory concurrency and message passing concurrency. Maybe consistency models is what you are thinking about? Alternatively, maybe you want to implement shared-memory on top of message passing. In this case cache coherency is definitely applicable, but I'm not sure how amenable are common cache coherency protocols to be implemented in software (but it is certainly possible, and probably what some RDMA system do).
    - samsquire 3y ago
      I'm not an expert but here's my intuition. The L1 cache is very fast and each core has its own 32 kilobytes or so cache. If we could send between L1 caches of cores then couldn't we have latency below 100 nanoseconds?
      - gpderetta 3y ago
        You can already have sub 100ns latency on core-to-core communication on some common machines. And yes, thank if the magic of bus snooping the transfer can in practice happen cache to cache, although counterintuitively it is not necessarily what you want for message queues.
  - toast0 3y ago
nick_ 3y ago
> I have an idea: I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! If I'm understanding you correctly, this is exactly what I've wanted for a while. Let me use the cached values of things when I want, and let me read and write from/to RAM when I want. Those calls imply the load/store order semantics (I think?).
- bcrosby95 3y ago
  This sounds like volatile in Java, and while sometimes useful it is still a minor part of writing concurrent code. In particular, once you read the value is potentially stale. If you write to something based upon it you now have a race condition.
KMag 3y ago
> I have an idea: I would really like to layer an abstraction ontop of the memory model to formulate a protocol for interprocess/interthread communication. In other words, the cache coherency protocol IS the protocol for message passing. No locks! That's generally what you get with RCU/lockfree data structures.

weinzierl 3y ago

This is a very approachable, yet detailed, introduction to a difficult topic. I wish I had it when I first got into this. Another good resource for me was Mara Bos' book "Rust Atomics and Locks". It is primarily a Rust book , but I found the concise and reduced to the essentials explanations of memory ordering really helpful.

sumtechguy 3y ago
I had this one ARM platform that was absolutely unforgiving on any sort of memory shenanigans that x86 lets you get away with. Read too much data... fault. Too little... fault. Unaligned memory... fault. Really had to go thru the code and make sure anything like that was removed or properly done (curse you sprintf).
- KMag 3y ago
  I remember Netscape Navigator getting SIGBUS on Solaris SPARC machines once or twice a week. Presumably this was due to most development being done on systems that allowed unaligned memory operations. Architectures that allow unaligned memory operations should at least have some sampling mechanism to record the instruction addresses causing misaligned operations, for both portability and performance improvement of codebases.
  - sumtechguy 3y ago
    while probably true NN was wildly crashy anyway.

deutschepost 3y ago

Gotta love those full phonescreen popups if I want a chat with their sales team. No. And if I would it wouldn’t be over a chat window on a website.

layer8 3y ago

Is there a quick explanation why data races are UB in the C++ MM but not in the Java MM? Famously, Java’s String::hashCode implementation makes use of the Racy Single-Check Idiom, so this is a core functionality on all supported platforms. What is the cost of Java guaranteeing defined behavior here? Or is it just that it would be costly on some non-mainstream platforms not supported by Java but supported by C++?

bluGill 3y ago
Data races are generally UB because to make them defined you have to implement some form of locking on all use which is CPU expensive. With a good architecture you can make those data races impossible in the first place in most cases (not all, but most) and this is considered best practice in general: even when there is no data race, it is difficult to reason about all the possible states of your system when data is shared across threads. As such C++ has decided that data races as UB is the correct thing: in most cases the data race doesn't actually exist - the compiler just doesn't have enough information to prove it doesn't exist. When there is an exception you do have to manually add something to your code to force the synchronization, but hopefully that is rare, and when it happens you want to audit that code more anyway. I don't know how Java does data races, but often the language doesn't actually prevent data races the way you want it to. That is A=something; B=SomethingEles; can ensure A is updated before B, but will it ensure that either both A and B are both updated or neither are - which may be what you really need, and of course if you don't need that guarantee having it will slow down code that needs A until B is updated even though it doesn't care.
- layer8 3y ago
  If you look up the Racy Single-Check Idiom, the point is to have defined behavior without any additional cost (aside from possible duplicate initialization). No locking, and not even volatile. At least on x86 it effectively comes for free.
  - bluGill 3y ago
    On X86 a lot of cases where C++ has UB the behavior could be considered fully defined since there is no optimization the compiler can do based on it being undefined and x86 guarantees memory order. On ARM you get no such guarantees and it isn't free.

NobodyNada 3y ago

For a more in depth introduction to the topic with a lot of practical code examples, I highly recommend Herb Sutter’s excellent talk: Part 1 https://www.youtube.com/watch?v=A8eCGOqgvH4 https://www.youtube.com/watch?v=A8eCGOqgvH4 Part 2 https://www.youtube.com/watch?v=KeLBd2EJLOU https://www.youtube.com/watch?v=KeLBd2EJLOU