8 ms·

What every systems programmer should know about lockless concurrency [pdf]

419 points by sidcool 9y ago

jeff571 9y ago
Keep in mind lockless algorithms are not necessarily more scalable than lock-based algorithms, usually have higher constant overheads, and are significantly easier to get wrong. However, this post is, in part, about how to implement locks.
- taneq 9y ago
  > However, this post is, in part, about how to implement locks. I haven't read the article in-depth but yeah, it seems like it maybe would have been better titled "What every C++ systems programmer should know about std::atomic". Which is still cool but from the title I was expecting some fancy voodoo algorithms for threadsafe non-locking FIFO queues or something.
  - buserror 9y ago
    Completely agree with this, the topic is much wider than the meat of the paper. A bit of a clickbait here.
  - banachtarski 9y ago
    I think it's meant to be pretty fundamental. It's not supposed to include "voodoo algorithms" because it literally says "what every systems programmer should know...". The voodoo algorithm is a voodoo algorithm because not everyone needs to know it. In contrast, a mutex and all of that stuff is a consequence of how memory sequencing on a CPU works. If you understand those concepts, the rest is a hop, skip, and a jump away.
    - taneq 9y ago
      I guess my beef was mostly in response to the word "lockless", which I'd hoped meant "not using any wait-for-other-thread type semantics" but in this context seems to mean "implementing locking without using OS-provided locking primitives, although standard library is fine." I was hoping that there was some cool new trick I'd missed or fundamentally different way to do concurrency than locking. I get disappointed easily in cases like this. :/
  - johndubchak 9y ago
    I think that might be what parts of this upcoming release might contain: https://www.amazon.com/C-Concurrency-Action-Anthony-Williams/dp/1617294691/ref=sr_1_2?ie=UTF8&qid=1509644435&sr=8-2&keywords=Anthony+Williams+C%2B%2B+Concurrency+in+Action https://www.amazon.com/C-Concurrency-Action-Anthony-Williams...
  - Animats 9y ago
    Me too. If you can do lockless add-to-queue and remove-from-queue, that's valuable. It's hard to get that right, especially on non x86/amd64 platforms. Every network packet, and often every interrupt, goes through a queue operation like that. Not stalling the other CPUs on each interrupt is important.
- banachtarski 9y ago
  I think it's worth thinking in terms of the probability of contention per cycle. If the odds of contention is very low, lock-free will be much better (imagine accessing a shared data structure which is vast compared to the range of usage in a typical use). Also, I think it's worth noting that it's really not that much more complicated than a simple mutex if you use the default sequential consistency memory order on an atomic. When you start attempting to optimize around certain patterns using the weaker memory orders, yea, things get a lot tougher.
  - yason 9y ago
    If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer. I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.
    - banachtarski 9y ago
      Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.
      - gpderetta 9y ago
        Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
- sdenton4 9y ago
  As the text puts it: "And as always, consider the tradeoffs you make between complexity and performance. Lockless programming is a perilous activity with a proud tradition of code that is ever so subtly wrong."
- saas_co_de 9y ago
  Lock-free using CAS type operations looks good in theory but having to do a cache flush for every atomic operation really bogs things down when you get into complex algorithms so the simple lock ends up being cheaper. An alternative lock-free approach is to segmented memory between threads and then coordinate between threads using messages passed with ring buffers. This can be done entirely without atomic operations but hits other scaling problems and is also extremely difficult to implement so probably not widely applicable.
  - gpderetta 9y ago
    CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).
    - dragontamer 9y ago
      > CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Perhaps "Cache Flush" is the wrong word, but as long as cores are forced to communicate, you're going to get a performance penalty. I know when you do a simple atomic_increment on x86_64 platforms, things can be 2x slower at a minimum than a non-atomic increment. "Cache Coherence" simply means that the CPU handles all of those edge cases for you. But it still needs to be handled, and that entails a performance penalty. If you have a 4-core / 8-thread machine (Like a recent Intel i7), its faster to have 8-Non Atomic counters that are added up at the end... rather than to have 1-atomic counter with 8-threads doing atomic-increment on it. ---------------- Any core that modifies a memory location invalidates the cache for all other cores. (ie: Core 1 does atomic_inc(x), implies that Core2/Core3/Core4 all have an invalid value of "x". So atomic_inc(x) causes a cache-flush on Core2/Core3/Core4) Again, I'm not an expert, but that's my understanding of how modern systems work. ------- I looked up the Intel Architecture Manual, and they have the following table: https://imgur.com/uesh8co https://imgur.com/uesh8co If the data is in another core's L1 cache, the latency increases dramatically, especially on a "Dirty Hit". (ie: Core1 is trying to read "x", but Core3 is telling the other cores that "x" has changed) In effect, its more efficient for an Intel CPU to access something from L3 cache than for it to access a "Dirty" value from another core. Heck, based on these numbers, even a "Clean" hit is more costly than using the L3 cache!
