Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An introduction to lockless algorithms (2021)

lwn.net

Post reply on HN
Print view View original

11–20 of 71 posts

Re: An introduction to lockless algorithms (2021)

#11

Post by kangda123 »

snakey wrote: post #9
samsquire wrote: post #2

I 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/20…

The Art of Multiprocessor Programming is really good

Re: An introduction to lockless algorithms (2021)

#12

Post by gpderetta »

klabb3 wrote: post #10
gsliepen wrote: post #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 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 i…

I think the issues with concurrency are at this point greatly overblown. Is it hard? Maybe, so it are a lot of things in our field. Is it phd level? Not at all, unless you are literally breaking new ground; most problems have very well known solutions.

Mutexes are a solution to the mutual exclusion problem, no more no less. Sometimes this problem can be solved by a queue, but that opens other large cans of worms like asynchronicity.

I write more lock-less [1] code than most, but I will often fall back to a mutex as the right solution for a problem given a complexity and performance budget.

[1] by that I mean code without standard use of mutexes, not necessarily non-blocking.

Re: An introduction to lockless algorithms (2021)

#13

Post by gpderetta »

spacechild1 wrote: post #7
gsliepen wrote: post #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 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-... )

Similar issues with locking mutexes from signal handlers or from high priority threads (if you want to avoid prio-inversion).

Re: An introduction to lockless algorithms (2021)

#14

Post by oriolid »

spacechild1 wrote: post #7
gsliepen wrote: post #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 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-... )

If putting the thread to sleep would be the problem, simple try_to_lock instead of blocking would be the solution. In practice, it looks like releasing the lock and potentially waking up threads that were blocking on it is another problem (https://timur.audio/using-locks-in-real-time-audio-processin...)

For what it's worth, on macOS profiling audio apps shows that the OS itself is using mutexes on audio thread and it doesn't seem to be a problem. The popular JUCE libraries add another set of mutexes.

Re: An introduction to lockless algorithms (2021)

#15

Post by gpderetta »

oriolid wrote: post #14
spacechild1 wrote: post #7

Earlier quoted context omitted.

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-... )

If putting the thread to sleep would be the problem, simple try_to_lock instead of blocking would be the solution. In practice, it looks like releasing the lock and potentially waking up threads that were blocking on it is another problem ( https://timur.audio/using-locks-in-real-time-audio-processin... ) For what it's worth, on macOS profiling audio apps shows that the OS itself is using mutexes on audio thread and…

try_lock fails. Then what?

Re: An introduction to lockless algorithms (2021)

#16

Post by liblfds-temp »

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

Re: An introduction to lockless algorithms (2021)

#17

Post by [deleted] »

gpderetta wrote: post #15
oriolid wrote: post #14

Earlier quoted context omitted.

If putting the thread to sleep would be the problem, simple try_to_lock instead of blocking would be the solution. In practice, it looks like releasing the lock and potentially waking up threads that were blocking on it is another problem ( https://timur.audio/using-locks-in-real-time-audio-processin... ) For what it's worth, on macOS profiling audio apps shows that the OS itself is using mutexes on audio thread and…

try_lock fails. Then what?

[deleted]

Re: An introduction to lockless algorithms (2021)

#18

Post by oriolid »

gpderetta wrote: post #15
oriolid wrote: post #14

Earlier quoted context omitted.

If putting the thread to sleep would be the problem, simple try_to_lock instead of blocking would be the solution. In practice, it looks like releasing the lock and potentially waking up threads that were blocking on it is another problem ( https://timur.audio/using-locks-in-real-time-audio-processin... ) For what it's worth, on macOS profiling audio apps shows that the OS itself is using mutexes on audio thread and…

try_lock fails. Then what?

Citing TFA,

> If you’re less lucky, you’ll have to switch your audio effect to bypass mode, or perhaps fade out, or some similar fallback strategy. It’s probably not ideal, but in many cases still better than a glitch.

Re: An introduction to lockless algorithms (2021)

#19

Post by dspig »

oriolid wrote: post #18
gpderetta wrote: post #15

Earlier quoted context omitted.

try_lock fails. Then what?

Citing TFA, > If you’re less lucky, you’ll have to switch your audio effect to bypass mode, or perhaps fade out, or some similar fallback strategy. It’s probably not ideal, but in many cases still better than a glitch.

or if the lock is on some smaller part you might be able to still render the audio but e.g. not update the settings that changed yet, and try again next time.

Re: An introduction to lockless algorithms (2021)

#20

Post by nyanpasu64 »

klabb3 wrote: post #10
gsliepen wrote: post #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 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 i…

In addition to lock-free queues, I think another important lock-free primitive is a cell where writing a value drops previous values, even if they haven't been read, used for eg. time of day, volume levels passed from an audio thread to a GUI VU meter, and the like. Implementations include word-sized relaxed atomics (bigger tears), SPSC triple buffers (doesn't generalize to >2 threads), or other days structures I don't understand as well, like RCU or hazard pointers.
Post reply on HN