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

21–30 of 71 posts

Re: An introduction to lockless algorithms (2021)

#21

Post by nyanpasu64 »

gpderetta wrote: post #12
klabb3 wrote: post #10

Earlier quoted context omitted.

> 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…

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. And finding the presence of a bug or reproducing it is usually probabilistic, making concurrency heisenbugs hard to discover, locate, and prove they're fixed.

It can be made somewhat tractable to experienced concurrency wizards; I think Rust's "cross-thread shared ^ mutable" rule is a good starting point, but have less experience with Go, JS, or Erlang-style approaches.

Re: An introduction to lockless algorithms (2021)

#22

Post by myrmidon »

gpderetta wrote: post #12
klabb3 wrote: post #10

Earlier quoted context omitted.

> 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…

From my point of view, the issues with concurrency (specifically the shared memory "threadlike"-kind) are absolutely NOT overblown, because misuse of that mechanism can completely RUIN a codebase in a way that few other things can; "goto" abuse would be a good analogy, or massive amounts of partly redundant global state.

My perception is that other comparably dangerous mechanisms are taught with appropriate caveats-- you WILL typically be admonished to keep variables as local as possible, learn how to encapsulate state, and probably be instructed to ALWAYS use proper loops, conditionals and function calls instead of wild gotos-- it does not even matter if you learn programming in university or on your own.

But with threading this is not the case, you'll typically get handed threading primitives without much prejudice, with predictable results.

Re: An introduction to lockless algorithms (2021)

#23

Post by intelVISA »

gpderetta wrote: post #12
klabb3 wrote: post #10

Earlier quoted context omitted.

> 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…

Concurrency, like distributed systems, is only "hard" in so much it's easier to sell your product, that features it, if you can convinice others of how arduous solving such a CS101 topic would otherwise be.

Re: An introduction to lockless algorithms (2021)

#24

Post by corbet »

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.

Re: An introduction to lockless algorithms (2021)

#25

Post by dataflow »

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…

> Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost.

You'll need to expand on this, since mutex acquisition also requires similar atomic read-modify-write operations. I think what you may be trying to say is that lockless algorithms require more of these operations as they scale to more processors?

Re: An introduction to lockless algorithms (2021)

#26

Post by loeg »

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 implemented with (among other) cmpxchg instructions under the hood. It’s sort of a false dichotomy to divide the world into locks and cmpxchgs. Also inconsistent to claim they are slow but uncontended mutexes are fast. It is certainly true that you can write slower and harder to understand algorithms using atomic primitives instead of mutexes.

Re: An introduction to lockless algorithms (2021)

#27

Post by loeg »

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.

Re: An introduction to lockless algorithms (2021)

#28

Post by gsliepen »

dataflow wrote: post #25
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…

> Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost. You'll need to expand on this, since mutex acquisition also requires similar atomic read-modify-write operations. I think what you may be trying to say is that lockless algorithms require more of these operations as they scale to more processors?

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.

Re: An introduction to lockless algorithms (2021)

#30

Post by dataflow »

gsliepen wrote: post #28
dataflow wrote: post #25

Earlier quoted context omitted.

> Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have a significant cost. You'll need to expand on this, since mutex acquisition also requires similar atomic read-modify-write operations. I think what you may be trying to say is that lockless algorithms require more of these operations as they scale to more processors?

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?
Post reply on HN