6 ms·

An introduction to lockless algorithms (2021)

216 points by signa11 4y ago

samsquire 4y ago
I like the code of this ringbuffer https://www.linuxjournal.com/content/lock-free-multi-producer-multi-consumer-queue-ring-buffer https://www.linuxjournal.com/content/lock-free-multi-produce... I liked this whitepaper https://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf https://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf I am a beginner at this kind of thing but I created an array of integers that each thread owns an index. They write to the array at their index that they want access to the critical section. We scan the array forwards and backwards to see if there is any thread that has claim to the critical section. I even TRIED to write a model checker https://github.com/samsquire/multithreaded-model-checker https://github.com/samsquire/multithreaded-model-checker This is inspired by left-right concurrency control whitepaper Left-Right: A Concurrency Control Technique with Wait-Free Population Oblivious Reads
- ki_ 4y ago
  Ringbuffers are one of my favorite things to use. Thanks for the article.
- dist1ll 4y ago
  The article in the first link is pretty bad, and the entire code is undefined behavior. First of all, using inline asm + volatile to emulate well-ordered release & acquire on x86 is unnecessary. That's exactly what atomics are supposed to provide for you. > In this article, I concentrate on x86, as it is the most widespread architecture rather than write generic (but slower) code. Any reasonable C++ compiler will generate simple loads and stores for atomic r&a. There's no penalty for writing generic code.
- snakey 4y ago
  I too am a beginner with concurrent programming—it's a difficult topic to get your head around at first. Some resources that I've found super helpful: - Dmitry Vyukov's Lockless Algorithms: https://www.1024cores.net/home/lock-free-algorithms https://www.1024cores.net/home/lock-free-algorithms - Jeff Preshing's blog (worth exploring all adjacent articles): https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p... - Bartosz Milewski: https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-ordering/ https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-... - Memory Barriers: a Hardware View for Software Hackers—P.McKenney: https://www.researchgate.net/publication/228824849_Memory_Barriers_a_Hardware_View_for_Software_Hackers https://www.researchgate.net/publication/228824849_Memory_Ba... I hope you find some of these useful. I've re-read Paul McKenney's paper every 2-3 months in an attempt to get this stuff to stick! :)
  - kangda123 4y ago
    The Art of Multiprocessor Programming is really good
  - neandrake 4y ago
    Thanks for linking all these references! I’m also new to a lot of these topics but recently read Rust Atomics and Locks which has helped my understanding quite a bit - at least keeping me above water reading all the discussion in this post. The examples are in Rust but the concepts are at the kernel/cpu level and apply beyond the language. I recommend it. https://marabos.nl/atomics/ https://marabos.nl/atomics/
gsliepen 4y ago
"Lockless" sounds very positive, and it's tempting to think that everything should be made lockless. However, it's less great than it sounds. Mutexes are very cheap in the uncontended case, and in the contended case they have some nice properties. You should only consider going for a lockless algorithm if you can prove it is better than just using a mutex. Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost. Another problem with lockless is that you can't turn every algorithm into a lockless one, it's actually only a handful of them that are practical to implement locklessly. Of course, the ones that are practical, like some queue and linked list algorithms, can give very nice benefits if used correctly.
- corbet 4y ago
  Even an uncontended mutex can create a lot of cache-line bouncing, making it less cheap than it seems.
  - gsliepen 4y ago
    But a lockless algorithm would have the same amount of cache-line bouncing in the uncontended case. In the LWN series about lockless algorithms, there is a lot of detail about the atomic primitives used in them, but apart from ringbuffers, linked lists and RCU, I actually didn't see any mention of higher level lockless algorithms. For single-producer, single-consumer queues and for linked lists, lockless algorithms are known and performant, but many others are either not that performant, or they come with severe restrictions. For example, RCU sounds great, but you have to worry about grace periods, and you should only use it when you read much more often than you modify.
    - cryptonector 4y ago
      I've an RCU-like scheme that's performant and doesn't have anything like grace periods, and it works in user-land. https://github.com/cryptonector/ctp https://github.com/cryptonector/ctp
liblfds-temp 4y ago
I am the author of liblfds, a portable, license-free, lock-free data structure library written in C. I've been working on other projects for the last number of years, but I'm finally back to liblfds and making progress toward the next release. https://www.liblfds.org/slblog/2023-04.html https://www.liblfds.org/slblog/2023-04.html
- loeg 4y ago
  I might also point people at ConcurrencyKit.
  - liblfds-temp 4y ago
    I know Samy. CK is extremely well made.
haberman 4y ago
I only had time to skim, but the primitives described here (acquire, release, happens before) sound almost exactly like the model that was standardized in C++11 and C11.
- loeg 4y ago
  This is not a coincidence. :-)
DSingularity 4y ago
When “lockless” algorithms rely on CMPXCHG aren’t they just shifting the lock from software to hardware?
atorodius 4y ago
I am a noob here, so maybe this is obvious, but how exactly is a "lock" defined? it seems to me the acquire/release semantics are very similar to locks? I.e. I'm struggling to understand what is "lockless" about the primitives.

