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

61–70 of 86 posts

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

#61

Post by kerkeslager »

bluGill wrote: post #49
josephg wrote: post #29

Earlier quoted context omitted.

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?

This is impossible to do in a useful way for publication. You can do case studies, but minor changes in various factors that seem minor can make a massive difference in benchmarks. As such you need to find real world data, used in a real world scenario, for your application: then benchmark it. Even then you have a benchmark useful for your application only, and not worth publishing.

I disagree. I've gotten a lot from reading publications about people profiling their applications and posting about the results with descriptions of their application design and load. Yes, obviously you can't read that and draw conclusions about how the same data structure or algorithm will perform in your application, but it helps you build an intuition for what is likely to work in applications with different characteristics.

Here's an example: https://queue.acm.org/detail.cfm?id=1814327

If you read that for the first time and don't learn something, I'd be quite surprised.

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

#62

Post by slaymaker1907 »

kerkeslager wrote: post #59
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…

I appreciate your polite tone here. To expand on this at the risk of sounding a bit rude: nobody should listen to anyone who speaks about performance in terms of reasoning about a system instead of profiling it. Computers are shockingly complex. I can't tell you how many times I've reasoned about a system, ran the profiler, and discovered I was completely wrong. When I was working on an interpreter for a Lisp, I impl…

I don't think that's quite correct because there are many optimizations which are impossible (or nearly impossible) to do after a system is implemented. Daniel Lemire wrote an excellent post on this exact subject https://lemire.me/blog/2023/04/27/hotspot-performance-engine....

In terms of programming languages, I think python is an excellent example of a language which has many features that have ended up making it extremely difficult to optimize even compared to other dynamic languages like LISPs. Even if you don't have to worry about backwards compatibility, there are design decisions that can limit performance which end up necessitating a rewrite of the entire system to actually change.

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

#63

Post by gpderetta »

dragontamer wrote: post #60
gpderetta wrote: post #55

Earlier quoted context omitted.

A sync, assuming it is your typical memory barrier, is not bound by the L3 latency. You pay (in first approximation) the L3 cost when you touch a contended cache line, whether you are doing a plain write or a full atomic CAS. Separately fences and atomic RMWs are slower than plain read/writes, but that's because of the (partially) serialising effects they have on a CPU pipleline, and very little todo with L3 (or any…

Perhaps my brain is conflicting multiple things. So here's what I know. L1 / L2 caches are "inside the core". To talk to other cores, your data must leave L1/L2 cache and talk to a network. It is on _THIS_ network that the L3 cache exists. Its not really "L3 cache", its just the memory-network that implements the MOESI protocol (or whatever proprietary variant: MOESIF or whatever) that sits between L2 cache, L3 cache…

Indeed L3 being shared and also often working as the MOESI directory works out to the interthread latency being the same order of magnitude as the L3 latency.

My point is that sync has nothing to do with caches. Caches are coherent all the time and do not need barriers. In particular I don't think the git pull/push maps well to MOESI as it is an optimistic protocol and only require transfering opportunistically on demand what is actually needed by a remote core, not conservatively everything that has changed like in git.

The explicit sync model is more representative of non coherent caches, which are not really common as they are hard to use.

Memory barriers are for typical CPUs, purely an i internal matter of the core and synchronize internal queues with L1. In a simple x86 model, where the only visible source of reordering is StoreLoad, a memory barrier simply stalls the pipeline until all preceding stores in program order are flushed out of the write buffer into L1.

In practice things these days things are more complex and a fence doesn't fully stall the pipeline, potentially only needs to visibly prevents loads from completing.

Other more relaxed CPUs also need to synchronise load queues, but still for the most part fences are a core local matter.

Some architectures have indeed remote fences (even x86 is apparently getting some in the near future) but these are more exotic and, AFAIK, do not usually map to default c++11 atomics.

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

#64

Post by gpderetta »

m4nu3l wrote: post #57
cout wrote: post #56

Earlier quoted context omitted.

Maybe this has changed, but last time I looked at futexes there was no syscall for locking (assuming no contention), but unlocking always made a syscall. This was many years ago so it could be different now.

The code isn't the easiest to read but in glibc it seems that the syscall is only performed if waiters are detected in userspace during an unlock operation https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...

Indeed You only need to FUTEX_WAKE if you know there are waiters (or of you lost track of the number of waiters).

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

#65

Post by gpderetta »

CyberDildonics wrote: post #58
cjensen wrote: post #41

An issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type is 64-bits. Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits. You can then use the compared 64-bits as a kind of version number to prevent the a-b-a problem. Using only the built-in atomics is work…

> Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits The instructions should compare 128 bits and swap 128 bits. I don't know why 'good' algorithms would use these if they don't need to, because 128 bit operations are slower. Not only that, 128 bit compare and swap doesn't work if it is not 128 bit aligned while 64 bit compare and swap will work even if the…

