Of course, with Cosmopolitan being open source and all, I could do these measurements myself, but still ...
Of course, with Cosmopolitan being open source and all, I could do these measurements myself, but still ...
Pro tip: if you really do know that contention is unlikely, and uncontended acquisition is super important, then it's theoretically impossible to do better than a spinlock.
Reason: locks that have the ability to put the thread to sleep on a queue must do compare-and-swap (or at least an atomic RMW) on `unlock`. But spinlocks can get away with just doing a store-release (or just a store with a compiler fence on X86) to `unlock`.
Spinlocks also have excellent throughput under most contention scenarios, though at the cost of power and being unkind to other apps on the system. If you want your spinlock to be hella fast on contention just make sure you `sched_yield` before each retry (or `SwitchToThread` on Windows, and on Darwin you can do a bit better with `thread_switch(MACH_PORT_NULL, SWITCH_OPTION_DEPRESS, 1)`).
The more common pattern in rt/audio code is "try to take the lock, but have an alternate code path if that fails". It's not that is never going to be contention, but it will be extremely rare, and when it occurs, it probably matters. RWLocks are also a common pattern, with the RT thread(s) being read-only (and still being required to fall back on an alternate code path if the read lock cannot be taken).
if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return;
for (unsigned i = 0; i < 40; ++i) {
/* spin for a bounded a mount of time */
if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return;
sched_yield();
}
... /* actual full lock algo goes here */
So, the reason to use spinlocks isn't that they are faster for short critical sections, but that they don't have to CAS on unlock - and so they are faster especially in the uncontended case (and in all other cases too).In other words, the modern rule of thumb is something like: if you're going to grab the lock so frequently that the uncontended lock/unlock time shows up as a significant percentage of your execution time, then use a spinlock. That probably implies that you are probably holding the lock for <100x or even <1000x context switch time, or something around there.
Realistically though, lots of lock free employs copy-on-write or rcu.
I have written quite the fair share of lock free code (back then when it was new), and generally enjoy writing it (to this day). Yet, for most folks it's just too hard to reason/understand/maintain it.
Just a note, lock free is a lesser requirement than wait-free.
Yeah, and maybe also consider changing your design because usually this isn't needed.
Every time I've seen this happen it's in code that scales really well to lots of CPUs while having a lot of shared state, and the way it gets there is that it's using very fine-grained locks combined with smart load balancing. The idea is that the load balancer makes it improbable-but-not-impossible that two processors would ever want to touch the same state. And to achieve that, locks are scattered throughout, usually protecting tiny critical sections and tiny amounts of state.
Whenever I've gotten into that situation or found code that was in that situation, the code performed better than if it had coarser locks and better than if it used lock-free algorithms (because those usually carry their own baggage and "tax"). They performed better than the serial version of the code that had no locks.
So, the situation is: you've got code that performs great, but does in fact spend maybe ~2% of its time in the CAS to lock and unlock locks. So... you can get a tiny bit faster if you use a spinlock, because then unlocking isn't a CAS, and you run 1% faster.
So I would only use this pattern for situations where the very fact that a NRT thread tries to acquire the lock already means that RT safety is not a concern anymore (e.g. a device has been disconnected)
For this reason, on Darwin you want to avoid spinlocks unless you know that all threads touching the spinlock are always running in the same QoS. Instead of spinlocks, your go-to for low-overhead locks there is os_unfair_lock, which is a spinlock variant that donates priority of the blocked threads to the running thread.
I know it can happen in theory. But theory and practice ain’t the same.
I worked for Apple when I shipped this too lmao
One particular app had a particularly nasty habit of losing priority because most of its work was done in a set of daemons and not in the UI process itself. The foreground app is allowed to use Performance cores and receive USER_INTERACTIVE priority for operations if it wants, but daemons cannot unless they have a mach IPC voucher stating that the UI is blocked on their work. But if you do the wrong thing with a semaphore or a spinlock, you get booted out of the thread group and now you’re running on Efficiency cores at USER_INITIATED priority and suddenly your latency numbers spike 10x on systems with asymmetric cores. I remember solving a particularly bad one which was basically doubling our request latency on phones with E cores.
The company had a pretty widely spread internal article trying to whack people over the head to stop abusing lock primitives in this way, but we just kept shipping code with this issue.
(Most of the inversion issues came from the use of semaphores though. The problem got 1000x worse in swift concurrency because using semaphores blocks an entire SC OS thread and you only get as many of those as you have cores. Most Apple Watches and HomePod only have 2 of them so you can easily deadlock. Which most people fixed by just… adding a timeout to their locks. It was horrifying.)
It sounds like this is relevant when developing user app code, not just the kernel or core libraries. Is there an external version of this article? I would be very interested to read more.
let valueIWant: String? = nil
let sem = DispatchSemaphore(value: 0)
someAsyncFunction() { result in
// this is called in another thread
valueIWant = result
sem.signal()
}
sem.wait()
assert(valueIWant != nil)
Note, this is mostly about semaphores, so it’s a bit offtopic from the original discussion here which is about spinlocks. But basically, never lock something in expectation of another thread unlocking it. Since semaphores are ownerless, the scheduler has no idea what thread will eventually signal the semaphore, so it can’t boost the priority of any threads you’re waiting on.Not to mention the thread explosion issue: If the task running the completion (ie. signal()) is submitted to a libdispatch queue, the thread pool implementation will spawn more threads if all of them are starved, to eliminate deadlocks, which can lead to thread explosion in addition to the priority inversion issue. This advice dates back to when libdispatch was invented (and the internal article was called The Semaphore Antipattern…)
But with Swift Concurrency it’s far, far worse, because the SC thread pool does not spawn new threads if all of them are blocked. Meaning the dispatch block that’s supposed to call the callback may never get run, and you deadlock. Most importantly, this is true even of plain ObjC libdispatch code written 15 years ago: If some ancient framework you’re calling into does the semaphore antipattern, libdispatch is allowed to assume that all Swift Concurrency threads will eventually make forward progress, and so it doesn’t spawn new threads to handle the work, even if all threads are blocked. So ancient code that uses this antipattern suddenly blows up if someone calls it (transitively!) from a swift concurrency context. I’ve squashed countless bugs on this issue alone. (I wrote my own article on this internally too, titled something like “Semaphore abuse: How to deadlock your process and require a device reboot”)
IMHO, the semaphore should be officially marked deprecated and trigger warnings… there are no appropriate uses for it. If you’re in a synchronous context and need to block on the result of async code, the best bet is to stop what you’re doing and file a bug to the people writing the async code and tell them to give you a synchronous API (or refactor your code to be async.) Never ever use semaphores to block on async code. Not even once.
Also I found another reference to that internal post here https://cohost.org/Catfish-Man/post/913314-a-love-letter-to-...
Basically people recommend os_unfair_lock because of what it can’t do.
Bare spinlocks are very bad in this way, unless you have dedicated hardware threads (with SMT you can pin all but one of the threads with the remaining thread being general purpose, though you may want a way to inform the scheduler which cores to currently prefer due to their pinned tasks being more idle).
This is something I've thinking about a lot over time, that the CAS is only there to atomically determine if there are any sleeping waiters on unlock and you have to do a futex_wake. I would really want some way to get away with non-fenced operations (at least on x86), but I don't know if it's just that nobody has figured out why, or there is a fundamental reason why that's not possible.
I think the issue is that if you ask the CPU to just store something (like in a spin lock), whether or not there’s a fence, it’s an operation with limited data flow dependencies so it’s easy for the CPU to execute. Even the fence can be handled using wacky speculation tricks.
But if you want to do something like, “store this value but only if the old value satisfies some predicate”, then there’s a load and the whole thing is dependent on the load. So you’re asking the CPU to load, then run a predicate, then store, and for that to be fenced, and atomic.
Strictly more work. I don’t think there’s any trick to make it faster than just the store release.
Well yes but on x86 that comes for free. The overhead of the full fence brought in by lock cmpxchg or lock xchg is in the order of ~10ns, which for an uncontended lock means that a mutex is almost 2x as slow as a spinlock.
A load acquire + store release would be a couple of ns (assuming everything in L1 etc...)
Consider the implementation of Dekker's algorithm for example.
[1] https://www.cs.bgu.ac.il/~hendlerd/papers/p168-expensiveSync...
This relaxed-load-CAS, coupled with some form of control or data dependency would be sufficient to implement your mutex. But would such a CAS be significantly cheaper than the existing CAS? If it was, you would be able to approximate the strong CAS semantics by adding lfence+sfence after the relaxed CAS. These fences are cheap, so if strong CAS was possible to be implemented this way with significant improvements, intel would have already done it.
Finally, it is practically possible to implement the sequence store(A);#StoreLoad;load (B) without an explicit fence by using the colocation trick: have A and B be adjacent in memory (on the same cacheline), store to A, then do a wider load on both A and B. Intel does not give multithread guarantees on this, but my understanding is that it works: the wider load fails to be store-forwarded and stalls the pipeline waiting for the previous store to be flushed. In practice this costs about as much as a fence, so in addition to being undefined, is not cheaper.
- On the wait side, do the CAS to set the "waiter present" bit. Down unlock, do a (relaxed) read of the lock word, and if "waiter present" isn't set, just do a release store to unlock (and go down some slow CAS-y wake path if a waiter is present). On the wait side, never do an un-timed futex wait; just do a series of timed waits, with increasing wait times (so that you still eventually fix things if you hit the unlucky race between the previous holder's check+store sequence). (You can also do some tricks with counters to let waiters do an unconditional sleep once they get their wait acknowledged).
- Split out the "waiter present" bit into its own byte, do a store-load sequence (with just a compiler reordering fence) to check for waiters, and have waiters either do a membarrier() syscall or wait "long enough" that they're sure they've gotten the same effect. (This gets tricky w.r.t. mutex lifetime though; you either need out of band lifetime knowledge or to use RCU or whatever and indirect through pointers).
Practically, neither was ever "better enough" for anything but microbenchmarks to be worth the complexity.
If you are doing this, given the cost of membarrier, you are optimizing for almost always uncontended locks. At this point you can make your lock default-owned by the first thread to lock it and have the owner lock and unlock be basically free until it is contended. This is basically the biased locking optimization that Java implements (or used to).
You don't necessarily want a biased lock for all this kind of stuff, because "sparsely contended" doesn't necessarily imply thread-associated. E.g. one place I was looking at this for was locks for pages of virtual memory in a heap; no thread "owns" any given heap page, but it was very uncommon to get unlucky and have two threads touching adjacent pages at the exact same time. These kind of "sloppy mutexes" get half the fast-path speedup of biased locks but without the heavily asymmetric performance costs. (At least, that was the theory; like I said it didn't really pan out to be that useful in practice).
Assuming `sched_yield` does something.
There's a futex congestion problem inside Wine's memory allocator. There are several levels of locks. If you're growing a buffer, in the sense of C's "realloc", and no buffer is available, memory allocation is locked during the allocation of a bigger buffer, copying of the contents, and release of the old buffer. "Push" type operations can force this. Two orders of magnitude performance drops ensue when multi-threaded programs are contending for that lock.[1]
Inside one of the lock loops is a call to "YieldProcessor".
static void spin_lock( LONG *lock )
{
while (InterlockedCompareExchange( lock, -1, 0 ))
YieldProcessor();
}
But the actual code for YieldProcessor is a NOP on x86:[2] static FORCEINLINE void YieldProcessor(void)
{
#ifdef __GNUC__
#if defined(__i386__) || defined(__x86_64__)
__asm__ __volatile__( "rep; nop" : : : "memory" );
#elif defined(__arm__) || defined(__aarch64__)
__asm__ __volatile__( "dmb ishst\n\tyield" : : : "memory" );
#else
__asm__ __volatile__( "" : : : "memory" );
#endif
#endif
}
}Wine devs are aware of this, but the mess is bad enough that no one has tackled it. This is down in the core of what "malloc" calls, so changes there could have unexpected effects on many programs. Needs attention from someone really into mutexes.
[1] https://forum.winehq.org/viewtopic.php?t=37688
[2] https://gitlab.winehq.org/wine/wine/-/blob/HEAD/include/winn...
Spinning on the CMPXCHG is also a bad idea. You should spin on the read and only then attempt the CMPXCHG.
You care about exchange vs read/load because of cache line ownership. Every time you try to do the exchange, the attempting CPU must take exclusive ownership of the cacheline (stealing it from the lock owner). To unlock, the lock owner must take it back.
If the attempting CPU instead only reads, the line ownership stays with the lock holder and unlock is cheaper. In general you want cache line ownership to change hands as few times as possible.
https://github.com/google/nsync/blob/c6205171f084c0d3ce3ff51...
Works fine on Microsoft Windows. Only fails on Wine.
OTOH, the usual way to lock via a busy loop/spin, does require some attempts then backoff with a random duration.
> __asm__ __volatile__( "rep; nop" : : : "memory" );
It might look like a NOP, but "REP NOP" is not a real NOP, it's the PAUSE instruction (which very old processors from the 1990s treated as a normal NOP).
I don't think this is more expensive than release certainly not because of the line where the write goes in most cache coherency protocols.
Granted this lock does wake up too many people but you did say usually uncontended.
That'll be hella slow
That syscall will be worse than a CAS just because it’s a syscall. Not to mention it’ll have to lock some kernel data structure just to figure out that there aren’t any threads to wake.
There are three states of the mutex: locked=1, unlocked=0, and sleeping=2. A thread comes along to a locked mutex, and atomically moves it to sleeping and sleeps via futex. The freeing thread unconditionally writes 0 and atomically sees the old value: if 2 wake all, if 1 no need to wake anybody.
Maybe that is equally expensive to a CAS, but I don't think it ultimately is.
Atomic RMW is almost as expensive as CAS. Exactly as expensive as CAS on some cpus.
Shouldn't you rather use pause instructions (_mm_pause, __yield, ISB, etc.) instead of thread switching? That's what I have seen in most spin lock implementations. Maybe it depends on the use case?
unbiasing/re-biasing a lock can be quite heavy, though. JVM did it by pausing threads (or waiting for GC to do so)
> uses an optimistic CAS (compare and swap) immediately, so that locking happens quickly when there's no contention