- deleted 9y ago
  [deleted]
johnbender 9y ago
It seems like weak memory models get short shrift, but if you're going to program without locks it's semi-important to understand what information one gets when examining a read-write pair. It's true that (as implied by the article) you can probably get by with just studying/programming with the C/C++ [1][2] "atomic" memory access types and letting the compiler enforce those semantics, though the reasoning behind a lot of these memory orderings is lost without understanding the motivation/arch. models behind them. If you're interested in the C/C++ memory models there's active research into specifying them without bad behavior (thin-air reads [3]). Recent results include a semantics that makes value promises and requires a justifying execution [4] which is not totally dissimilar from those required by the official java memory model [5]. 1. http://en.cppreference.com/w/cpp/atomic/atomic http://en.cppreference.com/w/cpp/atomic/atomic 2. http://en.cppreference.com/w/c/atomic http://en.cppreference.com/w/c/atomic 3. http://www.cl.cam.ac.uk/~pes20/cpp/notes42.html http://www.cl.cam.ac.uk/~pes20/cpp/notes42.html 4. https://people.mpi-sws.org/~dreyer/papers/promising/paper.pdf https://people.mpi-sws.org/~dreyer/papers/promising/paper.pd... 5. http://rsim.cs.uiuc.edu/Pubs/popl05.pdf http://rsim.cs.uiuc.edu/Pubs/popl05.pdf
- bshanks 9y ago
  I wonder how the memory model in https://people.mpi-sws.org/~dreyer/papers/promising/paper.pdf https://people.mpi-sws.org/~dreyer/papers/promising/paper.pd... compares to the WMM and WMM-S memory models given in https://arxiv.org/pdf/1707.05923.pdf https://arxiv.org/pdf/1707.05923.pdf ; and if there are other research memory models out there that should also be considered?
  - johnbender 9y ago
    These papers take forever to read (take it from me, I am doing research in this area, in particular proofs of correctness for lock free programs). I recommend focusing on the C/C++ ones if only for the practical value. As for comparison, the C/C++ memory model is more general and is operational. It is also formalized in coq and has some good theorems (data race free sequential consistency being the most obvious). The RISC memory model is axiomatic and follows the standard axiomatic approach adopted for many other memory models like Java and the current C/C++ standard. That's not a dig, they just don't care as much about rigor. Axiomatic models consider the every possible execution and then weed out bad ones, where as the operational semantics defines the set of all possible executions using a transition relation. If you're into math you might see these vaguely as extensional and intensional respectively.
dragontamer 9y ago
Lockless concurrency was always an "interesting" subject to me, but I never thought it was practical for me to use them. Mostly because multithreaded programming generally has easier-to-use and higher-level constructs (ie: Reader-Writer Queues already written) that can be used. However, I've recently grown to respect Lockless Programming as I have begun to experiment with GPU programming. OpenCL doesn't give you Mutexes, and indeed, you really shouldn't "lock" an instruction pointer in a GPU ever. (On AMD systems, a singular instruction pointer runs 64 different "threads". So if one of these "threads" lock up, ALL 64 of them lock. This "Single Instruction, Multiple Data" is the key to why GPUs have so many "cores") As such, the only practical way to write decently high-performance code with concurrency on a GPU is through Atomics (ie: Compare and Swap). Which of course, requires an understanding of memory barriers as well.
- blattimwind 9y ago
  > Single Instruction, Multiple Data *multiple threads (preferably both, in the case of GPUs, but what you described is SIMT)
  - djmips 9y ago
    Some would say SIMT is a marketing term but at the end of the day SIMT is a subset of SIMD
  - dragontamer 9y ago
    I know its what NVidia calls SIMT, but its what AMD calls SIMD. ¯\_(ツ)_/¯ NVidia is somewhat correct to call their "SIMT" concept something new, because Intel's original SIMD implementations (MMX and SSE) couldn't do the thread-divergence thing very easily (AVX 512 adds a few more features to make thread-divergence easier to handle at the CPU level). But as far as I can tell, AMD GPUs can do thread-divergence, "constant broadcasts", and all that jazz too, but AMD still calls it SIMD.
