11 ms·

ARM and Lock-Free Programming

229 points by markdog12 6y ago

KingMachiavelli 6y ago
Does Rust and it's borrow checker make this easier/implicit? If compiled code will have to work on both RISC and CISC for the near future. Is the burden to do lock free C++ by identifying all the memory conditions outway the learning curve of Rust? Don't know Rust beyond dead simple projects but just curious.
- chrismorgan 6y ago
  Rust’s ownership and concurrency model prevent you from writing such broken code by accident. The early code examples in the article wouldn’t compile in Rust: you have to use atomic types explicitly, or pass values around explicitly (which will most commonly match the two paradigms of memory sharing and message passing). Rust makes doing things the way shown here quite difficult, which is a good thing, because the idiomatic functionally-equivalent code in Rust will be much easier to follow.
- aliceryhl 6y ago
  Writing to an ordinary integer in Rust only compiles if it is guaranteed that the integer is not shared with any other code, so writing to that boolean would not compile with an ordinary integer. Rust instead has various special types, such as AtomicBool, that works in the same way as the C++ atomic bool from the example. That said, to actually write the release/acquire thing they did, you will need unsafe code because, to the compiler, the other variables are also shared, and would normally be prevented even if you used the atomic. That said, it would be possible to encapsulate this unsafe in a library without infecting other parts of the code.
