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.

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.

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.

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.

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)?

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.

^ 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.

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

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.

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/

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.

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.

A fully lock free allocator would be a huge result by itself: you would be able to allocate from a signal handler, or having truly lock free algorithms that do not need custom allocators, or avoid deadlock prone code in tricky parts like dlclose...

But I guess this was only one part and malloc wouldn't be fully lockfree.

In any case the lockfree mallocs designs I have seen use NxN queues to shuffle buffers around, but I guess it would be unsuitable for a generic malloc.

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.

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.

> 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.

Optimizing Lisp lexical environments with hashes is going to be a fool's errand. The way you optimize lexical environments is by compiling them, so that there is no searching at all.

The value in the interpreter is that it provides an alternative implementation of the semantics. This becomes particularly valuable in some area that happens to be under-documented, and the compiler and interpreter are found to disagree.

It can be easier to get the semantics right in the interpreter. A simple implementation of environments (and whatnot) reduces the likelihood of bugs and leaves the code readable. Interpreted behavior of special forms can usually serve as the reference implementation for compilation.

If an interpreter is slow, that just means that the build steps for bootstrapping the compiler using the interpreter takes longer.