A collection of lock-free data structures written in standard C++11 (opens in new tab)

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

Pikus has a number of C++ Parallelism performance talks that discusses this issue.

In particular, the "cost of synchronization" is roughly the price of a L3 memory read/write, or ~50 cycles. In contrast, a read/write to L1 cache is like 4 cycles latency and can be done multiple times per clock tick, and you can go faster (IE: register space).

So an unsynchronized "counter++" will be done ~4-billion times a second.

But a "counter++; sync()" will slow you down 50x slower. That is to say, the "sync()" is the "expensive part" to think about.

------------

A lock is two sync() statements. One sync() when you lock, and a 2nd sync() when you unlock. Really, half-sync() since one is an acquire half-sync and the other is a release half-sync.

If your lock-free data structure uses more than two sync() statements, you're _probably_ slower than a dumb lock-based method (!!!). This is because the vast majority of lock()/unlocks() are uncontested in practice.

So the TL;DR is, use locks because they're so much easier to think about. When you need more speed, measure first, because it turns out that locks are really damn fast in practice and kind of hard to beat.

That being said, there's other reasons to go lock-free. On some occasions, you will be forced to use lock-free code because blocking could not be tolerated. (Ex: lock-free interrupts. Its fine if the interrupt takes a bit longer than expected during contention). So in this case, even if lock-free is slower, the guarantee for forward progress is what you're going for, rather than performance.

So the study of lock-free data-structures is still really useful. But don't always think of for performance reasons, because these data-structures very well will be slower than std-library + lock() in many cases.

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.

For me the biggest benefit of lock free programming is avoiding deadlocks.

Locks are not composable. Unless you are aware of what locks every function in your call tree is using, you can easily end up with a deadlock.

This is why RCU, aka Read-Copy-Update, exists. RCU avoids the expensive synchronization part by delaying the release of the older version of the data structure until a point at which all CPUs are guaranteed to see the new version of the data. The patents have now expired, so it's worth investigating for people that need to write high performance multithreaded code that hits certain shared data structures really hard.

The linked talk from Herb Sutter says as much, but it is a good suggestion to make that visible upfrontm, thanks.

Additionally, cacheline alignment of indexes is something that's there to mitigate the false sharing phenomenom and reduce some of the cache synchronization cost.

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.

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.

Actually C++ only requires TriviallyComparable for std::atomic. The issue with 2CAS is that intel until very recently only provided cmpxchg16b[1] but no 128 atomic load and stores: SSE 128 bit memory operations were not guaranteed to be atomic (and in fact were observed not to be on some AMDs).

So a 128 bit std::atomic on intel was not only suboptimal as the compiler had to use 2cas for load and stores as well, but actually wrong as an atomic load from readonly memory would fault. So at some point the ABI was changed to use the spinlock pool. Not sure if it has changed since.

If you do it "by hand", when you only need a 2cas, a 128 bit load that is not atomic is fine as any tearing will be detected by the CAS and 'fixed', but it is hard for the compiler to optimize generic code.

[1] which actually does full 128bit compare and swap, you are probably confusing it with the Itanium variant.

The lack of DWCAS as a primitive in general is really annoying, C++ aside. RISC-V's -A extension has no form of it, either; you only get XLEN-sized AMO + LL/SC (no 2*XLEN LL/SC either!)

It's one of those features that when you want it, you really really really want it, and the substitutions are all pretty bad in comparison.

> 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 they aren't 64 bit aligned.

True, that would help immensely in creating MPMC data structures, but as these are SPSC there is no problem. Also to clarify, this is only for the indexes, the data members can be anything.

Using these intrinsics or inline assembly would break portability or create situations where platforms have different feature levels, which is not something I intend to do. I want the library to be compatible with everything from a tiny MCU to x86.

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

Even in single producer single consumer scenarios you need locks for multithreaded/interrupt use if you're not properly using atomics and proper fences.

You may need a lock if you have operations that are not atomic, even with a single writer, as a reader could find an inconsistency.

This seems unnecessarily pedantic. Lock-free conventionally implies concurrent, otherwise it's meaningless.

Lock-free doesn't mean "doesn't have locks". It means "doesn't need locks to be used concurrently".

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.

https://max0x7ba.github.io/atomic_queue/html/benchmarks.html for an existing set of benchmarks where this could be added

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

This is already noted in the Queue readme, only the Queue constructs the type, the other 2 data structures are meant for PODs only.

I will take a look at adding support for constructing in-place for the other 2 data structures, but at the moment, they are just for PODs.

Atomic operations can't be meaningfully said to perform any locking.

In any case lock-free is defined in term of progress guarantees.