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

31–40 of 71 posts

Re: An introduction to lockless algorithms (2021)

#31

Post by mattpallissard »

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 should only consider going for a lockless algorithm if you can prove it is better than just using a mutex.

I'm with you. If you aren't benchmarking your datastructure changes, you probably shouldn't be messing around with lock-free code to begin with.

Re: An introduction to lockless algorithms (2021)

#32

Post by themulticaster »

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…

I'd like to add some context as to why lockless algorithms are popular in the Linux kernel. Roughly speaking, there are two possible scenarios in which kernel code is executed: Either in context of a process (e.g. while handling a syscall) or while handling an interrupt [1]. Now, a mutex usually sets the current thread to sleep if it tries to lock a currently locked mutex. Even in kernel land, this is perfectly fine as long as the kernel is in process context. However, while handling an interrupt there is no current thread that can be put to sleep. Therefore you can't use a mutex for kernel data structures that will be accessed during interrupts, and that applies to a lot of data structures.

This is why some common locking advice does not really apply to kernel code. Another example would be "avoid using spinlocks, prefer a mutex" - spinlocks are widely used in the kernel since they're the most straightforward alternative to mutexes.

Not disagreeing with the parent post, just wanted to add some context why LWN likes to talk about lockless algorithms.

[1] Actually, the kernel differentiates between hardirqs and softirqs, but that's not important here.

Re: An introduction to lockless algorithms (2021)

#33

Post by gsliepen »

corbet wrote: post #24
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…

Even an uncontended mutex can create a lot of cache-line bouncing, making it less cheap than it seems.

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.

Re: An introduction to lockless algorithms (2021)

#34

Post by gsliepen »

dataflow wrote: post #30
gsliepen wrote: post #28

Earlier quoted context omitted.

Yes, only a few lockless algorithms require only a single atomic operation. And as soon as you need to do cmpxchg in a loop and there is contention, you can burn a lot of cycles while cache lines bounce between cores, potentially an unbounded number of cycles if it is not a wait-free algorithm. While a mutex would have to pay the price of a futex call in the contended case, it is at least bounded.

Yeah. Now what about cases where the max contention is bounded (say, at most 2 threads waiting on a lock)? And what about factors other than running time? How does, say, fairness affect this picture?

If multiple cores are trying to do atomic operations on the same value, the hardware typically is not fair. For mutexes, it depends on whether the operating system wakes up waiters in a fair way. Often that is not fully fair either.

If there are only two threads at most, you can sometimes use a different algorithm than if you have an arbitrary number of threads (for example, for single-producer, single-consumer queues, lockless is typically better than with a mutex).

You should of course benchmark your particular problem to see what solution is actually faster.

Re: An introduction to lockless algorithms (2021)

#35

Post by liblfds-temp »

loeg wrote: post #27
liblfds-temp wrote: post #16

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

I might also point people at ConcurrencyKit.

I know Samy. CK is extremely well made.

Re: An introduction to lockless algorithms (2021)

#36

Post by gsliepen »

themulticaster wrote: post #32
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…

I'd like to add some context as to why lockless algorithms are popular in the Linux kernel. Roughly speaking, there are two possible scenarios in which kernel code is executed: Either in context of a process (e.g. while handling a syscall) or while handling an interrupt [1]. Now, a mutex usually sets the current thread to sleep if it tries to lock a currently locked mutex. Even in kernel land, this is perfectly fine…

Indeed. Also, spinlocks are not that great in userlang where one thread can preempt another thread that is holding a spinlock, which means threads on other cores that also want that lock would spin for a whole timeslice and burn a huge amount of cycles.

In the kernel, spinlocks are typically taken at the same time IRQs for the current core are disabled, which avoids this issue (and deadlocks of course).

Re: An introduction to lockless algorithms (2021)

#37

Post by dfox »

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…

The problem with typical OS-provided mutex is that it is almost always in some way distinctly non-cheap either because of the particular implementation or because of limitations imposed by ABI/API compatibility (and in some case both).

Re: An introduction to lockless algorithms (2021)

#38

Post by bsder »

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 should only consider going for a lockless algorithm if you can prove it is better than just using a mutex.

I would, in fact, give precisely the reverse advice for one reason:

Mutexs don't compose.

Mutexs are really good at putting subtle bugs into your code that are ridiculously difficult to figure out.

Lockless algorithms may be slower or cause performance issues, but they don't malfunction because you got the release order backwards.

Re: An introduction to lockless algorithms (2021)

#39

Post by cryptonector »

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're too focused on "mutex". There are many more interesting constructs that one can build in a lockless manner: lists, hash tables, RCU, etc.

Here's some of mine: https://github.com/cryptonector/ctp/

Re: An introduction to lockless algorithms (2021)

#40

Post by gautamdivgi »

nyanpasu64 wrote: post #21
gpderetta wrote: post #12

Earlier quoted context omitted.

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…

The nasty part of concurrency bugs is that normally you can expect the code is almost correct and needs some tweaks to fix oversights, but concurrency bugs in incompletely thought-out code more often requires throwing out the design to build it right. Additionally, concurrency issues usually arise from multiple components interacting in nonlocal ways, requiring a global knowledge of the system to diagnose and fix. An…

Aren’t there formal analysis techniques that can help ferret those out? My MSCS had a course called “science of programming”. The focus used to be proofs for correctness of programs, which included concurrent programs.
Post reply on HN