Rendered at 12:14:15 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
DmitryOlshansky 3 minutes ago [-]
I think one area where spinlock could be useful is fibers. There you have an option to schedule another fiber instead of spinning CPU until timeslice runs out.
pizlonator 12 hours ago [-]
Super dangerous to benchmark lock performance using microbenchmarks. If you have a tiny benchmark, then you're putting the CPU and memory into a very specific and unusual state (everything is quiet other than the lock itself).
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.
neeeeees 9 hours ago [-]
To repurpose a famous quote - all benchmarks are wrong, but some are useful
vova_hn2 6 hours ago [-]
I want to share an excellent related article, "A Concurrency Cost Hierarchy" [0] by Travis Downs [1]. It was posted to HN many times [2], the largest discussion has 26 comments [3].
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
I genuinely had not heard of anyone actually using a spinlock in production code until I started using LMAX Disruptor a few years ago.
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.
kazinator 11 hours ago [-]
Before we had futexes in the Linux kernel, spinlocks were used to boostrap the implementation of everything else in the user space threading library.
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".
bob1029 14 hours ago [-]
To be really pedantic, it's a spin wait, not a spin lock in disruptor. You are waiting for a sequence, not mutually excluding some resource. Many threads can watch the same volatile at the same time without blocking each other.
nly 13 hours ago [-]
If you have an application where your threads are pinned to dedicated cores, and those cores are all isolated from general OS scheduling, then it's the lowest latency means to synchronize arbitrary things between threads
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
BobbyTables2 9 hours ago [-]
Tell a kernel developer that spin locks aren’t for production code.
Bring a wind turbine with you because the laughing will be quite intense…
yxhuvud 8 hours ago [-]
Very different situation as stuff inside the kernel presumably cannot be preeempted at any time. Preemption does a number on spinlocks.
tombert 8 hours ago [-]
Totally fair. I haven’t done much kernel stuff (outside of very basic toy stuff for QEMU).
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.
loeg 7 hours ago [-]
Kernel can prevent preemption (mostly). Userspace can not (mostly).
ChickeNES 9 hours ago [-]
Heh, I lost it myself when reading it, so you're not wrong.
Thanks for sharing. Can someone tell me what does this paragraph mean?
> 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.
moregrist 11 hours ago [-]
In simplest terms: if you don’t tell the kernel that you’re waiting, the scheduler assumes you aren’t and will wake you up and let you spin, to the detriment of other threads that aren’t waiting.
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.
rcxdude 4 hours ago [-]
The basic idea is that a lock should be something the OS is aware of, so that while a thread is blocked on a lock, the scheduler never tries to wake it at all, and when it is unlocked, the scheduler can wake up the thread that's waiting on it immediately. If the scheduler isn't aware of the lock, it'll just try to wake up the thread periodically, often just wasting CPU when it's still blocked or kept asleep when it could be running.
pamcake 10 hours ago [-]
> Note that even OS kernels can have this issue - imagine what happens in virtualized environments with overcommitted physical CPU's scheduled by a hypervisor as virtual CPU's? Yeah - exactly. Don't do that. Or at least be aware of it, and have some virtualization-aware paravirtualized spinlock so that you can tell the hypervisor that "hey, don't do that to me right now, I'm in a critical region".
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.
sedatk 15 hours ago [-]
It’s one of the secret ingredients to avoid a Big Kernel Lock™.
foldr 3 hours ago [-]
One use case I’ve found is for a lock that you don’t need to acquire. For example, you need a lock to read a cache entry, but if you can’t acquire the lock after a few spins, you can just proceed without the cache. For fine-grained locking, a spin lock can have a significantly lower memory overhead than a full futex.
ignoramous 14 hours ago [-]
> had not heard of anyone actually using a spinlock in production code
Optimistically spinning for a bit before falling back to futex or equivalent is very different from a spinlock.
mathisfun123 14 hours ago [-]
not all architectures have atomic cas
loeg 13 hours ago [-]
Real architectures you'd run more than a single thread on? Such as?
tom_ 11 hours ago [-]
Quad core ARMv8-A, e.g., Nintendo Switch.
loeg 7 hours ago [-]
ARMv8-A has atomic CAS, unless this is some silly definition thing where it's "a system that has the behavior of atomic CAS but is named something else."
tom_ 53 minutes ago [-]
Maybe that's the trap I'm falling into? From memory it doesn't have any actually atomic operations, only an ll/sc sort of mechanism - which I've never really thought of as an atomic operation?
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.
monster_truck 4 hours ago [-]
I don't think that came until 8.1
dalvrosa 3 days ago [-]
Thanks for sharing! Happy to get feedback :)
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
loeg 13 hours ago [-]
Spinlocks are unsuitable for situations where you can be involuntarily context switched (the vast majority of userspace programs). Probably worth mentioning that.
josefx 3 hours ago [-]
Unsuitable? Probably depends on your use case. Even a normal end user system shouldn't constantly kick your threads out unless it has enough other things to do to to keep every core busy.
RossBencina 9 hours ago [-]
TFA mentions power usage from a dollar cost perspective, but there is also the thermal aspect. You do not want to trigger thermal throttling (or lose boost) while doing almost nothing.
gavinlilly 13 hours ago [-]
If contention is expected, would it be better to first perform a relaxed read before the exchange? For example:
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);
}
nly 13 hours ago [-]
If you're expecting heavy contention, and there's no risk of any of the threads being descheduled, then FIFO spinlocks are probably best.
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)
jeffbee 14 hours ago [-]
This would have different answers depending on if it ran on a machine with a more closely-shared cache, right? For example on an Intel efficiency core cluster where 4 cores share an L2.
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...
[3] https://news.ycombinator.com/item?id=24489829
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.
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".
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
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.
> 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.
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.
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
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)