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

51–60 of 71 posts

Re: An introduction to lockless algorithms (2021)

#51

Post by cryptonector »

bsder wrote: post #38
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…

> Mutexs don't compose.

The don't compose because (as you hinted) lock taking/releasing order has to be the same for all callers, but if mutexes are being taken behind the scenes then API usage order becomes critical, and it is trivial to screw that up.

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

And they may scale better. Scalability is important.

For me the classic case is rw locks vs. RCU-ish schemes. I think there's no case where rw locks are ever appropriate if you have an RCU-ish alternative. For example, OpenSSL uses only rw locks -- nuts!

Re: An introduction to lockless algorithms (2021)

#52

Post by rootw0rm »

rerdavies wrote: post #41
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…

On Intel processors, which have strong memory order, concurrency is fairly easy to reason about. On processors with weak memory ordering (ARM notably), things get really treacherous. I'm still settling in to the horrors of memory ordering on ARM. The one thing I know for sure, is that my oeuvre contains a trail of code that will work fine on Intel processors, but won't work on ARM (or any other processor with weak me…

You should always use memory fences on Intel when using atomics imo

Re: An introduction to lockless algorithms (2021)

#53

Post by slaymaker1907 »

loeg wrote: post #26
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.

This is a common misunderstanding but just because you use cmpxchgs and other similar instructions has nothing to do with being lockfree. Lockfree really means *dead*lock free since it guarantees that some thread always makes progress. This is far more difficult than it sounds since you can't assume that some particular thread (like the one holding a lock) is ever scheduled. Some models relax this a bit though and do assume a thread requesting to execute will eventually execute in which case systems with mutexes can be lockfree.

Re: An introduction to lockless algorithms (2021)

#54

Post by klabb3 »

intelVISA wrote: post #23
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…

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.

If I were younger you would have triggered my impostor syndrome, but as a man of wisdom I know that you (a) have super-human skills[1] nobody else has, or (b) you’re talking about something different.

Note I’m not talking about an isolated case of analyzing a concurrent snippet of code for happens-before relationships, but rather how to write highly concurrent code within large scale applications, without runaway complexity.

[1]: https://bholley.net/blog/2015/must-be-this-tall-to-write-mul...

Re: An introduction to lockless algorithms (2021)

#55

Post by klabb3 »

nyanpasu64 wrote: post #20
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…

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…

Yes! I’ve used atomics for metric counters (MPMC) with reasonable success. But for anything larger than an atomic uint64, you’d need good library support. Fortunately this can be solved without OS support in an optimistic fashion (atomic retry loop), right?

Re: An introduction to lockless algorithms (2021)

#56

Post by cryptonector »

nyanpasu64 wrote: post #20
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…

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…

> another important lock-free primitive is a cell where writing a value drops previous values, even if they haven't been read

More importantly, if you've read a value then that value should stay alive (not be destructed/collected) until you explicitly release it or re-read that "cell".

Then what you do is publish immutable data to the "cell".

Unlike rw locks there's neither the risk of readers blocking behind writers nor writers being starved, and it's highly concurrent.

Clojure has a `ref` for this. Linux has RCU, which is a bit like this.

I've implemented just that in a lockless way twice (see elsewhere in this thread) with this C API:

  typedef struct thread_safe_var *thread_safe_var; /* TSV */
  typedef void (*thread_safe_var_dtor_f)(void *); /* Value destructor */

  /* Initialize a TSV with a given value destructor */
  int  thread_safe_var_init(thread_safe_var *, thread_safe_var_dtor_f);

  /* Destroy a TSV */
  void thread_safe_var_destroy(thread_safe_var);

  /* Get the current value of the TSV and a version number for it */
  int  thread_safe_var_get(thread_safe_var, void **, uint64_t *);

  /* Release the reference to the last value read by this thread from the TSV */
  void thread_safe_var_release(thread_safe_var);

  /* Wait for a value to be set on the TSV */
  int  thread_safe_var_wait(thread_safe_var);

  /* Set a new value on the TSV (outputs the new version) */
  int  thread_safe_var_set(thread_safe_var, void *, uint64_t *);

Re: An introduction to lockless algorithms (2021)

#57

Post by afr0ck »

gsliepen wrote: post #36
themulticaster wrote: post #32

Earlier quoted context omitted.

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

You don't have to disable IRQs if the spinlock is never taken by an interrupt handler. Disabling preemption would be enough in such a case, and that reduces latency issues related to disabling IRQs.

Re: An introduction to lockless algorithms (2021)

#58

Post by gsliepen »

bsder wrote: post #38
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…

I see your point, but as a counterpoint, consider that you have two or more distinct data structures, for example several separate linked lists. What if you need to update multiple lists in one atomic operation? With mutexes, you can do this rather easily: either you have one mutex that guards all lists, or you have one mutex for each list and you ensure you always take them in the same order. I would think that qualifies as composing. However, you can't easily compose a lockless algorithm that works on one list to make it work on multiple at the same time.

Re: An introduction to lockless algorithms (2021)

#59

Post by slaymaker1907 »

cryptonector wrote: post #50
gsliepen wrote: post #33

Earlier quoted context omitted.

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

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

Just looking at this initially, thread_safe_var_init is not correct. There is no guarantee whatsoever that "*vpp = vp" actually does anything, the compiler is perfectly free to just never allocate vp and just use the memory at vpp (thus allowing partial initialization) and the situation is even worse on ARM. You need some sort of memory barrier between that last assignment and it should probably be a volatile/std::atomic pointer.

Re: An introduction to lockless algorithms (2021)

#60

Post by neandrake »

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…

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/

Post reply on HN