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

21–30 of 86 posts

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

#21

Post by adzm »

kevincox wrote: post #5
planede wrote: post #4

Earlier quoted context omitted.

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.

Definitely not. I don't think there many standard libraries that use syscalls for every lock. It is near universal to attempt a lock in user space (maybe even spin a few times) and only call the kernel if you need to wait. So low-contention locks should very rarely make a syscall.

Critical sections in Windows certainly behave this way with a configurable spin count.

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

#22

Post by whiteboardma »

dnedic wrote: post #19
whiteboardma wrote: post #16

Earlier quoted context omitted.

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

This is a multi producer scenario, the README clearly states that these data structures are only single producer single consumer multi thread/interrupt safe. I will also add disclaimers to the javadocs comments on methods just to reduce confusion.

Wops, my bad

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

#23

Post by Koshkin »

Notbrainiac wrote: post #10

Every datastructure is lock free. Locks are required when you have multiple writers. The article states the usefull only for certain circumstance: for single consumer single producer scenarios. So yea within these assumptions you can make something work.

Note that "lock-free" is a technical term that has a very specific, precise meaning (implying that the user of the structure does not need to use locking explicitly).

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

#25

Post by smat »

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…

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.

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

#26

Post by duped »

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

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.

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

#27

Post by quietbritishjim »

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

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.

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

#28

Post by OskarS »

ot wrote: post #9
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…

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 nonsense and stuff) that are just not possible to do lock-free. The very "lock-freedomness" of the datastructure slows it down enough that in low contention scenarios mutexes clearly would outperform them without being particularly contrived.

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

#29

Post by josephg »

ot wrote: post #9
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…

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…

Are there any good benchmarks which demonstrate the performance characteristics you’re talking about? Or case studies where an application moved from mutexes to lock free data structures, and compared the resulting performance?

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

#30

Post by dnedic »

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 is why you would use the Ring Buffer or Bipartite Buffer to place 1000 elements at a time, not the queue. Check the documentation for more info.
Post reply on HN