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

A collection of lock-free data structures written in standard C++11

github.com

Post reply on HN
Print view View original

31–40 of 86 posts

Re: A collection of lock-free data structures written in standard C++11

#31

Post by dnedic »

quietbritishjim wrote: post #27
smat wrote: post #25

Earlier quoted context omitted.

I assume the author of the library works under a hard real-time constraint. Under such circumstances (an example would be low latency audio) you can not tolerate the latency impact of a sporadic syscall.

Perhaps, but that is almost the opposite of what they said: in hard real time you can tolerate a longer average latency in return for needing a shorter maximum latency. That matches from what I would expect from a lock free data structure. But that doesn't match the (dubious) claim that locks are usually slower.

You make good points, I will try to rephrase that part of the README to be more accurate and explain benefits not mentioned yet like determinism.

Re: A collection of lock-free data structures written in standard C++11

#32

Post by [deleted] »

OskarS wrote: post #28
ot wrote: post #9

Earlier quoted context omitted.

This is true in principle and it is good calling it out, but in practice I've never seen a mutex-based data structure beat an equivalent lock-free data structure, even at low contention, unless the latter is extremely contrived. A mutex transaction generally requires 2 fences, one on lock and one on unlock. The one on unlock would not be strictly necessary in principle (on x86 archs the implicit acquire-release seman…

Assuming low or no contention, it is easy to imagine a scenario where a mutex vastly outperforms it: if you need to push a 1000 things into the queue, it's still just two fences for the mutex but it's now a 1000 CASes. Moreover: the point with mutexes is that your data structure can be the optimized assuming no thread-safety. There are lots of, like, hyper-optimized hash table variants (with all sorts of SIMD nonsens…

[deleted]

Re: A collection of lock-free data structures written in standard C++11

#33

Post by m4nu3l »

planede wrote: post #4
bluGill wrote: post #2

From the FAQ: > The biggest reason you would want to use a lockfree data structure in such a scenario would be performance. Locking has a non-neglegible runtime cost on hosted systems as every lock requires a syscall. This is misleading. While a lock does have a runtime cost, in some cases that cost is less than all the force CPU cache synchronization calls that lock free needs to do. With a lock you only have to syn…

Moreover, is "every lock requires a syscall" accurate? Probably depends on target platform and standard library, but my impression was that at low contention it doesn't really require syscalls, at least on Linux and glibc's pthread.

That's my understanding too. In Linux mutexes are implemented by futexes (Fast User-Space mutexes). If there is no contention they are guaranteed to not perform a syscall https://en.wikipedia.org/wiki/Futex

Re: A collection of lock-free data structures written in standard C++11

#34

Post by ape4 »

whiteboardma wrote: post #16
dnedic wrote: post #11

Earlier quoted context omitted.

Could you elaborate on the alleged race conditions? Any advice on reliably testing the race conditions? The problem with adding those is the fact that they will give lots of false negatives and if you rely on them you have a problem.

Looking at the Push operation defined in queue_impl.hpp, if multiple threads perform concurrent pushes, they might end up writing their element to the same slot in _data since the current position _w is not incremented atomically

Just add a lock ;)

Re: A collection of lock-free data structures written in standard C++11

#35

Post by ashvardanian »

bluGill wrote: post #2

From the FAQ: > The biggest reason you would want to use a lockfree data structure in such a scenario would be performance. Locking has a non-neglegible runtime cost on hosted systems as every lock requires a syscall. This is misleading. While a lock does have a runtime cost, in some cases that cost is less than all the force CPU cache synchronization calls that lock free needs to do. With a lock you only have to syn…

Both lock-free and mutex-based approaches have their applications. The general rule of thumb, for 2-4 threads in the same NUMA node lock-free is faster. Need more cores? Use a proper heavy mutex.

Re: A collection of lock-free data structures written in standard C++11

#36

Post by bluGill »

duped wrote: post #26
smat wrote: post #25

Earlier quoted context omitted.

I assume the author of the library works under a hard real-time constraint. Under such circumstances (an example would be low latency audio) you can not tolerate the latency impact of a sporadic syscall.

You often can tolerate the latency. The problem of locks is they are potentially unbounded and you can miss a deadline. It's not about performance so much as determinism.

Lock free doesn't solve this. One thread will always make progress, but you have no way to ensure it is your thread so you can miss a deadline with lock free. When the data is under a lot of contention across many cores this is an issue (most of us don't have hundreds of cores so we don't see this).