rpo1991 9y ago
Keep in mind lockless algorithms are not necessarily more scalable than lock-based algorithms, usually have higher constant overheads, and are significantly easier to get wrong. However, this post is, in part, about how to implement locks.
xyzzy_plugh 9y ago
I have always found that the biggest hurdle in understanding concurrency amongst my peers is learning how memory barriers work.
- gpderetta 9y ago
  Although I did understand memory barriers early while playing with lock free concurrency, I didn't really grok them until much later. I had initially a very hard time, while thinking in term of reordering, in figuring out which barrier goes where. But the C++ memory model (and the acquire/release consistency model in general), which does away with explicit barriers but attach synchronization behaviour to store->load edges [1], instead clicked almost immediately and in retrospect made it easier for me to describe an algorithm in the more informal reordering based model. [1] barriers are available, but are discouraged and are still defined in term of acquire/release and sequential consistency.
- ohazi 9y ago
  One reason for this is that for the longest time they weren't really available in a cross platform way. I'd learn about e.g. mutexes in a computer architecture class, and then I could immediately go use them with boost or pthread or whatever. I'd also learn about atomic operations, atomic cas, and memory barriers, but short of some very specific game libraries with weird macros for this, I couldn't find them anywhere. It seemed like we were expected to sprinkle volatile everywhere, remember rules about unaligned access, and write our own platform specific macros for memory barriers. If you're primarily testing your code on an x86 laptop, it's very difficult to be confident that you're doing it correctly.
  - exDM69 9y ago
    > I'd also learn about atomic operations, atomic cas, and memory barriers, but short of some very specific game libraries with weird macros for this, I couldn't find them anywhere. How come? These days atomic ops are included in C and C++ standard library. And there are atomic operations for every important compiler out there and if you need portability across compilers (without relying on new C/C++ standards), there are portability libraries (e.g. boost). These have existed for a long time E.g. here are GCC's atomics: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins... > It seemed like we were expected to sprinkle volatile everywhere, remember rules about unaligned access, and write our own platform specific macros for memory barriers. Unless you're using Java, "volatile" is not useful for concurrent programming. When you see volatile keyword in C code, it's almost always wrong or there for a legacy reason. Sounds like your computer architecture classes were not up to date or very well taught.