On x86, any CAS on a misaligned address that crosses a cache line boundary can fault in the best case (if the mis-feature is disabled by the os) or cost thousands of clock cycles on all cores. So it "works" only for small values of "works".

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

#66

Post by dragontamer »

gpderetta wrote: post #63
dragontamer wrote: post #60

Earlier quoted context omitted.

Perhaps my brain is conflicting multiple things. So here's what I know. L1 / L2 caches are "inside the core". To talk to other cores, your data must leave L1/L2 cache and talk to a network. It is on _THIS_ network that the L3 cache exists. Its not really "L3 cache", its just the memory-network that implements the MOESI protocol (or whatever proprietary variant: MOESIF or whatever) that sits between L2 cache, L3 cache…

Indeed L3 being shared and also often working as the MOESI directory works out to the interthread latency being the same order of magnitude as the L3 latency. My point is that sync has nothing to do with caches. Caches are coherent all the time and do not need barriers. In particular I don't think the git pull/push maps well to MOESI as it is an optimistic protocol and only require transfering opportunistically on de…

> The explicit sync model is more representative of non coherent caches, which are not really common as they are hard to use.

Not that I'm a professional GPU programmer. But I'm pretty certain that GPU caches are non-coherent.

But yeah, cache-coherence is just assumed on modern CPUs. Your clarification on store-queues and load-queues is helpful (even if the caches are coherent, the store-queue and load-queue can still introduce an invalid reordering. So it sounds like your point is that the various sync() instructions are more about these queues?)

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

#67

Post by kerkeslager »

slaymaker1907 wrote: post #62
kerkeslager wrote: post #59

Earlier quoted context omitted.

I appreciate your polite tone here. To expand on this at the risk of sounding a bit rude: nobody should listen to anyone who speaks about performance in terms of reasoning about a system instead of profiling it. Computers are shockingly complex. I can't tell you how many times I've reasoned about a system, ran the profiler, and discovered I was completely wrong. When I was working on an interpreter for a Lisp, I impl…

I don't think that's quite correct because there are many optimizations which are impossible (or nearly impossible) to do after a system is implemented. Daniel Lemire wrote an excellent post on this exact subject https://lemire.me/blog/2023/04/27/hotspot-performance-engine... . In terms of programming languages, I think python is an excellent example of a language which has many features that have ended up making it…

> I don't think that's quite correct because there are many optimizations which are impossible (or nearly impossible) to do after a system is implemented.

Who said you have to profile after a system is implemented? Certainly I didn't: if anything, I prefer to profile during prototyping, although few companies outside the largest budget for any real prototyping these days it seems. Usually I settle for timing things and profiling as early as possible so that you can catch any performance issues before any calcifying structure is built around the non-performant code.

Yes, I did profile after the fact in the Lisp story, but my point in that story was that my reasoning led me to the wrong conclusions, not that I did everything perfectly (on the contrary, it's a story about learning from my mistakes!).

I agree that Daniel Lemire post is excellent, but nothing in that post leads me to believe he'd disagree with anything I've said.

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

#68

Post by sakras »

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

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

Here's one I had: I was trying to build a Bloom filter in parallel. Each thread had large-ish batches of hashes it wanted to insert into the filter. Naively, you'd just have each thread iterate through the batches and do __sync_fetch_and_or for each of the hashes (this was a register-blocked Bloom filter so we only needed to perform one 8-byte or operation per hash).

What ended up being MUCH faster was to partition the filter, and to have a lock per partition. Each thread would attempt to grab a random lock, perform its inserts into that partition, then release the lock and try to grab another random lock that it hasn't grabbed yet. Granted, these locks were just atomic booleans, not std::mutex or anything like that. But I think this illustrates that partitioning+locking can be better for throughput. If you want predictable latency for single inserts, then I'd imagine the __sync_fetch_and_or strategy would work better. Which maybe brings up a broader point that this whole discussion relies a lot on exactly what "faster" means to you.

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

#69

Post by xfs »

josephg wrote: post #29
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…

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?

https://youtu.be/_qaKkHuHYE0 (CppCon) A senior software engineer at Google tried to optimize tcmalloc by replacing a mutex with lockless MPMC queue. After many bugs and tears, the result is not statistically significant in production systems.

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

#70

Post by saagarjha »

samsquire wrote: post #52

I think I lean towards per-thread sharding instead of mutex based or lock free data structures except for lockfree ringbuffers. You can get embarassingly parallel performance if you split your data by thread and aggregate periodically. If you need a consistent view of your entire set of data, that is a slow path with sharding. In my experiments with multithreaded software I simulate a bank where many bankaccounts are…

This is a great way to structure your code if it’s possible to do so, but this isn’t always the case unfortunately :(
Post reply on HN