Generally lock-free is better for these situations as odds are when you hold a lock at least some CPU cycles are used for something that isn't directly modifying the data that needs the lock - those cycles the other CPU can touch it when lock-free. (note that when using a lock there is a trade-off, often it is better to hold the lock for longer than needed instead of dropping, doing a couple operations and then locking again)

Re: A collection of lock-free data structures written in standard C++11

#37

Post by tialaramex »

bluGill wrote: post #36
duped wrote: post #26

Earlier quoted context omitted.

You often can tolerate the latency. The problem of locks is they are potentially unbounded and you can miss a deadline. It's not about performance so much as determinism.

Lock free doesn't solve this. One thread will always make progress, but you have no way to ensure it is your thread so you can miss a deadline with lock free. When the data is under a lot of contention across many cores this is an issue (most of us don't have hundreds of cores so we don't see this). Generally lock-free is better for these situations as odds are when you hold a lock at least some CPU cycles are used f…

If you must make progress locally (not just globally) the guarantee you need is wait freedom which is even stronger than lock freedom.

(All wait free algorithms are lock free because necessarily if every thread is guaranteed to eventually make progress then overall progress is definitely made)

Re: A collection of lock-free data structures written in standard C++11

#38

Post by ot »

OskarS wrote: post #28
ot wrote: post #9

Earlier quoted context omitted.

This is true in principle and it is good calling it out, but in practice I've never seen a mutex-based data structure beat an equivalent lock-free data structure, even at low contention, unless the latter is extremely contrived. A mutex transaction generally requires 2 fences, one on lock and one on unlock. The one on unlock would not be strictly necessary in principle (on x86 archs the implicit acquire-release seman…

Assuming low or no contention, it is easy to imagine a scenario where a mutex vastly outperforms it: if you need to push a 1000 things into the queue, it's still just two fences for the mutex but it's now a 1000 CASes. Moreover: the point with mutexes is that your data structure can be the optimized assuming no thread-safety. There are lots of, like, hyper-optimized hash table variants (with all sorts of SIMD nonsens…

If you are going to do batch operations, your data structure should be optimized to support them, so you're back to one CAS. The same would apply to the locked scenario, where you probably don't want to copy 1000 elements in the critical section.

About the sufficiently smart optimizations, sure, everything is easy to imagine, but in my experience this never happened, and I'd be curious to hear practical examples if you have any.

Re: A collection of lock-free data structures written in standard C++11

#39

Post by T0pH4t »

OskarS wrote: post #28
ot wrote: post #9

Earlier quoted context omitted.

This is true in principle and it is good calling it out, but in practice I've never seen a mutex-based data structure beat an equivalent lock-free data structure, even at low contention, unless the latter is extremely contrived. A mutex transaction generally requires 2 fences, one on lock and one on unlock. The one on unlock would not be strictly necessary in principle (on x86 archs the implicit acquire-release seman…

Assuming low or no contention, it is easy to imagine a scenario where a mutex vastly outperforms it: if you need to push a 1000 things into the queue, it's still just two fences for the mutex but it's now a 1000 CASes. Moreover: the point with mutexes is that your data structure can be the optimized assuming no thread-safety. There are lots of, like, hyper-optimized hash table variants (with all sorts of SIMD nonsens…

^ This can definitely be the case in a multi-producer/multi-consumer (MPMC) scenario if CAS is involved with loops. Great care has to be taken when writing MPMC data structures without locks that are more performant then lock equivalents; they are far more complex. I think it should be called out that it seems most (if not all) of the data structures provided are single producer/consumer which generally always have much simpler designs (and limitations of use) then MPMC.

Re: A collection of lock-free data structures written in standard C++11

#40

Post by T0pH4t »

T0pH4t wrote: post #39
OskarS wrote: post #28

Earlier quoted context omitted.

Assuming low or no contention, it is easy to imagine a scenario where a mutex vastly outperforms it: if you need to push a 1000 things into the queue, it's still just two fences for the mutex but it's now a 1000 CASes. Moreover: the point with mutexes is that your data structure can be the optimized assuming no thread-safety. There are lots of, like, hyper-optimized hash table variants (with all sorts of SIMD nonsens…

^ This can definitely be the case in a multi-producer/multi-consumer (MPMC) scenario if CAS is involved with loops. Great care has to be taken when writing MPMC data structures without locks that are more performant then lock equivalents; they are far more complex. I think it should be called out that it seems most (if not all) of the data structures provided are single producer/consumer which generally always have m…

I could I should also say this applies to MPSC and SPMC. Basically anything other than SPSC.
Post reply on HN