kkyn 9y ago
It seems like weak memory models get short shrift, but if you're going to program without locks it's semi-important to understand what information one gets when examining a read-write pair.
sigu1 9y ago
I have always found that the biggest hurdle in
signa11 9y ago
imho, memory-barriers.txt, in linux kernel documentation should be a required grokking before getting into lockless stuff.
- albertzeyer 9y ago
  Link: https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt
  - maxxxxx 9y ago
    I wish I could write that well :(. This is better than most write ups with fancy graphics.
codepie 9y ago
The thread example given in article is only limited to a single writer and multiple readers. Things get interesting when you want to have lock free concurrency with multiple readers and writers. One of the famous techniques is using software transactional memory (https://en.m.wikipedia.org/wiki/Software_transactional_memory https://en.m.wikipedia.org/wiki/Software_transactional_memor...). But it hasn't really caught up in the industry and it still exists within academia. The existing lock free concurrency solutions are not mature enough to replace locks. I like this analogy of what garbage collection is to memory is STM is to memory(https://homes.cs.washington.edu/~djg/papers/analogy_oopsla07.pdf https://homes.cs.washington.edu/~djg/papers/analogy_oopsla07...).
- signa11 9y ago
  > ... But it hasn't really caught up in the industry and it still exists within academia... acm had this article a while back: http://pages.cs.wisc.edu/~cain/pubs/cascaval_cacm08.pdf http://pages.cs.wisc.edu/~cain/pubs/cascaval_cacm08.pdf may you please comment on that ? thank you !
- gpderetta 9y ago
  There are lock free algos that support multiple writers. The reason they are sometime avoided is that, in addition of being often more complicated, they usually scale badly; that's inherently true with any algorithm violating the single writer principle, not just with lock-free algos; that's true with STM as well.
- saas_co_de 9y ago
  Intel has TSX https://software.intel.com/en-us/node/524022 https://software.intel.com/en-us/node/524022 I have never used it though and I am not sure who does.
  - convolvatron 9y ago
    I wish this were more useful. The real sticking point for me is that you can run out of transaction contexts - which means you have to have a full software implementation as backup. the only case I can think of where I would actually use the thing is if I already had an STM runtime and I wanted to cut down some of the constant time overheads. the other problematic aspect s that transaction scheduler policy is pretty important for contended performance and as part of the broader system design. in this case you have to live with whatever intel gives you
JohnHam 9y ago
I have always found that the biggest hurdle in understanding concurrency
amelius 9y ago
How well does Rust support these concepts?
- pjmlp 9y ago
  As far as I know Rust doesn't have a memory model fully defined yet, but their type system already helps a lot. https://github.com/nikomatsakis/rust-memory-model https://github.com/nikomatsakis/rust-memory-model A bit old, https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.html https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.h...
  - steveklabnik 9y ago
    We don't, but there's been a ton of work; http://plv.mpi-sws.org/rustbelt/ http://plv.mpi-sws.org/rustbelt/ For this kind of thing we mostly say "we defer to the C++ memory model" at the moment.
Girlang 9y ago
No locks in Erlang.
srcmap 9y ago
I implemented a lockless IPC, DIPC - Interprocess Communication and Distributed IPC library in 2000-2002 time frame. The library is used in vxWorks, QNX, Linux (both kernel and user space.) and tested heavily on Xeon SMP 1-2GHz CPU at that time. For memory management, it was implemented in C++ and the message (Memory) Alloc/Free calls were all lockless. One can allocated a memory from kernel and send it as msg to user space and use it there without copy. The limitation is that the max allows messages are statically pre-allocated for the system. The library manages the pre-allocated pools of various sizes with lockless APIs. When the pools runs out, the API returns error. The only primitive the library depended on was Atomic_Inc/Dec - absolutely no mutex, spin locks in the non-blocking API code path, etc. The library was designed to support HA (High available ) TCP/IP stack and routing protocols. The APIs was not the complex. The most complicate part was the regress testing code and the diagnostic code. The API was used by team of 100+ developers. I need help them to debug complex IPC/DIPC issues - and prove to them when the error return, it was not the library/API issue. There was a trace mechanism that track all the messages went thru the system(s). The trace system was also completely non-blocking and lockless, worked both in kernel and user space. All context switches in Linux Kernel was tracked - very similar to FTRACE in kernel today. I hacked the kernel/bios to preserve the DRAM content part of the trace system during warmboot. This way, I can recovered all the messages, last context switched info even for kernel hang, crash issue for postmortem. The trace system used rdtsc for time stamping had 0.5 nano-seconds resolution on 2Ghz Xeon CPU. The API/Library worked fine. The overall system complexities was a big issue. We can demo TCP/IP, BGP and various routing protocols that did HA Switch over and In Service OS upgrade. But only as demo - and after switch over the state syncing took a long time and reliability of HA TCP/IP and routing protocol was an big issue. Base on the lesson learned from that project - I went on and coded a different Application level HA system. That system based everything on top of standard Linux API/utilities. That works much better and the HA port of the SW took only 1 dev (me) 3 weeks to code. It supported in service SW (include Linux kernel) upgrade, HW/SW fault detected and automatically switch over. It was deployed in Comcast. Fault detection took < 50 ms and switch over is almost instance. Full state sync was done with wget over management Ethernet interface and always took < 1 second. All incremental states update were done over UDP and took 1 pkt. The funny Biz/$ outcomes from these two projects: The first one: startup sold only one HA router for $200k and burned 100M+ of VC $ but sold to Nokia for $400+Mil. I was able to paid off my mortgage with the options from that company - Not FU money but ok outcome. The 2nd one: The startup sold $40M of products for $60K from that project to Comcast and various Cable companies at 60% margin. That product (with 19+ FPGA) was created/code/developed with ~8 HW/FW/SW engineers (including the 2 founders). The VC got "a seasoned CEO" - managed to raise a few more rounds, kick out the founders (MIT PhD), hired 160+ people and ran the company to the ground.
SEJeff 9y ago
Another one (posted by me) on "Fear and Loathing in Lock Free Programming": https://news.ycombinator.com/item?id=15530032 https://news.ycombinator.com/item?id=15530032
ozfive 9y ago
This is incredibly well thought out and written. I felt like a friend was telling me about something that we would only understand. Matt Kline, bravo.

419 points by sidcool 9y ago

Keep in mind lockless algorithms are not necessarily more scalable than lock-based algorithms, usually have higher constant overheads, and are significantly easier to get wrong. However, this post is, in part, about how to implement locks.

taneq 9y ago
> However, this post is, in part, about how to implement locks. I haven't read the article in-depth but yeah, it seems like it maybe would have been better titled "What every C++ systems programmer should know about std::atomic". Which is still cool but from the title I was expecting some fancy voodoo algorithms for threadsafe non-locking FIFO queues or something.
- buserror 9y ago
  Completely agree with this, the topic is much wider than the meat of the paper. A bit of a clickbait here.
- banachtarski 9y ago
  I think it's meant to be pretty fundamental. It's not supposed to include "voodoo algorithms" because it literally says "what every systems programmer should know...". The voodoo algorithm is a voodoo algorithm because not everyone needs to know it. In contrast, a mutex and all of that stuff is a consequence of how memory sequencing on a CPU works. If you understand those concepts, the rest is a hop, skip, and a jump away.
  - taneq 9y ago
    I guess my beef was mostly in response to the word "lockless", which I'd hoped meant "not using any wait-for-other-thread type semantics" but in this context seems to mean "implementing locking without using OS-provided locking primitives, although standard library is fine." I was hoping that there was some cool new trick I'd missed or fundamentally different way to do concurrency than locking. I get disappointed easily in cases like this. :/
- johndubchak 9y ago
  I think that might be what parts of this upcoming release might contain: https://www.amazon.com/C-Concurrency-Action-Anthony-Williams/dp/1617294691/ref=sr_1_2?ie=UTF8&qid=1509644435&sr=8-2&keywords=Anthony+Williams+C%2B%2B+Concurrency+in+Action https://www.amazon.com/C-Concurrency-Action-Anthony-Williams...
- Animats 9y ago
  Me too. If you can do lockless add-to-queue and remove-from-queue, that's valuable. It's hard to get that right, especially on non x86/amd64 platforms. Every network packet, and often every interrupt, goes through a queue operation like that. Not stalling the other CPUs on each interrupt is important.
banachtarski 9y ago
I think it's worth thinking in terms of the probability of contention per cycle. If the odds of contention is very low, lock-free will be much better (imagine accessing a shared data structure which is vast compared to the range of usage in a typical use). Also, I think it's worth noting that it's really not that much more complicated than a simple mutex if you use the default sequential consistency memory order on an atomic. When you start attempting to optimize around certain patterns using the weaker memory orders, yea, things get a lot tougher.
- yason 9y ago
  If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer. I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.
  - banachtarski 9y ago
    Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.
    - gpderetta 9y ago
      Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
sdenton4 9y ago
As the text puts it: "And as always, consider the tradeoffs you make between complexity and performance. Lockless programming is a perilous activity with a proud tradition of code that is ever so subtly wrong."
saas_co_de 9y ago
Lock-free using CAS type operations looks good in theory but having to do a cache flush for every atomic operation really bogs things down when you get into complex algorithms so the simple lock ends up being cheaper. An alternative lock-free approach is to segmented memory between threads and then coordinate between threads using messages passed with ring buffers. This can be done entirely without atomic operations but hits other scaling problems and is also extremely difficult to implement so probably not widely applicable.
- gpderetta 9y ago
  CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).
  - dragontamer 9y ago
    > CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Perhaps "Cache Flush" is the wrong word, but as long as cores are forced to communicate, you're going to get a performance penalty. I know when you do a simple atomic_increment on x86_64 platforms, things can be 2x slower at a minimum than a non-atomic increment. "Cache Coherence" simply means that the CPU handles all of those edge cases for you. But it still needs to be handled, and that entails a performance penalty. If you have a 4-core / 8-thread machine (Like a recent Intel i7), its faster to have 8-Non Atomic counters that are added up at the end... rather than to have 1-atomic counter with 8-threads doing atomic-increment on it. ---------------- Any core that modifies a memory location invalidates the cache for all other cores. (ie: Core 1 does atomic_inc(x), implies that Core2/Core3/Core4 all have an invalid value of "x". So atomic_inc(x) causes a cache-flush on Core2/Core3/Core4) Again, I'm not an expert, but that's my understanding of how modern systems work. ------- I looked up the Intel Architecture Manual, and they have the following table: https://imgur.com/uesh8co https://imgur.com/uesh8co If the data is in another core's L1 cache, the latency increases dramatically, especially on a "Dirty Hit". (ie: Core1 is trying to read "x", but Core3 is telling the other cores that "x" has changed) In effect, its more efficient for an Intel CPU to access something from L3 cache than for it to access a "Dirty" value from another core. Heck, based on these numbers, even a "Clean" hit is more costly than using the L3 cache!
deleted 9y ago
[deleted]

johnbender 9y ago

It seems like weak memory models get short shrift, but if you're going to program without locks it's semi-important to understand what information one gets when examining a read-write pair. It's true that (as implied by the article) you can probably get by with just studying/programming with the C/C++ [1][2] "atomic" memory access types and letting the compiler enforce those semantics, though the reasoning behind a lot of these memory orderings is lost without understanding the motivation/arch. models behind them. If you're interested in the C/C++ memory models there's active research into specifying them without bad behavior (thin-air reads [3]). Recent results include a semantics that makes value promises and requires a justifying execution [4] which is not totally dissimilar from those required by the official java memory model [5]. 1. http://en.cppreference.com/w/cpp/atomic/atomic http://en.cppreference.com/w/cpp/atomic/atomic 2. http://en.cppreference.com/w/c/atomic http://en.cppreference.com/w/c/atomic 3. http://www.cl.cam.ac.uk/~pes20/cpp/notes42.html http://www.cl.cam.ac.uk/~pes20/cpp/notes42.html 4. https://people.mpi-sws.org/~dreyer/papers/promising/paper.pdf https://people.mpi-sws.org/~dreyer/papers/promising/paper.pd... 5. http://rsim.cs.uiuc.edu/Pubs/popl05.pdf http://rsim.cs.uiuc.edu/Pubs/popl05.pdf

bshanks 9y ago
I wonder how the memory model in https://people.mpi-sws.org/~dreyer/papers/promising/paper.pdf https://people.mpi-sws.org/~dreyer/papers/promising/paper.pd... compares to the WMM and WMM-S memory models given in https://arxiv.org/pdf/1707.05923.pdf https://arxiv.org/pdf/1707.05923.pdf ; and if there are other research memory models out there that should also be considered?
- johnbender 9y ago
  These papers take forever to read (take it from me, I am doing research in this area, in particular proofs of correctness for lock free programs). I recommend focusing on the C/C++ ones if only for the practical value. As for comparison, the C/C++ memory model is more general and is operational. It is also formalized in coq and has some good theorems (data race free sequential consistency being the most obvious). The RISC memory model is axiomatic and follows the standard axiomatic approach adopted for many other memory models like Java and the current C/C++ standard. That's not a dig, they just don't care as much about rigor. Axiomatic models consider the every possible execution and then weed out bad ones, where as the operational semantics defines the set of all possible executions using a transition relation. If you're into math you might see these vaguely as extensional and intensional respectively.

dragontamer 9y ago

Lockless concurrency was always an "interesting" subject to me, but I never thought it was practical for me to use them. Mostly because multithreaded programming generally has easier-to-use and higher-level constructs (ie: Reader-Writer Queues already written) that can be used. However, I've recently grown to respect Lockless Programming as I have begun to experiment with GPU programming. OpenCL doesn't give you Mutexes, and indeed, you really shouldn't "lock" an instruction pointer in a GPU ever. (On AMD systems, a singular instruction pointer runs 64 different "threads". So if one of these "threads" lock up, ALL 64 of them lock. This "Single Instruction, Multiple Data" is the key to why GPUs have so many "cores") As such, the only practical way to write decently high-performance code with concurrency on a GPU is through Atomics (ie: Compare and Swap). Which of course, requires an understanding of memory barriers as well.

blattimwind 9y ago
> Single Instruction, Multiple Data *multiple threads (preferably both, in the case of GPUs, but what you described is SIMT)
- djmips 9y ago
  Some would say SIMT is a marketing term but at the end of the day SIMT is a subset of SIMD
- dragontamer 9y ago
  I know its what NVidia calls SIMT, but its what AMD calls SIMD. ¯\_(ツ)_/¯ NVidia is somewhat correct to call their "SIMT" concept something new, because Intel's original SIMD implementations (MMX and SSE) couldn't do the thread-divergence thing very easily (AVX 512 adds a few more features to make thread-divergence easier to handle at the CPU level). But as far as I can tell, AMD GPUs can do thread-divergence, "constant broadcasts", and all that jazz too, but AMD still calls it SIMD.

rpo1991 9y ago

xyzzy_plugh 9y ago

I have always found that the biggest hurdle in understanding concurrency amongst my peers is learning how memory barriers work.

gpderetta 9y ago
Although I did understand memory barriers early while playing with lock free concurrency, I didn't really grok them until much later. I had initially a very hard time, while thinking in term of reordering, in figuring out which barrier goes where. But the C++ memory model (and the acquire/release consistency model in general), which does away with explicit barriers but attach synchronization behaviour to store->load edges [1], instead clicked almost immediately and in retrospect made it easier for me to describe an algorithm in the more informal reordering based model. [1] barriers are available, but are discouraged and are still defined in term of acquire/release and sequential consistency.
ohazi 9y ago
One reason for this is that for the longest time they weren't really available in a cross platform way. I'd learn about e.g. mutexes in a computer architecture class, and then I could immediately go use them with boost or pthread or whatever. I'd also learn about atomic operations, atomic cas, and memory barriers, but short of some very specific game libraries with weird macros for this, I couldn't find them anywhere. It seemed like we were expected to sprinkle volatile everywhere, remember rules about unaligned access, and write our own platform specific macros for memory barriers. If you're primarily testing your code on an x86 laptop, it's very difficult to be confident that you're doing it correctly.
- exDM69 9y ago
  > I'd also learn about atomic operations, atomic cas, and memory barriers, but short of some very specific game libraries with weird macros for this, I couldn't find them anywhere. How come? These days atomic ops are included in C and C++ standard library. And there are atomic operations for every important compiler out there and if you need portability across compilers (without relying on new C/C++ standards), there are portability libraries (e.g. boost). These have existed for a long time E.g. here are GCC's atomics: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins... > It seemed like we were expected to sprinkle volatile everywhere, remember rules about unaligned access, and write our own platform specific macros for memory barriers. Unless you're using Java, "volatile" is not useful for concurrent programming. When you see volatile keyword in C code, it's almost always wrong or there for a legacy reason. Sounds like your computer architecture classes were not up to date or very well taught.

kkyn 9y ago

It seems like weak memory models get short shrift, but if you're going to program without locks it's semi-important to understand what information one gets when examining a read-write pair.

sigu1 9y ago

I have always found that the biggest hurdle in

signa11 9y ago

imho, memory-barriers.txt, in linux kernel documentation should be a required grokking before getting into lockless stuff.

albertzeyer 9y ago
Link: https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt
- maxxxxx 9y ago
  I wish I could write that well :(. This is better than most write ups with fancy graphics.

codepie 9y ago

The thread example given in article is only limited to a single writer and multiple readers. Things get interesting when you want to have lock free concurrency with multiple readers and writers. One of the famous techniques is using software transactional memory (https://en.m.wikipedia.org/wiki/Software_transactional_memory https://en.m.wikipedia.org/wiki/Software_transactional_memor...). But it hasn't really caught up in the industry and it still exists within academia. The existing lock free concurrency solutions are not mature enough to replace locks. I like this analogy of what garbage collection is to memory is STM is to memory(https://homes.cs.washington.edu/~djg/papers/analogy_oopsla07.pdf https://homes.cs.washington.edu/~djg/papers/analogy_oopsla07...).

signa11 9y ago
> ... But it hasn't really caught up in the industry and it still exists within academia... acm had this article a while back: http://pages.cs.wisc.edu/~cain/pubs/cascaval_cacm08.pdf http://pages.cs.wisc.edu/~cain/pubs/cascaval_cacm08.pdf may you please comment on that ? thank you !
gpderetta 9y ago
There are lock free algos that support multiple writers. The reason they are sometime avoided is that, in addition of being often more complicated, they usually scale badly; that's inherently true with any algorithm violating the single writer principle, not just with lock-free algos; that's true with STM as well.
saas_co_de 9y ago
Intel has TSX https://software.intel.com/en-us/node/524022 https://software.intel.com/en-us/node/524022 I have never used it though and I am not sure who does.
- convolvatron 9y ago
  I wish this were more useful. The real sticking point for me is that you can run out of transaction contexts - which means you have to have a full software implementation as backup. the only case I can think of where I would actually use the thing is if I already had an STM runtime and I wanted to cut down some of the constant time overheads. the other problematic aspect s that transaction scheduler policy is pretty important for contended performance and as part of the broader system design. in this case you have to live with whatever intel gives you

JohnHam 9y ago

I have always found that the biggest hurdle in understanding concurrency

amelius 9y ago

How well does Rust support these concepts?

pjmlp 9y ago
As far as I know Rust doesn't have a memory model fully defined yet, but their type system already helps a lot. https://github.com/nikomatsakis/rust-memory-model https://github.com/nikomatsakis/rust-memory-model A bit old, https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.html https://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.h...
- steveklabnik 9y ago
  We don't, but there's been a ton of work; http://plv.mpi-sws.org/rustbelt/ http://plv.mpi-sws.org/rustbelt/ For this kind of thing we mostly say "we defer to the C++ memory model" at the moment.

Girlang 9y ago

No locks in Erlang.

srcmap 9y ago

I implemented a lockless IPC, DIPC - Interprocess Communication and Distributed IPC library in 2000-2002 time frame. The library is used in vxWorks, QNX, Linux (both kernel and user space.) and tested heavily on Xeon SMP 1-2GHz CPU at that time. For memory management, it was implemented in C++ and the message (Memory) Alloc/Free calls were all lockless. One can allocated a memory from kernel and send it as msg to user space and use it there without copy. The limitation is that the max allows messages are statically pre-allocated for the system. The library manages the pre-allocated pools of various sizes with lockless APIs. When the pools runs out, the API returns error. The only primitive the library depended on was Atomic_Inc/Dec - absolutely no mutex, spin locks in the non-blocking API code path, etc. The library was designed to support HA (High available ) TCP/IP stack and routing protocols. The APIs was not the complex. The most complicate part was the regress testing code and the diagnostic code. The API was used by team of 100+ developers. I need help them to debug complex IPC/DIPC issues - and prove to them when the error return, it was not the library/API issue. There was a trace mechanism that track all the messages went thru the system(s). The trace system was also completely non-blocking and lockless, worked both in kernel and user space. All context switches in Linux Kernel was tracked - very similar to FTRACE in kernel today. I hacked the kernel/bios to preserve the DRAM content part of the trace system during warmboot. This way, I can recovered all the messages, last context switched info even for kernel hang, crash issue for postmortem. The trace system used rdtsc for time stamping had 0.5 nano-seconds resolution on 2Ghz Xeon CPU. The API/Library worked fine. The overall system complexities was a big issue. We can demo TCP/IP, BGP and various routing protocols that did HA Switch over and In Service OS upgrade. But only as demo - and after switch over the state syncing took a long time and reliability of HA TCP/IP and routing protocol was an big issue. Base on the lesson learned from that project - I went on and coded a different Application level HA system. That system based everything on top of standard Linux API/utilities. That works much better and the HA port of the SW took only 1 dev (me) 3 weeks to code. It supported in service SW (include Linux kernel) upgrade, HW/SW fault detected and automatically switch over. It was deployed in Comcast. Fault detection took < 50 ms and switch over is almost instance. Full state sync was done with wget over management Ethernet interface and always took < 1 second. All incremental states update were done over UDP and took 1 pkt. The funny Biz/$ outcomes from these two projects: The first one: startup sold only one HA router for $200k and burned 100M+ of VC $ but sold to Nokia for $400+Mil. I was able to paid off my mortgage with the options from that company - Not FU money but ok outcome. The 2nd one: The startup sold $40M of products for $60K from that project to Comcast and various Cable companies at 60% margin. That product (with 19+ FPGA) was created/code/developed with ~8 HW/FW/SW engineers (including the 2 founders). The VC got "a seasoned CEO" - managed to raise a few more rounds, kick out the founders (MIT PhD), hired 160+ people and ran the company to the ground.

SEJeff 9y ago

Another one (posted by me) on "Fear and Loathing in Lock Free Programming": https://news.ycombinator.com/item?id=15530032 https://news.ycombinator.com/item?id=15530032

ozfive 9y ago

This is incredibly well thought out and written. I felt like a friend was telling me about something that we would only understand. Matt Kline, bravo.