Fine-grained locking with two-bit mutexes
probablydance.com
probablydance.com
This really only matters on contended spinlocks, which is not normally the case in a scalable system. But there are always pathological workloads that stress performance in challenging ways.
But even byte/word spin locks that could avoid the atomic unlock, and even in modern systems where atomic operations are quite cheap relative to cache miss, still have two major problems, the "thundering herd" effect, and unfairness/starvation.
The basic spin lock is just a bit or byte or word in memory where waiters just keep reading the lock value until it becomes unlocked, and then they attempt to lock it. If that fails, continue waiting.
The thundering herd problem is at the cache coherency level. If you have a bunch of CPUs waiting on the lock then when the lock is released at the cache coherency level they all have that line invalidated, and then they will each request the line again, see the new (unlocked) value, and they will all try to take the lock, and each of those lock operations is an exclusive access to the line which also invalidates all others, and in the end only one succeeds, so all the others were wasted and go back to waiting, pulling the line back into shared state. So N CPUs taking a contended spin lock can become an O(N^2) operation all up. Coherency protocols might be smart enough to mitigate this somewhat so it may not be not quite so bad, but it's always going to be costly and those hardware heuristics could break down in extreme cases. So the effective critical section including the lock overhead can grow quickly as you increase CPU count, which can cause scalability to not just hit a wall but go off a cliff and get worse as you get more CPUs contending for the lock. Which is obviously bad, but the negative feedback spiral is particularly bad (workload slows down -> more CPUs recruited to handle workload -> workload gets slower) and means you can get stuck in a degraded state beyond the overload condition.
The fairness problem is difficult as well. A cache coherency protocol itself can be fair and anti-starvation, in that a CPU will get access to a line in a relatively equal and timely manner, and that could be mathematically proven and verified in the hardware. But when you start building on top of that, those properties don't automatically translate to the higher level primitive. In the above situation where it's a free-for-all on the lock word, any one waiter may get access to the line fairly and never be starved at the hardware level, but each time it performs the atomic operation to acquire the lock it might find that it has been taken by another CPU -- the hardware doesn't know what the lock is or that the value 0x1234 means it's free. So to truly have fair and non-starving locks, you need to build them with those guarantees in software, and only rely on the hardware for atomic operations.
The ticket locks that parent poster refers to are one such solution for fairness as they're FIFO. They were brought in to Linux due to unfairness/starvation problems. They are since superseded by "queued" spinlocks which are also FIFO but instead of spinning on the lock word each CPU spins on its own area, so unlock becomes closer to a 1:1 operation at the coherency level rather than 1:N (using the "MCS" algorithm) which tackles the former thundering herd problem.
Reason: some rare cases of interaction between the thread running JS and the JIT or GC threads require somehow locking some of the object’s state. Objects need to be small since adding even one word costs multiple %’s of perf. And there happened to be two bits available in the indexingType byte in the header.
mutex is unlocked (state: unlocked)
A locks mutex (state: locked -> locked)
B attempts to lock mutex (state: locked -> sleeper)
C attempts to lock mutex (no changes)
A unlock mutex (state: sleeper -> unlocked), state was sleeper so notify_one B
B locks the mutex (state: unlocked ->locked)
B unlocks mutex (state: locked -> unlocked), state was locked, so do not notify
Incidentally, I love the atomic::wait in c++20, although it is not without issues https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p26...).
I had some concerns about the second one, but I think it works too…
Another interesting thing to point out is that there seems to be a crossover point between when using an array of std::mutex is better vs having an array of these pointer-locks. Imagine you have an array of pointers to objects that you want to lock. With the pointer locks, you’ll have 8 mutexes per cache line, which for small arrays will probably have a high degree of false sharing. With an array of std::mutex, you’d probably pad them out to 64 bytes and there would be no false sharing. But for larger arrays (assuming a uniform distribution of accesses), the probability of false sharing would be low enough that the pointer-mutex would be faster.
The last thing I have to say is that I’ve been reading a lot about memory models lately, and I’ve become terrified of trying to mix TLA+ and non-seq_cst memory orders. Since TLA+ produces a global total order of actions, you still haven’t quite properly model checked your program if you haven’t modeled C++’s memory in your spec. That said, you can probably get away with it most of the time (especially on x86).
But the point of the wait/notify in the post to sleep if I understand correctly. My guess is there is some amount of spurious waking up that’s happening, or multiple threads are woken up by the notify_one (it only guarantees at least one is woken up!) An exponential backoff would reduce the probability of these spurious wakeups colliding dramatically.
On a separate note, fairness isn’t always required, just throughput. If you need predictable latency then this lock won’t work for you, but in this case optimizing for mean latency seems more worthwhile.
Instead of that, use fetch_or with only the corresponding bit set. That leaves the rest of the word unchanged and the locking position set to one.
Then check the return value. You know the lock is taken now. If the bit is set in the return, it was locked before your fetch_or. So try-lock failed and changed nothing. If the bit is clear in the return, try-lock succeeded and you now hold the lock.
This eliminates the guess the word part of using CAS and eliminates the retry loop you get because other bits in the word might have changed while you were trying to lock it.
On the other hand atomic::wait doesn't necessarily map directly to a futex_wait (nor it can in all cases, futexes are always exactly 32 bits). IIRC, at least on libstdc++, atomic::{wait,notify_one} are user-space fast pathed so they already keep some side structure, so you could get away with calling notify_one unconditionally and use only one bit.
I think it is a mistake on libstdc++ part though. I really would like atomic to be a thin wrapper around futex and, as you can't rely on the fast path being available everywhere you need either platform specific code or suboptimal duplicate code.
In fact libstdc++ does more as it adds spin-waiting and more optimizations which are not necessarily wanted.
In the kernel of course you could just reuse your wait queue structure for that, which is exactly what bit mutexes do in Linux, but that's an implementation detail to my point.
It's a trade-off.
> Also I’m trying out a donation button for the first time. If open source work like this is valuable for you, consider paying for it. The recommended donation is $20 (or your local cost for an item on a restaurant menu) for individuals, or $1000 for organizations. (or your local cost of hiring a contractor for a day) But any amount is appreciated.
But also, you miss 100% of the shots you don't take.
[1]: http://joeduffyblog.com/2006/12/14/anticonvoy-locks-in-windo...
Also the article does indeed implement a real mutex (although a buggy one), not a spinlock. std::atomic::wait will use futexes (or whatever) underneath to genuinely put the process to sleep until it receives a wakeup.