216 points by signa11 4y ago

I like the code of this ringbuffer https://www.linuxjournal.com/content/lock-free-multi-producer-multi-consumer-queue-ring-buffer https://www.linuxjournal.com/content/lock-free-multi-produce... I liked this whitepaper https://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf https://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf I am a beginner at this kind of thing but I created an array of integers that each thread owns an index. They write to the array at their index that they want access to the critical section. We scan the array forwards and backwards to see if there is any thread that has claim to the critical section. I even TRIED to write a model checker https://github.com/samsquire/multithreaded-model-checker https://github.com/samsquire/multithreaded-model-checker This is inspired by left-right concurrency control whitepaper Left-Right: A Concurrency Control Technique with Wait-Free Population Oblivious Reads

ki_ 4y ago
Ringbuffers are one of my favorite things to use. Thanks for the article.
dist1ll 4y ago
The article in the first link is pretty bad, and the entire code is undefined behavior. First of all, using inline asm + volatile to emulate well-ordered release & acquire on x86 is unnecessary. That's exactly what atomics are supposed to provide for you. > In this article, I concentrate on x86, as it is the most widespread architecture rather than write generic (but slower) code. Any reasonable C++ compiler will generate simple loads and stores for atomic r&a. There's no penalty for writing generic code.
snakey 4y ago
I too am a beginner with concurrent programming—it's a difficult topic to get your head around at first. Some resources that I've found super helpful: - Dmitry Vyukov's Lockless Algorithms: https://www.1024cores.net/home/lock-free-algorithms https://www.1024cores.net/home/lock-free-algorithms - Jeff Preshing's blog (worth exploring all adjacent articles): https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p... - Bartosz Milewski: https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-ordering/ https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-... - Memory Barriers: a Hardware View for Software Hackers—P.McKenney: https://www.researchgate.net/publication/228824849_Memory_Barriers_a_Hardware_View_for_Software_Hackers https://www.researchgate.net/publication/228824849_Memory_Ba... I hope you find some of these useful. I've re-read Paul McKenney's paper every 2-3 months in an attempt to get this stuff to stick! :)
- kangda123 4y ago
  The Art of Multiprocessor Programming is really good
- neandrake 4y ago
  Thanks for linking all these references! I’m also new to a lot of these topics but recently read Rust Atomics and Locks which has helped my understanding quite a bit - at least keeping me above water reading all the discussion in this post. The examples are in Rust but the concepts are at the kernel/cpu level and apply beyond the language. I recommend it. https://marabos.nl/atomics/ https://marabos.nl/atomics/

gsliepen 4y ago

"Lockless" sounds very positive, and it's tempting to think that everything should be made lockless. However, it's less great than it sounds. Mutexes are very cheap in the uncontended case, and in the contended case they have some nice properties. You should only consider going for a lockless algorithm if you can prove it is better than just using a mutex. Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost. Another problem with lockless is that you can't turn every algorithm into a lockless one, it's actually only a handful of them that are practical to implement locklessly. Of course, the ones that are practical, like some queue and linked list algorithms, can give very nice benefits if used correctly.

corbet 4y ago
Even an uncontended mutex can create a lot of cache-line bouncing, making it less cheap than it seems.
- gsliepen 4y ago
  But a lockless algorithm would have the same amount of cache-line bouncing in the uncontended case. In the LWN series about lockless algorithms, there is a lot of detail about the atomic primitives used in them, but apart from ringbuffers, linked lists and RCU, I actually didn't see any mention of higher level lockless algorithms. For single-producer, single-consumer queues and for linked lists, lockless algorithms are known and performant, but many others are either not that performant, or they come with severe restrictions. For example, RCU sounds great, but you have to worry about grace periods, and you should only use it when you read much more often than you modify.
  - cryptonector 4y ago
    I've an RCU-like scheme that's performant and doesn't have anything like grace periods, and it works in user-land. https://github.com/cryptonector/ctp https://github.com/cryptonector/ctp

liblfds-temp 4y ago

I am the author of liblfds, a portable, license-free, lock-free data structure library written in C. I've been working on other projects for the last number of years, but I'm finally back to liblfds and making progress toward the next release. https://www.liblfds.org/slblog/2023-04.html https://www.liblfds.org/slblog/2023-04.html

loeg 4y ago
I might also point people at ConcurrencyKit.
- liblfds-temp 4y ago
  I know Samy. CK is extremely well made.

haberman 4y ago

I only had time to skim, but the primitives described here (acquire, release, happens before) sound almost exactly like the model that was standardized in C++11 and C11.

loeg 4y ago
This is not a coincidence. :-)

DSingularity 4y ago

When “lockless” algorithms rely on CMPXCHG aren’t they just shifting the lock from software to hardware?

atorodius 4y ago

I am a noob here, so maybe this is obvious, but how exactly is a "lock" defined? it seems to me the acquire/release semantics are very similar to locks? I.e. I'm struggling to understand what is "lockless" about the primitives.