An introduction to lockless algorithms (2021)
1–10 of 71 posts
Re: An introduction to lockless algorithms (2021)
#2I like the code of this ringbuffer
https://www.linuxjournal.com/content/lock-free-multi-produce...
I liked this whitepaper 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
This is inspired by left-right concurrency control whitepaper Left-Right: A Concurrency Control Technique with Wait-Free Population Oblivious Reads
Re: An introduction to lockless algorithms (2021)
#3I like the code of this ringbuffer https://www.linuxjournal.com/content/lock-free-multi-produce... I liked this whitepaper 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 s…
Ringbuffers are one of my favorite things to use. Thanks for the article.
Re: An introduction to lockless algorithms (2021)
#4I like the code of this ringbuffer https://www.linuxjournal.com/content/lock-free-multi-produce... I liked this whitepaper 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 s…
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.
Re: An introduction to lockless algorithms (2021)
#5"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.
Re: An introduction to lockless algorithms (2021)
#6"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 algorit…
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.
You can make every data structure lock-free, even wait-free, there are universal constructions [1]. The resulting performance may however be prohibitive.
[1] https://www.researchgate.net/publication/221343511_Impossibi...
Re: An introduction to lockless algorithms (2021)
#7"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 algorit…
You are totally right. Here's my rough personal guideline: prefer mutexes over lockfree code - unless you can't. For example, you cannot lock a mutex from the audio callback because it might put the thread to sleep and you would miss your deadline. (For anyone interested in this topic: http://www.rossbencina.com/code/real-time-audio-programming-...)
Re: An introduction to lockless algorithms (2021)
#8"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 algorit…
To add to this, the superset of these ideas is referred to as "non-blocking", and lock-freedom is one flavor. There is also obstruction-freedom, starvation-freedom, wait-freedom, etc.. All of which have their own trade-offs and complexities. If you're interested in some literature, McKenney's book[0] is considered a great practical introduction to these ideas. (also discussed before on HN [1][2])
In applications where you're willing to trade throughput for latency (like RTOS schedulers, drivers, audio processing), it can often make sense to go for a wait-free data structure.
[0] https://arxiv.org/pdf/1701.00854.pdf
Re: An introduction to lockless algorithms (2021)
#9I like the code of this ringbuffer https://www.linuxjournal.com/content/lock-free-multi-produce... I liked this whitepaper 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 s…
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
- Jeff Preshing's blog (worth exploring all adjacent articles): https://preshing.com/20120612/an-introduction-to-lock-free-p...
- Bartosz Milewski: 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_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! :)
Re: An introduction to lockless algorithms (2021)
#10"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 algorit…
> Mutexes are very cheap in the uncontended case
It was a while ago I was deep into this mess so forgive any ignorance–but–iirc the thread-mutex dogma[1] has many pitfalls despite being so widely used. Primarily they’re easy to misuse (deadlocks, holding a lock across a suspend point), and have unpredictable performance because they span so far into compiler, OS and CPU territory (instruction reordering, cache line invalidation, mode switches etc). Also on Arm it’s unclear if mutices are as cheap because of the relaxed memory order(?). Finally code with mutices are hard to test exhaustively, and are prone to heisenbugs.
Now, many if not most of the above apply to anything with atomics, so lock-free/wait-free won’t help either. There’s a reason why a lot of concurrency is ~phd level on the theoretical side, as well as deeply coupled with the gritty realities of hardware/compilers/os on the engineering side.
That said, I still think there’s room for a slightly expanded concurrency toolbox for mortals. For instance, a well implemented concurrent queue can be a significant improvement for many workflows, perhaps even with native OS support (io_uring style)?. Another exciting example is concurrency permutation test frameworks[2] for atomics that reorder operations in order to synthetically trigger rare logical race conditions. I’ve also personally had great experience with the Golang race detector. I hope we see some convergence on some of this stuff within a few years. Concurrency is still incredibly hard to get right.
[1]: I say this only because CS degrees has preached mutices to as the silver bullet for decades.