Optimizing a Spin-Lock
david.alvarezrosa.com
david.alvarezrosa.com
The real world story for locks is usually that you're not rage-contending 100% of the time, but that you have some contention combined with CPUs doing some real work and some real memory accesses.
What I've found is that in those more real scenarios, the locks that perform best in microbenchmarks fall apart compared to completely different and unexpected algorithms.
My own programming experience is mostly Python, so throughout the most of my career I treated locks as pure magic and didn't think much about what happens under the hood.
At some point in my life I became interested in Rust and lower-level programming and this article in particular really helped me to set my head straight on this topic. It doesn't only explain how concurrency primitives actually work, but it also explains why they work this way, what choices and trade-offs are involved.
This article uses C++ for all examples, but there are really nothing language specific, all principles will work in Rust, C, Zig etc
[0] https://travisdowns.github.io/blog/2020/07/06/concurrency-co...
[1] https://travisdowns.github.io/
[2] https://hn.algolia.com/?q=https%3A%2F%2Ftravisdowns.github.i...
I was always told that they were an anti-pattern, and I think that generally that is a pretty good rule of thumb, but I guess like most stuff in CS: there are always exceptions to "good rules of thumb".
I still haven't actually explicitly written a spinlock for anything in production, but Disruptor has shown me that there are cases for it.
> Use a lock where you tell the system that you're waiting for the lock, and where the unlocking thread will let you know when it's done, so that the scheduler can actually work with you, instead of (randomly) working against you.
I have “implemented” a sleep lock in xv6. Is it what he meant? What does the Linux scheduler “know” about it and will do differently? (Trying to figure out what does “work with you” mean)
Thanks in advance.
If the OS knows that a thread is waiting for a lock, the scheduler will not bother to schedule it until the lock is available.
In general, it’s tempting when you’re bound by lock latency to skip the syscall overhead of sleeping. But a lot of the time that’s a code smell that there are other inefficiencies in the system and you should rethink how you’re scheduling work.
A bit like what classic UNIX does with wchan, but between the kernel and userspace this time. Related: https://rdmsr.github.io/writing/turnstiles/
I can't be the only one who learned this the hard way by cramming too many vCPUs onto too few physical cores and initially wondering where the high load and latencies came from.
Go stdlib sync.Mutex uses spins: https://victoriametrics.com/blog/go-sync-mutex / https://archive.vn/BIb7F
Though it's true you can end up with the same end result, in that you can just keep trying the operation until you accidentally do a read-modify-write that's ended up - well, "atomic" is a valid way to describe it.
So maybe it is good enough to count, though personally I'm still not quite convinced.
> Load-link returns the current value of a memory location, while a subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link. Together, this implements a lock-free, atomic, read–modify–write operation.
Entering the kernel with a futex wait or wake under contention costs a couple of microseconds, whereas a spinlock will cost you double digit to low triple digit nanos depending on cores/sockets etc
If you have futexes you can try to grab a lock with an atomic operation and if that fails, go wait on the futex via system call, so there is no need to spin. Spinlocks then remain useful as an optimization, because there are situations in which it is cheaper to spin around a bunch of times until the thread on another processor gives up the lock, than to take a trip into the kernel.
You can also spin, but with a scheduler yield in the loop; we don't normally think of that as a spinlock. That's what you fall back on after spinning some number of times and failing to get the lock.
In the Linux kernel, spinlocks are the low level primitive. They are very efficient because unlike user space threading, they are not faced with guesswork about scheduling. They are "surgical".
Bring a wind turbine with you because the laughing will be quite intense…
At the level I work (which is generally server/distributed stuff), I have always used mutexes that are built into the platform.
Or more realistically, if I am the one writing the code, I just avoid mutexes and make my code ridiculously convoluted to do so.
Note that I don't recommend spinlock for most cases, only when there is a 1:1 mapping between threads and phsycal CPU cores, and only after measuring
And in this all-cores-busy case, do you want your waiters burning one of those precious cores while lock holders are preempted? If you care enough about your system design to even affirmatively select spinlocks in the first place, you should probably also care enough to not use them in preemptible userspace. Or at least, I am not aware of any reasonable usecase. Hybrid sleeplocks are fine, of course.
auto lock() noexcept -> void {
auto backoff = 1;
do {
while (locked_.load(std::memory_order_relaxed)) {
for (auto i = 0; i < backoff; ++i) _mm_pause();
backoff = backoff < 64 ? backoff << 1 : 64;
}
} while (locked_.exchange(true, std::memory_order_acquire);
}In a FIFO threads register themselves into a linked list, and the thread calling unlock() directly wakes the next. It's possible to have e.g. 20 threads in this case all spinning on their own cache lines (their private node), rather than a shared one (the lock head).
This can be coherence protocol optimal.
A dumb test and set spinlock, or variant thereof, is going to degrade quickly as all the cores are spinning on the same cacheline causing a lot of coherence traffic between cores (transitions between shared, exclusive and modified states)