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

61–70 of 71 posts

Re: An introduction to lockless algorithms (2021)

#61

Post by cryptonector »

slaymaker1907 wrote: post #59
cryptonector wrote: post #50

Earlier quoted context omitted.

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

Hmmm, good point, the init function does need a memory barrier. Thanks for the review!

Re: An introduction to lockless algorithms (2021)

#62

Post by loeg »

slaymaker1907 wrote: post #53
loeg wrote: post #26

Earlier quoted context omitted.

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…

I was responding specifically to this claim in the original comment:

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

Not interested in getting into a pedantic argument about the definition of "lockless" or "lockfree."

Re: An introduction to lockless algorithms (2021)

#64

Post by nyanpasu64 »

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

> O(N log(N)) where N is the maximum number of live threads that have read the variable and M is the number of values that have been set and possibly released).

If you reference N twice and M zero times, why did you define M? Did you make a typo in the O() or is this intentional?

> Most threads only ever need to call thread_safe_var_get().

> reference count the data.

Does getting a new value automatically release a reference to the old one (so it's no longer safe to read)?

Re: An introduction to lockless algorithms (2021)

#65

Post by gpderetta »

rootw0rm wrote: post #52
rerdavies wrote: post #41

Earlier quoted context omitted.

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

Explicit fences are extremely rarely needed on x86.

Re: An introduction to lockless algorithms (2021)

#66

Post by gpderetta »

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…

If you are using mutexes or other well defined abstractions, you need to care little about ordering.

If you are writing atomic based code, you should be using something like C++11 and C11 atomics that will take care of fencing on all platforms.

Re: An introduction to lockless algorithms (2021)

#68

Post by cryptonector »

slaymaker1907 wrote: post #59
cryptonector wrote: post #50

Earlier quoted context omitted.

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

I fixed that. TSAN also found a pair of data races involving assert()s (oof). All three are fixed.

Re: An introduction to lockless algorithms (2021)

#69

Post by cryptonector »

nyanpasu64 wrote: post #64
cryptonector wrote: post #50

Earlier quoted context omitted.

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

> O(N log(N)) where N is the maximum number of live threads that have read the variable and M is the number of values that have been set and possibly released). If you reference N twice and M zero times, why did you define M? Did you make a typo in the O() or is this intentional? > Most threads only ever need to call thread_safe_var_get(). > reference count the data. Does getting a new value automatically release a r…

> If you reference N twice and M zero times, why did you define M? Did you make a typo in the O() or is this intentional?

That was a typo. It should have read `O(N log(M))`.

> Does getting a new value automatically release a reference to the old one (so it's no longer safe to read)?

Correct. Every read (get) of the variable causes the previous value to no longer be safe to use in that thread.

Re: An introduction to lockless algorithms (2021)

#70

Post by cryptonector »

slaymaker1907 wrote: post #59
cryptonector wrote: post #50

Earlier quoted context omitted.

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

I've added use of Helgrind's `ANNOTATE_HAPPENS_BEFORE()` and `ANNOTATE_HAPPENS_AFTER()` macros to the functions in `atomics.c` and now this is Helgrind-clean as well as TSAN-clean.

The only bugs found by TSAN (as noted in another reply) were the one you found and two assert()s that didn't use atomics. Those two asserts could be a big problem if one ran a non-NDEBUG build in production.

So now this is TSAN- and Helgrind-clean.

Thanks for prompting me to do this extra work!

Post reply on HN