5 ms·

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 structur

by ot 3y ago

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 semantics would be enough) but you generally do a CAS anyway to atomically check whether there are any waiters that need a wake-up, which implies a fence. Good lock-free data structures OTOH require just one CAS (or other fenced RMW) on the shared state. Besides, at large scale, no matter how small your critical section is, it will be preempted every once in a while, and when you care about tail latency that is visible. Lock-free data structures have more predictable latency characteristics (even better if wait-free).

OskarS 3y ago
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.
- dnedic 3y ago
  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.
- deleted 3y ago
  [deleted]
- ot 3y ago
  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.
  - sakras 3y ago
    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.
    - ot 3y ago
      This seems to me like a parallel accumulation problem, why not have each thread accumulate a filter on a subset of the data (so no locking involved), and then reduce the results (which is just an OR of all the local accumulations)?
      - sakras 3y ago
        Parallel reductions are more heavy-weight synchronizations than locks. Say we have 64 partitions, then we need to perform 6 levels of tree reduction, or avoid parallelism completely and perform the reduction on a single thread. Either way it was slower. The locking strategy very rarely had any reduction in parallelism due to the randomized lock-taking. There were also other reasons, such as not wanting to replicate the filter per-thread.
- T0pH4t 3y ago
  ^ 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.
  - T0pH4t 3y ago
    I could I should also say this applies to MPSC and SPMC. Basically anything other than SPSC.
josephg 3y ago
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?
- bluGill 3y ago
  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.
  - kerkeslager 3y ago
    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 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.
    - josephg 3y ago
      Thanks for the link! I read that about a decade ago, and its still a great read. That article makes it seem ridiculous to implement software any other way. And yet, yesterday I watched a talk about how ridiculous it is to use mmap to implement a database: https://db.cs.cmu.edu/mmap-cidr2022/ https://db.cs.cmu.edu/mmap-cidr2022/ And I ended up side tracked watching some talks from CMU about database page buffers and such. Its weird how people with different backgrounds (OS / kernel people and database people) come to very similar problems in computing with very different perspectives, and they end up implementing very different systems as a result. And in each case, each community thinks the other way is basically wrong. My understanding is that Linus Torvalds thinks O_DIRECT is a ridiculous flag that database people probably don't want. And from a database perspective, its crazy how difficult the linux kernel makes it to write high performance filesystem code that never corrupts data if the system crashes. fsync is a misshapen sledgehammer, and disk write barriers or IO completion events are totally missing from linux.
kerkeslager 3y ago
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 implemented my first cut of scopes (all the variables within a scope and their values) as a naive unsorted list of key/value pairs, thinking I'd optimize later. When I came back to optimize, I reimplemented this as a hashmap, but when I ran my test programs, to my horror, they were all 10x slower. I plugged in a hashmap library used in lots of production systems and got a significant 2x performance gain, which was still slower than looping over an unsorted list of key/value pairs. The fact is, most scopes have <10 variables, and at that size, looping over a list is faster than the constant time of a hashmap. I can reason about why this is, but that's just fitting my reasons to the facts ex-post-facto. Reasoning didn't lead me to the correct answer, observation did. Returning to parallel data structures, the fact is, I don't know why lock-free structures are faster than mutex-based structures, I just know that they are in every situation where I've profiled them. Reasoning isn't completely useless--reasoning is how you intuit what you should be profiling. But if you're just reasoning about how two alternatives will perform and not profiling them in real-life production systems you're wasting everyone's time.
- slaymaker1907 3y ago
  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-engineering-fails/ 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.
  - 3y ago

by ot 3y ago

OskarS 3y ago

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.

dnedic 3y ago
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.
deleted 3y ago
[deleted]
ot 3y ago
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.
- sakras 3y ago
  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.
  - ot 3y ago
    This seems to me like a parallel accumulation problem, why not have each thread accumulate a filter on a subset of the data (so no locking involved), and then reduce the results (which is just an OR of all the local accumulations)?
    - sakras 3y ago
      Parallel reductions are more heavy-weight synchronizations than locks. Say we have 64 partitions, then we need to perform 6 levels of tree reduction, or avoid parallelism completely and perform the reduction on a single thread. Either way it was slower. The locking strategy very rarely had any reduction in parallelism due to the randomized lock-taking. There were also other reasons, such as not wanting to replicate the filter per-thread.
T0pH4t 3y ago
^ 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.
- T0pH4t 3y ago
  I could I should also say this applies to MPSC and SPMC. Basically anything other than SPSC.

josephg 3y ago

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?

bluGill 3y ago
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.
- kerkeslager 3y ago
  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 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.
  - josephg 3y ago
    Thanks for the link! I read that about a decade ago, and its still a great read. That article makes it seem ridiculous to implement software any other way. And yet, yesterday I watched a talk about how ridiculous it is to use mmap to implement a database: https://db.cs.cmu.edu/mmap-cidr2022/ https://db.cs.cmu.edu/mmap-cidr2022/ And I ended up side tracked watching some talks from CMU about database page buffers and such. Its weird how people with different backgrounds (OS / kernel people and database people) come to very similar problems in computing with very different perspectives, and they end up implementing very different systems as a result. And in each case, each community thinks the other way is basically wrong. My understanding is that Linus Torvalds thinks O_DIRECT is a ridiculous flag that database people probably don't want. And from a database perspective, its crazy how difficult the linux kernel makes it to write high performance filesystem code that never corrupts data if the system crashes. fsync is a misshapen sledgehammer, and disk write barriers or IO completion events are totally missing from linux.

kerkeslager 3y ago

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 implemented my first cut of scopes (all the variables within a scope and their values) as a naive unsorted list of key/value pairs, thinking I'd optimize later. When I came back to optimize, I reimplemented this as a hashmap, but when I ran my test programs, to my horror, they were all 10x slower. I plugged in a hashmap library used in lots of production systems and got a significant 2x performance gain, which was still slower than looping over an unsorted list of key/value pairs. The fact is, most scopes have <10 variables, and at that size, looping over a list is faster than the constant time of a hashmap. I can reason about why this is, but that's just fitting my reasons to the facts ex-post-facto. Reasoning didn't lead me to the correct answer, observation did. Returning to parallel data structures, the fact is, I don't know why lock-free structures are faster than mutex-based structures, I just know that they are in every situation where I've profiled them. Reasoning isn't completely useless--reasoning is how you intuit what you should be profiling. But if you're just reasoning about how two alternatives will perform and not profiling them in real-life production systems you're wasting everyone's time.

slaymaker1907 3y ago
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-engineering-fails/ 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.
- 3y ago