- mhh__ 6y ago
  Compiler checking of multi-threaded code is a good step forward (D has it too, albeit no one's entirely sure how to move forward with the feature), but to access the actual gadget (fence, etc.) you still need some level of either programmer guidance or library code to manage that access
- ncmncm 6y ago
  You can do everything you might do in Rust equally as easily in C++. The compiler won't hold your hand, so much, but if you wrap the semantics in a library, and use the library, you get the same reliability from it. (This is an unpopular observation in certain places.)
  - floatboth 6y ago
    The power of Rust is not in what you can do, it's in what you can't (without the `unsafe` keyword). C++ doesn't have the prevention. If you're not an expert on concurrency, you might just share mutable access to a regular bool variable between threads and use it in that way (as in the article) and nothing would tell you it's wrong. You wouldn't know you need a specific library (or just "to use std::atomic" in this case) until you encounter the weird runtime behavior, try to debug it, try to formulate a google query that describes the bugs/code well enough, and find the answers. "Hand holding" (i.e. rejecting programs that don't conform to more advanced correctness rules) is great. It's what computers are good at. It's foolish not to use computers for this!
    - ncmncm 6y ago
      > C++ doesn't have the prevention Obviously. But that was not the topic. A discipline of single-writer is as easily composed in C++, and, encapsulated in a library, as easily maintained. Nothing about Rust makes this unavailable in C++. The library itself, then, becomes responsible for maintaining the discipline, not the compiler. But once encoded there, it is done. Rust's compiler provides safety advantages, but there is no need to exaggerate them. (Exaggeration is a liability to your language community.)
  - adwn 6y ago
    > [...] if you wrap the semantics in a library, and use the library, you get the same reliability from it. Wrong. Rust offers more tools for checking that your library is used correctly than C++ does. First and foremost, the borrow checker – there is nothing comparable in C++, and it's a lot harder/impossible to statically prevent code from modifying shared data after a mutex has been unlocked, for example. > (This is an unpopular observation in certain places.) It is unpopular because it is factually incorrect.
signa11 6y ago
previously : https://news.ycombinator.com/item?id=25255113 https://news.ycombinator.com/item?id=25255113
- speedgoose 6y ago
  This has no comments though.
mehrdadn 6y ago
If you want to dig deeper, watch these videos: https://herbsutter.com/2013/02/11/atomic-weapons-the-c-memory-model-and-modern-hardware/ https://herbsutter.com/2013/02/11/atomic-weapons-the-c-memor...
- sprachspiel 6y ago
  Even after watching these videos and reading lots of articles on the topic, I still find the full C++ memory model extremely hard to understand. However, on x86 there are actually only a couple of things that one needs to understand to write correct lock free code. This is laid out in a blog post: https://databasearchitects.blogspot.com/2020/10/c-concurrency-model-on-x86-for-dummies.html https://databasearchitects.blogspot.com/2020/10/c-concurrenc...
  - dragontamer 6y ago
    C++'s "seq_cst" model is simple. If you're having any issues understanding anything at all, just stick with seq_cst. If you want slightly better performance on some processors, you need to dip down into acquire-release. This 2nd memory model is faster because of the concept of half-barriers. Lets say you have: a(); b(); acquire_barrier(); // Half barrier c(); d(); e(); release_barrier(); // Half barrier f(); g(); The compiler, CPU, and cache is ALLOWED to rearrange the code into the following: acquire_barrier(); // Optimizer moved a() and b() from outside the barrier to inside the barrier a(); b(); d(); c(); e(); g(); f(); release_barrier(); // Optimizer moved g() and f() from outside the barrier to inside the barrier You're allowed to move optimizations "inside" towards the barrier, but you are not allowed to rearrange code "outside" of the half-barrier region. Because more optimizations are available (for the compiler, the CPU, or the caches), half-barriers execute slightly faster than full sequential consistency. ---------- Now that we've talked about things in the abstract, lets think about "actual" code. Lets say we have: int i = 0; // a(); i++; // b(); full_barrier(); // seq_cst barrier i+=2; // c(); i+=3; // d(); i+=4; // e(); full_barrier(); // seq_cst barrier i+=5; // f(); i+=6; // g(); As the optimizer, you're only allowed to optimize to... int i = 1; // a() and b() rearranged to the same line full_barrier(); // Not allowed to optimize past this line i+= 9; // c, d, and e rearranged full_barrier(); i+= 11; // f, g rearranged. Now lets do the same with half barriers: int i = 0; // a(); i++; // b(); acquire_barrier(); // acquire i+=2; // c(); i+=3; // d(); i+=4; // e(); release_barrier(); // release i+=5; // f(); i+=6; // g(); Because all code can be rearranged to the "inside" of the barrier, you can simply write: i = 21; Therefore, half-barriers are faster. ---------- Now instead of the compiler rearranging code: imagine the L1 cache is rearranging writes to memory. With full barriers, the L1 cache has to write: i = 1; full_barrier(); // Ensure all other cores see that i is now = 1; i = 10; // L1 cache allows CPU to do +2, +3, and +4 operations, but L1 "merges them together" and other cores do NOT see the +2, +3, or +4 operations full_barrier(); // L1 cache communicates to other cores that i = 10 now; i = 21; // L1 cache allows CPU to do +5 and +6 operations // Without a barrier, L1 cache doesn't need to tell anyone that i is 21 now. No communication is guaranteed. ---------- Similarly, with half-barriers instead, the L1 cache's communication to other cores only has to be: i = 21; // L1 cache can "lazily" inform other cores, allowing the CPU to perform i+=1, i+=2... i+=6. So for CPUs that implement half-barriers (like ARM), the L1 cache can communicate ever so slightly more efficiently, if the programmer specifies these barriers. ---------- Finally, you have "weak ordered atomics", which have no barriers involved at all. While the atomics are guaranteed to execute atomically, their order is completely unspecified. There's also consume / release barriers, which no one understands and no compiler implements. So ignore those. :-) They're trying to make consume/release easier to understand in a future standard... and I don't think they got all the "bugs" out of the consume/release standard yet. ------- EDIT: Now that I think of it, acquire_barriers / release_barriers are often baked into a load/store operation and are "relative" to a variable. So the above discussion is still inaccurate. Nonetheless, I think its a simplified discussion to kinda explain why these barriers exist and why programmers were driven to make a "more efficient barrier" mechanic.
fulafel 6y ago
Piggybacking this question for people interested in the topic: Which everyday high level data structures you use are built on lock-free implementations? Clojure's maps/vectors (which are persistent data structures) come to mind for me, for one.
- forrestthewoods 6y ago
  Almost zero. Queues or streams may have lockless properties. Or maybe not! For the most part concurrent, mutable access to a shared data structure is undesirable and to be avoided. If you find yourself wanting a lockless hashmap you’re going down the wrong path 99.9% of the time. There are always exceptions. But you better have a REALLY good reason why.
- jeffreygoesto 6y ago
  https://github.com/eclipse/iceoryx https://github.com/eclipse/iceoryx
- bitcharmer 6y ago
  SPSC (single producer single consumer) queues and ring buffers are used quite extensively in low-latency software engineering.
  - jamesmunns 6y ago
    Yup! In Rust specifically, I've written bbqueue, which is a bipbuffer-inspired lock-free ring buffer, intended for embedded systems and DMA usage. https://github.com/jamesmunns/bbqueue https://github.com/jamesmunns/bbqueue It uses atomics (and Rust's borrow checker) heavily to safely guarantee lock free behavior, and works pretty darn quick.
    - caspper69 6y ago
      You reference a blog post on your Github (regarding the algo description). I believe the author of that blog (someone at Ferrous Systems) has a pretty significant misunderstanding of DMA and serial ports, which raises a whole host of other questions on down the chain <additional unnecessary comment removed>. edit: I know it's not cool to complain about downvotes, but this is a legitimate concern to raise for this poster. I am not attempting to denigrate anyone here.
runeks 6y ago
I appreciate learning more about what, exactly, ARM's "weaker memory model" constitutes. It's clearer to me after reading this article. I wonder how much the gain in performance of e.g. Apple's M1 chip, compared to an x86 CPU, can be attributed to this weaker constraint. Given that the M1 can outperform an x86 CPU even when emulating x86 code, perhaps it's not much. Also, I suspect programming languages that are immutable by default will gain a larger advantage using ARM's weaker memory model, as the compiler can more often safely let the CPU perform reordering (due to not having to wait for a mutable variable being updated until it can execute a subsequent line of code which depends on this updated variable).
- saagarjha 6y ago
  The M1 chip can do uncontended atomics almost "for free", and offers a mode where it firms up its memory ordering without much performance loss, so I am not actually sure how much this gets them.
  - KMag 6y ago
    Well, it gets them enough that they bothered implementing all of the circuitry for both memory models and an extra bit of thread state to switch between them. I'm sure they did a bunch of simulation before going with that decision. I'm sure they did some simulations before going down that road and found that it was worth it vs. just going with a more strict x86-like memory model all the time.
    - cma 6y ago
      > I'm sure they did some simulations before going down that road and found that it was worth it vs. just going with a more strict x86-like memory model all the time. Or they didn't want developers to rely on it so they can remove it in the future when they deprecate x64 (they deprecated x86 so it is only a matter of time).
      - KMag 6y ago
        > Or they didn't want developers to rely on it If simulations show that it's not currently worth the effort, but they want to keep the option open, that implies that they believe some technological change in the future may make the relaxed memory model bear fruit. Actually, now that I think about it, another option is that the weaker memory model is more advantageous in lower power implementations, like iWatch, and preventing developers from relying on the stronger memory model available in M1 reduces the number of bugs in iWatch applications that share code with iPhone apps or OSX apps.
cesaref 6y ago
The most annoying aspect of lock free programming is the amount of 'roll your own' that goes on, and having to inspect this stuff to ensure it's got a chance of working on the platforms you care about. I totally get that this technique is inappropriate for many situations where a lock works well enough, but I work in a field (audio) where accidental use of locks and system calls is in general a larger problem than incorrect lock free code.
- jcelerier 6y ago
  Hm, in c++ there are a fair amount of battle-tested, permissively-licensed lockfree containers though I use https://github.com/cameron314/readerwriterqueue https://github.com/cameron314/readerwriterqueue and https://github.com/cameron314/concurrentqueue https://github.com/cameron314/concurrentqueue ; they deliver.
  - scott_s 6y ago
    Yes, in addition to the atomics and memory ordering primitives added in the C++11 standard [1], I find the Boost lock-free structures quite reasonable [2]. (Yes, I'm aware some have an automatic aversion to Boost. But it is well-designed and I believe is a header-only library.) [1] https://en.cppreference.com/w/cpp/atomic https://en.cppreference.com/w/cpp/atomic [2] https://www.boost.org/doc/libs/1_74_0/doc/html/lockfree.html https://www.boost.org/doc/libs/1_74_0/doc/html/lockfree.html
bullen 6y ago
As long as this code runs fine on ARM we're going to be ok: http://move.rupy.se/file/atomic.txt http://move.rupy.se/file/atomic.txt
ncmncm 6y ago
The importance and value of lock-free programming is massively overrated. I routinely improve performance and also reliability of systems by deleting lock-free queues. The secret to both is reduced coupling, which lock-free methods do nothing to help with. Atomic operations invoke hardware mechanisms that, at base, are hardly different from locks. While they won't deadlock by themselves, they are so hard to get right that failures equally as bad as deadlocking are hard to avoid. So, replace threads with separate processes that communicate via ring buffers, and batch work to make interaction less frequent. With interaction infrequent enough, time spent synchronizing, when you actually do it, becomes negligible.
- KMag 6y ago
  > So, replace threads with separate processes that communicate via ring buffers ... but those ringbuffers you're using presumably have a lockfree fast path with a futex or pthread mutex slow path to prevent the consumer from busy-waiting, so you're still taking advantage of lockfree data structures.
  - ncmncm 6y ago
    You may presume so, but you would be wrong. They are technically (also) lock-free, so require atomic operations when announcing additions, but being written by only one process, ownership of cache lines never changes, so hardware locks are not engaged. Readers do poll, and sleep as long as the tolerated latency when nothing new is found. Writers batch additions, and announce new entries only just so frequently.
    - KMag 6y ago
      Interesting, though the overhead of nanosleep vs. futex wait with non-NULL timeout should be dwarfed by the context switch. I can see where if you have extreme latency and/or throughput constraints on the writer side of the ring buffer, you couldn't afford the extra atomic read and occasional futex wake on the writer side to wake the consumer. > but being written by only one process, ownership of cache lines never changes, so hardware locks are not engaged. Which cache coherency protocol are you referring to where cache lines are "locked"? I'm aware that early multiprocessor systems locked the whole memory bus for atomic operations, but my understanding is that most modern processors use advanced variants on the MESI protocol[0]. In the MOESI variant, an atomic write (or any write, for that matter) would put the cache line in the O state in the writing core's cache. If we had to label cache line states as either "locked" or "unlocked", the M, O, and E states would be "locked", and S and I would be "unlocked". Your knowledge of cache coherency protocols is probably much better than mine, so I'm probably just misinterpreting your shorthand jargon for "locked" cache lines. By "hardware locks are not engaged" do you just mean that the O state doesn't ping-pong between cores? [0] http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2...
andy_threos_io 6y ago
Lock-Free programming is essential in high performance networking (10G+ network connections) and data communications. Most of the implementation are using ringbuffers. There can be multiple producer consumer implementation as well. But it's not a real issue for the new M1 minis as its network is down to 1Gbit (from the previous mini 10G).
- CharlesW 6y ago
  > But it's not a real issue for the new M1 minis as its network is down to 1Gbit (from the previous mini 10G). FWIW, that's just the built-in port. 10G adapters will do 900MB/s. https://www.owcdigital.com/products/thunderbolt-3-10g-ethernet-adapter https://www.owcdigital.com/products/thunderbolt-3-10g-ethern...
xmodem 6y ago
Aside - calling it now - but the M1's x86 memory model mode is a temporary thing that'll go away in a few years along with Rosetta 2 once Apple is happy with the level of universal binary support.
- gwbas1c 6y ago
  > in a few years Pure speculation: I suspect that Apple will support x86 longer than it supported PPC. Why? The macOS platform is "older" now and more popular than when PPC was around. There's more old applications laying around, unmaintained. Also, don't forget that "windows compatibility" was a huge Mac selling point when they switched to x86. So, I suspect a minimum of 8 years support, but possibly indefinitely if Windows can't make the jump to ARM. Again, pure speculation, but what will be the deciding factor is if x86 virtualization on ARM Mac ever becomes a thing. (And I hope it does!)
  - xmodem 6y ago
    > I suspect that Apple will support x86 longer than it supported PPC. Totally agree - I was surprised how quickly they dropped PPC support. The install base is so much larger now, and hardware refresh cycles so much longer that it'll be necessary. Hell, they've said this transition will take 2 years - the Intel transition took them a year to go from no Intel macs to all Intel macs. > So, I suspect a minimum of 8 years support, Not gonna happen. The Apple of today does not care about old unmaintained applications and definitely does not want to make computers for people to run Windows on.
    - gwbas1c 6y ago
      > The Apple of today does not care about old unmaintained applications The Apple of today is not the Apple of tomorrow. Considering how awesome the M1 Macs sound; if Mac reaches a high marketshare, it might be required.
- ant6n 6y ago
  I understand M1 has a special mode that implements the x86 memory model, which aids in Emulation. Apparently qualcom doesn’t have that, so x86 on Arm Windows is slow, being littered with memory barriers. Couldn’t one just use userthreads in an emulator and ignore all these memory issues? Sure that would mean every emulated process is running on one core, but as long as blocking io is implemented properly, how bad can that be? (It would be like having a single core for the emulated process)
alvarelle 6y ago
> ... std::atomic<bool>. This tells the compiler not to elide reads and writes of this variable, ... If I'm not mistaken, this is not true. The compiler is still allowed to elide reads and writes on atomic variables. (For example merge two consecutive writes, or remove unused reads)
- gpderetta 6y ago
  Correct. See "N4455 No Sane Compiler Would Optimize Atomics" [1]. The first sentence of that paper is (spoiler allert) a laconic "false". [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4455.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n445...
- brucedawson 6y ago
  Updated. Thanks for the correction.
marcan_42 6y ago
This reminds me of some lock-free code I fixed recently (by introducing a very peculiar kind of lock): https://github.com/Ardour/ardour/blob/master/libs/pbd/pbd/rcu.h https://github.com/Ardour/ardour/blob/master/libs/pbd/pbd/rc... The goal of the code is to allow a producer thread to update a pointer to an object in memory, which may be used lazily by consumer threads. Consumers are allowed to use stale versions of the object, but must not see inconsistent state. Obsolete objects must eventually be freed, but only after all consumers are done using them. And here's the catch: consumers are real-time code, so they must never block on a lock, nor are they allowed to free nor allocate memory on their own. The design is based around Boost's shared_ptr, so that had to stay. But the original code was subtly broken: the object is passed around by passing a pointer to a shared_ptr (so double indirection there) which gets cloned, but there was a race condition where the original shared_ptr might be freed by the producer while the consumer is in the process of cloning it. My solution ended up being to introduce a "lopsided spinlock". Consumers aren't allowed to block, but producers are. So consumers can locklessly signal, via an atomic variable, that they are currently inside their critical section. Then the producer can atomically (locklessly) swap the pointer at any time, but must spin (is this a half-lock?) until no consumers are in the critical section before freeing the old object. This ensures that any users of the old pointer have completed their clone of the shared_ptr, and therefore freeing the old one will no longer cause a use-after-free. Finally, the producer holds on to a reference to the object until it can prove that no consumers remain, to guarantee that the memory deallocation always happens in producer context. shared_ptr then ensures that the underlying object lives on until it is no longer needed. It's kind of weird to see a half-spinlock like this, where one side has a "critical section" with no actual locking, and the other side waits for a "lock" to be released but then doesn't actually lock anything itself. But if you follow the sequence of operations, it all works out and is correct (as far as I can tell). For various reasons this code has to build with older compilers, hence can't use C++ atomics. That's why it's using glib ones. (Note: I'm not 100% sure there are no hidden allocations breaking the realtime requirement on the reader side; I went into this codebase to fix the race condition, but I haven't attempted to prove that the realtime requirement was properly respected in the original code; you'd have to carefully look at what shared_ptr does behind the scenes)
- gpderetta 6y ago
jnwatson 6y ago
This is common knowledge in embedded circles, where weak memory models are the norm. This article doesn't address a different kind of memory weakness in some ARM implementations (and I presume other architectures) that you can run into when sharing memory between processes. The data cache is virtually tagged, virtually indexed, which means that the cache is keyed with the domain (essentially the process number) + the virtual address. This means that the MMU doesn't have to be consulted for cache lookups, however, if you have two different processes mapped into the same physical memory, the writing process must execute a flush instruction, and the reading process must execute an invalidate instruction.
- Arelius 6y ago
  Ohh, Thanks! I had never heard about ARM's cache being tagged like that. Do you have any recommended reading?
JoeAltmaier 6y ago
Very educational. I take exception with the common assertion that 'code is broken' if it doesn't work everywhere for every architecture. Code deployed for a particular purpose on a particular machine with a particular toolchain can work great and be 'correct' for that environment. I work in such environments all the time. And taking the time/performance hit seeking ill-conceived perfection wastes the clients time and money. But for the vast majority of cloud-deployed or open-source prjects, its certainly wise to err on the side of 'perfect'.
- brucedawson 6y ago
  When I said "that code was probably broken already" I meant that while the code might currently be working it could suddenly stop working if you upgrade your compiler. Yes, you are free to take that risk, but relying on things not guaranteed by the language is dangerous.
jhallenworld 6y ago
I thought barriers were required on x86 also. There are a few cases where ordering is not guaranteed. [Also the consumer should have a barrier between the test and the data read.] https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/ https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fe... The thing that's nice about x86 is that DMA is cache coherent- this is true for backwards compatibility with very old hardware.
- dragontamer 6y ago
  At the assembly level, barriers are not required in many cases because x86 have total-store ordering. There are a few cases where memory-barriers are still needed... but not nearly as many examples as in ARM-world. At the C / C++ level, barriers are required because almost all compilers rearrange code in the name of optimization (especially as you go from -O to -O1, to -O2, to -O3... more aggressive rearrangements happen). The optimizer needs to know "not" to rearrange some code, so a compiler barrier is needed. --------- It turns out that a compiler barrier (hey compiler: do not rearrange this read/write I'm specifying) is identical in concept to a CPU-memory barrier on a weak-ordered system (hey CPU: don't reorder this read/write I'm specifying).
vbezhenar 6y ago
What I'm afraid is with the introduction of ARM desktops, there will be subtle bugs which did not manifest on x86. Those bugs are hard to find in old legacy multi-million LoC codebase with lots of spaghetti code nobody bothered to refactor, so those bugs will haunt users for years. That's why I'm reluctant to move to this architecture at least for a few years, even if it's superior in theory. Thankfully ARM phones were a thing for a lot of time, so many libraries should work well.
mlindner 6y ago
This guy is a member of Antifa. I'm not a fan of people reposting articles by known left-wing terrorist organizations on hacker news.

229 points by markdog12 6y ago

Does Rust and it's borrow checker make this easier/implicit? If compiled code will have to work on both RISC and CISC for the near future. Is the burden to do lock free C++ by identifying all the memory conditions outway the learning curve of Rust? Don't know Rust beyond dead simple projects but just curious.

chrismorgan 6y ago
Rust’s ownership and concurrency model prevent you from writing such broken code by accident. The early code examples in the article wouldn’t compile in Rust: you have to use atomic types explicitly, or pass values around explicitly (which will most commonly match the two paradigms of memory sharing and message passing). Rust makes doing things the way shown here quite difficult, which is a good thing, because the idiomatic functionally-equivalent code in Rust will be much easier to follow.
aliceryhl 6y ago
Writing to an ordinary integer in Rust only compiles if it is guaranteed that the integer is not shared with any other code, so writing to that boolean would not compile with an ordinary integer. Rust instead has various special types, such as AtomicBool, that works in the same way as the C++ atomic bool from the example. That said, to actually write the release/acquire thing they did, you will need unsafe code because, to the compiler, the other variables are also shared, and would normally be prevented even if you used the atomic. That said, it would be possible to encapsulate this unsafe in a library without infecting other parts of the code.
mhh__ 6y ago
Compiler checking of multi-threaded code is a good step forward (D has it too, albeit no one's entirely sure how to move forward with the feature), but to access the actual gadget (fence, etc.) you still need some level of either programmer guidance or library code to manage that access
ncmncm 6y ago
You can do everything you might do in Rust equally as easily in C++. The compiler won't hold your hand, so much, but if you wrap the semantics in a library, and use the library, you get the same reliability from it. (This is an unpopular observation in certain places.)
- floatboth 6y ago
  The power of Rust is not in what you can do, it's in what you can't (without the `unsafe` keyword). C++ doesn't have the prevention. If you're not an expert on concurrency, you might just share mutable access to a regular bool variable between threads and use it in that way (as in the article) and nothing would tell you it's wrong. You wouldn't know you need a specific library (or just "to use std::atomic" in this case) until you encounter the weird runtime behavior, try to debug it, try to formulate a google query that describes the bugs/code well enough, and find the answers. "Hand holding" (i.e. rejecting programs that don't conform to more advanced correctness rules) is great. It's what computers are good at. It's foolish not to use computers for this!
  - ncmncm 6y ago
    > C++ doesn't have the prevention Obviously. But that was not the topic. A discipline of single-writer is as easily composed in C++, and, encapsulated in a library, as easily maintained. Nothing about Rust makes this unavailable in C++. The library itself, then, becomes responsible for maintaining the discipline, not the compiler. But once encoded there, it is done. Rust's compiler provides safety advantages, but there is no need to exaggerate them. (Exaggeration is a liability to your language community.)
- adwn 6y ago
  > [...] if you wrap the semantics in a library, and use the library, you get the same reliability from it. Wrong. Rust offers more tools for checking that your library is used correctly than C++ does. First and foremost, the borrow checker – there is nothing comparable in C++, and it's a lot harder/impossible to statically prevent code from modifying shared data after a mutex has been unlocked, for example. > (This is an unpopular observation in certain places.) It is unpopular because it is factually incorrect.

signa11 6y ago

previously : https://news.ycombinator.com/item?id=25255113 https://news.ycombinator.com/item?id=25255113

speedgoose 6y ago
This has no comments though.

mehrdadn 6y ago

If you want to dig deeper, watch these videos: https://herbsutter.com/2013/02/11/atomic-weapons-the-c-memory-model-and-modern-hardware/ https://herbsutter.com/2013/02/11/atomic-weapons-the-c-memor...

sprachspiel 6y ago
Even after watching these videos and reading lots of articles on the topic, I still find the full C++ memory model extremely hard to understand. However, on x86 there are actually only a couple of things that one needs to understand to write correct lock free code. This is laid out in a blog post: https://databasearchitects.blogspot.com/2020/10/c-concurrency-model-on-x86-for-dummies.html https://databasearchitects.blogspot.com/2020/10/c-concurrenc...
- dragontamer 6y ago
  C++'s "seq_cst" model is simple. If you're having any issues understanding anything at all, just stick with seq_cst. If you want slightly better performance on some processors, you need to dip down into acquire-release. This 2nd memory model is faster because of the concept of half-barriers. Lets say you have: a(); b(); acquire_barrier(); // Half barrier c(); d(); e(); release_barrier(); // Half barrier f(); g(); The compiler, CPU, and cache is ALLOWED to rearrange the code into the following: acquire_barrier(); // Optimizer moved a() and b() from outside the barrier to inside the barrier a(); b(); d(); c(); e(); g(); f(); release_barrier(); // Optimizer moved g() and f() from outside the barrier to inside the barrier You're allowed to move optimizations "inside" towards the barrier, but you are not allowed to rearrange code "outside" of the half-barrier region. Because more optimizations are available (for the compiler, the CPU, or the caches), half-barriers execute slightly faster than full sequential consistency. ---------- Now that we've talked about things in the abstract, lets think about "actual" code. Lets say we have: int i = 0; // a(); i++; // b(); full_barrier(); // seq_cst barrier i+=2; // c(); i+=3; // d(); i+=4; // e(); full_barrier(); // seq_cst barrier i+=5; // f(); i+=6; // g(); As the optimizer, you're only allowed to optimize to... int i = 1; // a() and b() rearranged to the same line full_barrier(); // Not allowed to optimize past this line i+= 9; // c, d, and e rearranged full_barrier(); i+= 11; // f, g rearranged. Now lets do the same with half barriers: int i = 0; // a(); i++; // b(); acquire_barrier(); // acquire i+=2; // c(); i+=3; // d(); i+=4; // e(); release_barrier(); // release i+=5; // f(); i+=6; // g(); Because all code can be rearranged to the "inside" of the barrier, you can simply write: i = 21; Therefore, half-barriers are faster. ---------- Now instead of the compiler rearranging code: imagine the L1 cache is rearranging writes to memory. With full barriers, the L1 cache has to write: i = 1; full_barrier(); // Ensure all other cores see that i is now = 1; i = 10; // L1 cache allows CPU to do +2, +3, and +4 operations, but L1 "merges them together" and other cores do NOT see the +2, +3, or +4 operations full_barrier(); // L1 cache communicates to other cores that i = 10 now; i = 21; // L1 cache allows CPU to do +5 and +6 operations // Without a barrier, L1 cache doesn't need to tell anyone that i is 21 now. No communication is guaranteed. ---------- Similarly, with half-barriers instead, the L1 cache's communication to other cores only has to be: i = 21; // L1 cache can "lazily" inform other cores, allowing the CPU to perform i+=1, i+=2... i+=6. So for CPUs that implement half-barriers (like ARM), the L1 cache can communicate ever so slightly more efficiently, if the programmer specifies these barriers. ---------- Finally, you have "weak ordered atomics", which have no barriers involved at all. While the atomics are guaranteed to execute atomically, their order is completely unspecified. There's also consume / release barriers, which no one understands and no compiler implements. So ignore those. :-) They're trying to make consume/release easier to understand in a future standard... and I don't think they got all the "bugs" out of the consume/release standard yet. ------- EDIT: Now that I think of it, acquire_barriers / release_barriers are often baked into a load/store operation and are "relative" to a variable. So the above discussion is still inaccurate. Nonetheless, I think its a simplified discussion to kinda explain why these barriers exist and why programmers were driven to make a "more efficient barrier" mechanic.

fulafel 6y ago

Piggybacking this question for people interested in the topic: Which everyday high level data structures you use are built on lock-free implementations? Clojure's maps/vectors (which are persistent data structures) come to mind for me, for one.

forrestthewoods 6y ago
Almost zero. Queues or streams may have lockless properties. Or maybe not! For the most part concurrent, mutable access to a shared data structure is undesirable and to be avoided. If you find yourself wanting a lockless hashmap you’re going down the wrong path 99.9% of the time. There are always exceptions. But you better have a REALLY good reason why.
jeffreygoesto 6y ago
https://github.com/eclipse/iceoryx https://github.com/eclipse/iceoryx
bitcharmer 6y ago
SPSC (single producer single consumer) queues and ring buffers are used quite extensively in low-latency software engineering.
- jamesmunns 6y ago
  Yup! In Rust specifically, I've written bbqueue, which is a bipbuffer-inspired lock-free ring buffer, intended for embedded systems and DMA usage. https://github.com/jamesmunns/bbqueue https://github.com/jamesmunns/bbqueue It uses atomics (and Rust's borrow checker) heavily to safely guarantee lock free behavior, and works pretty darn quick.
  - caspper69 6y ago
    You reference a blog post on your Github (regarding the algo description). I believe the author of that blog (someone at Ferrous Systems) has a pretty significant misunderstanding of DMA and serial ports, which raises a whole host of other questions on down the chain <additional unnecessary comment removed>. edit: I know it's not cool to complain about downvotes, but this is a legitimate concern to raise for this poster. I am not attempting to denigrate anyone here.

runeks 6y ago

I appreciate learning more about what, exactly, ARM's "weaker memory model" constitutes. It's clearer to me after reading this article. I wonder how much the gain in performance of e.g. Apple's M1 chip, compared to an x86 CPU, can be attributed to this weaker constraint. Given that the M1 can outperform an x86 CPU even when emulating x86 code, perhaps it's not much. Also, I suspect programming languages that are immutable by default will gain a larger advantage using ARM's weaker memory model, as the compiler can more often safely let the CPU perform reordering (due to not having to wait for a mutable variable being updated until it can execute a subsequent line of code which depends on this updated variable).

saagarjha 6y ago
The M1 chip can do uncontended atomics almost "for free", and offers a mode where it firms up its memory ordering without much performance loss, so I am not actually sure how much this gets them.
- KMag 6y ago
  Well, it gets them enough that they bothered implementing all of the circuitry for both memory models and an extra bit of thread state to switch between them. I'm sure they did a bunch of simulation before going with that decision. I'm sure they did some simulations before going down that road and found that it was worth it vs. just going with a more strict x86-like memory model all the time.
  - cma 6y ago
    > I'm sure they did some simulations before going down that road and found that it was worth it vs. just going with a more strict x86-like memory model all the time. Or they didn't want developers to rely on it so they can remove it in the future when they deprecate x64 (they deprecated x86 so it is only a matter of time).
    - KMag 6y ago
      > Or they didn't want developers to rely on it If simulations show that it's not currently worth the effort, but they want to keep the option open, that implies that they believe some technological change in the future may make the relaxed memory model bear fruit. Actually, now that I think about it, another option is that the weaker memory model is more advantageous in lower power implementations, like iWatch, and preventing developers from relying on the stronger memory model available in M1 reduces the number of bugs in iWatch applications that share code with iPhone apps or OSX apps.

cesaref 6y ago

The most annoying aspect of lock free programming is the amount of 'roll your own' that goes on, and having to inspect this stuff to ensure it's got a chance of working on the platforms you care about. I totally get that this technique is inappropriate for many situations where a lock works well enough, but I work in a field (audio) where accidental use of locks and system calls is in general a larger problem than incorrect lock free code.

jcelerier 6y ago
Hm, in c++ there are a fair amount of battle-tested, permissively-licensed lockfree containers though I use https://github.com/cameron314/readerwriterqueue https://github.com/cameron314/readerwriterqueue and https://github.com/cameron314/concurrentqueue https://github.com/cameron314/concurrentqueue ; they deliver.
- scott_s 6y ago
  Yes, in addition to the atomics and memory ordering primitives added in the C++11 standard [1], I find the Boost lock-free structures quite reasonable [2]. (Yes, I'm aware some have an automatic aversion to Boost. But it is well-designed and I believe is a header-only library.) [1] https://en.cppreference.com/w/cpp/atomic https://en.cppreference.com/w/cpp/atomic [2] https://www.boost.org/doc/libs/1_74_0/doc/html/lockfree.html https://www.boost.org/doc/libs/1_74_0/doc/html/lockfree.html

bullen 6y ago

As long as this code runs fine on ARM we're going to be ok: http://move.rupy.se/file/atomic.txt http://move.rupy.se/file/atomic.txt

ncmncm 6y ago

The importance and value of lock-free programming is massively overrated. I routinely improve performance and also reliability of systems by deleting lock-free queues. The secret to both is reduced coupling, which lock-free methods do nothing to help with. Atomic operations invoke hardware mechanisms that, at base, are hardly different from locks. While they won't deadlock by themselves, they are so hard to get right that failures equally as bad as deadlocking are hard to avoid. So, replace threads with separate processes that communicate via ring buffers, and batch work to make interaction less frequent. With interaction infrequent enough, time spent synchronizing, when you actually do it, becomes negligible.

KMag 6y ago
> So, replace threads with separate processes that communicate via ring buffers ... but those ringbuffers you're using presumably have a lockfree fast path with a futex or pthread mutex slow path to prevent the consumer from busy-waiting, so you're still taking advantage of lockfree data structures.
- ncmncm 6y ago
  You may presume so, but you would be wrong. They are technically (also) lock-free, so require atomic operations when announcing additions, but being written by only one process, ownership of cache lines never changes, so hardware locks are not engaged. Readers do poll, and sleep as long as the tolerated latency when nothing new is found. Writers batch additions, and announce new entries only just so frequently.
  - KMag 6y ago
    Interesting, though the overhead of nanosleep vs. futex wait with non-NULL timeout should be dwarfed by the context switch. I can see where if you have extreme latency and/or throughput constraints on the writer side of the ring buffer, you couldn't afford the extra atomic read and occasional futex wake on the writer side to wake the consumer. > but being written by only one process, ownership of cache lines never changes, so hardware locks are not engaged. Which cache coherency protocol are you referring to where cache lines are "locked"? I'm aware that early multiprocessor systems locked the whole memory bus for atomic operations, but my understanding is that most modern processors use advanced variants on the MESI protocol[0]. In the MOESI variant, an atomic write (or any write, for that matter) would put the cache line in the O state in the writing core's cache. If we had to label cache line states as either "locked" or "unlocked", the M, O, and E states would be "locked", and S and I would be "unlocked". Your knowledge of cache coherency protocols is probably much better than mine, so I'm probably just misinterpreting your shorthand jargon for "locked" cache lines. By "hardware locks are not engaged" do you just mean that the O state doesn't ping-pong between cores? [0] http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2...

andy_threos_io 6y ago

Lock-Free programming is essential in high performance networking (10G+ network connections) and data communications. Most of the implementation are using ringbuffers. There can be multiple producer consumer implementation as well. But it's not a real issue for the new M1 minis as its network is down to 1Gbit (from the previous mini 10G).

CharlesW 6y ago
> But it's not a real issue for the new M1 minis as its network is down to 1Gbit (from the previous mini 10G). FWIW, that's just the built-in port. 10G adapters will do 900MB/s. https://www.owcdigital.com/products/thunderbolt-3-10g-ethernet-adapter https://www.owcdigital.com/products/thunderbolt-3-10g-ethern...

xmodem 6y ago

Aside - calling it now - but the M1's x86 memory model mode is a temporary thing that'll go away in a few years along with Rosetta 2 once Apple is happy with the level of universal binary support.

gwbas1c 6y ago
> in a few years Pure speculation: I suspect that Apple will support x86 longer than it supported PPC. Why? The macOS platform is "older" now and more popular than when PPC was around. There's more old applications laying around, unmaintained. Also, don't forget that "windows compatibility" was a huge Mac selling point when they switched to x86. So, I suspect a minimum of 8 years support, but possibly indefinitely if Windows can't make the jump to ARM. Again, pure speculation, but what will be the deciding factor is if x86 virtualization on ARM Mac ever becomes a thing. (And I hope it does!)
- xmodem 6y ago
  > I suspect that Apple will support x86 longer than it supported PPC. Totally agree - I was surprised how quickly they dropped PPC support. The install base is so much larger now, and hardware refresh cycles so much longer that it'll be necessary. Hell, they've said this transition will take 2 years - the Intel transition took them a year to go from no Intel macs to all Intel macs. > So, I suspect a minimum of 8 years support, Not gonna happen. The Apple of today does not care about old unmaintained applications and definitely does not want to make computers for people to run Windows on.
  - gwbas1c 6y ago
    > The Apple of today does not care about old unmaintained applications The Apple of today is not the Apple of tomorrow. Considering how awesome the M1 Macs sound; if Mac reaches a high marketshare, it might be required.
ant6n 6y ago
I understand M1 has a special mode that implements the x86 memory model, which aids in Emulation. Apparently qualcom doesn’t have that, so x86 on Arm Windows is slow, being littered with memory barriers. Couldn’t one just use userthreads in an emulator and ignore all these memory issues? Sure that would mean every emulated process is running on one core, but as long as blocking io is implemented properly, how bad can that be? (It would be like having a single core for the emulated process)

alvarelle 6y ago

> ... std::atomic<bool>. This tells the compiler not to elide reads and writes of this variable, ... If I'm not mistaken, this is not true. The compiler is still allowed to elide reads and writes on atomic variables. (For example merge two consecutive writes, or remove unused reads)

gpderetta 6y ago
Correct. See "N4455 No Sane Compiler Would Optimize Atomics" [1]. The first sentence of that paper is (spoiler allert) a laconic "false". [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4455.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n445...
brucedawson 6y ago
Updated. Thanks for the correction.

marcan_42 6y ago

This reminds me of some lock-free code I fixed recently (by introducing a very peculiar kind of lock): https://github.com/Ardour/ardour/blob/master/libs/pbd/pbd/rcu.h https://github.com/Ardour/ardour/blob/master/libs/pbd/pbd/rc... The goal of the code is to allow a producer thread to update a pointer to an object in memory, which may be used lazily by consumer threads. Consumers are allowed to use stale versions of the object, but must not see inconsistent state. Obsolete objects must eventually be freed, but only after all consumers are done using them. And here's the catch: consumers are real-time code, so they must never block on a lock, nor are they allowed to free nor allocate memory on their own. The design is based around Boost's shared_ptr, so that had to stay. But the original code was subtly broken: the object is passed around by passing a pointer to a shared_ptr (so double indirection there) which gets cloned, but there was a race condition where the original shared_ptr might be freed by the producer while the consumer is in the process of cloning it. My solution ended up being to introduce a "lopsided spinlock". Consumers aren't allowed to block, but producers are. So consumers can locklessly signal, via an atomic variable, that they are currently inside their critical section. Then the producer can atomically (locklessly) swap the pointer at any time, but must spin (is this a half-lock?) until no consumers are in the critical section before freeing the old object. This ensures that any users of the old pointer have completed their clone of the shared_ptr, and therefore freeing the old one will no longer cause a use-after-free. Finally, the producer holds on to a reference to the object until it can prove that no consumers remain, to guarantee that the memory deallocation always happens in producer context. shared_ptr then ensures that the underlying object lives on until it is no longer needed. It's kind of weird to see a half-spinlock like this, where one side has a "critical section" with no actual locking, and the other side waits for a "lock" to be released but then doesn't actually lock anything itself. But if you follow the sequence of operations, it all works out and is correct (as far as I can tell). For various reasons this code has to build with older compilers, hence can't use C++ atomics. That's why it's using glib ones. (Note: I'm not 100% sure there are no hidden allocations breaking the realtime requirement on the reader side; I went into this codebase to fix the race condition, but I haven't attempted to prove that the realtime requirement was properly respected in the original code; you'd have to carefully look at what shared_ptr does behind the scenes)

gpderetta 6y ago

jnwatson 6y ago

This is common knowledge in embedded circles, where weak memory models are the norm. This article doesn't address a different kind of memory weakness in some ARM implementations (and I presume other architectures) that you can run into when sharing memory between processes. The data cache is virtually tagged, virtually indexed, which means that the cache is keyed with the domain (essentially the process number) + the virtual address. This means that the MMU doesn't have to be consulted for cache lookups, however, if you have two different processes mapped into the same physical memory, the writing process must execute a flush instruction, and the reading process must execute an invalidate instruction.

Arelius 6y ago
Ohh, Thanks! I had never heard about ARM's cache being tagged like that. Do you have any recommended reading?

JoeAltmaier 6y ago

Very educational. I take exception with the common assertion that 'code is broken' if it doesn't work everywhere for every architecture. Code deployed for a particular purpose on a particular machine with a particular toolchain can work great and be 'correct' for that environment. I work in such environments all the time. And taking the time/performance hit seeking ill-conceived perfection wastes the clients time and money. But for the vast majority of cloud-deployed or open-source prjects, its certainly wise to err on the side of 'perfect'.

brucedawson 6y ago
When I said "that code was probably broken already" I meant that while the code might currently be working it could suddenly stop working if you upgrade your compiler. Yes, you are free to take that risk, but relying on things not guaranteed by the language is dangerous.

jhallenworld 6y ago

I thought barriers were required on x86 also. There are a few cases where ordering is not guaranteed. [Also the consumer should have a barrier between the test and the data read.] https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/ https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fe... The thing that's nice about x86 is that DMA is cache coherent- this is true for backwards compatibility with very old hardware.

dragontamer 6y ago
At the assembly level, barriers are not required in many cases because x86 have total-store ordering. There are a few cases where memory-barriers are still needed... but not nearly as many examples as in ARM-world. At the C / C++ level, barriers are required because almost all compilers rearrange code in the name of optimization (especially as you go from -O to -O1, to -O2, to -O3... more aggressive rearrangements happen). The optimizer needs to know "not" to rearrange some code, so a compiler barrier is needed. --------- It turns out that a compiler barrier (hey compiler: do not rearrange this read/write I'm specifying) is identical in concept to a CPU-memory barrier on a weak-ordered system (hey CPU: don't reorder this read/write I'm specifying).

vbezhenar 6y ago

What I'm afraid is with the introduction of ARM desktops, there will be subtle bugs which did not manifest on x86. Those bugs are hard to find in old legacy multi-million LoC codebase with lots of spaghetti code nobody bothered to refactor, so those bugs will haunt users for years. That's why I'm reluctant to move to this architecture at least for a few years, even if it's superior in theory. Thankfully ARM phones were a thing for a lot of time, so many libraries should work well.

mlindner 6y ago

This guy is a member of Antifa. I'm not a fan of people reposting articles by known left-wing terrorist organizations on hacker news.