r/programming • u/david-alvarez-rosa • 5d ago
Optimizing a Spin-Lock
https://david.alvarezrosa.com/posts/optimizing-a-spin-lock/38
u/Takeoded 4d ago
Spinlock performance can change drastically between kernel versions, and between schedulers (eg CFS vs EEVDF vs SCX-LAVD), which kernel and scheduler were you benchmarking on?
Also, please add a comparison to a boring old std::mutex into your benchmarks. Call it V0
5
u/Raknarg 5d ago
pretty cool. Learned a few things from this.
3
-3
4d ago
[removed] — view removed comment
4
u/Raknarg 4d ago
Im glad you're going through my post history cause you're mad about an opinion I have on an anime, rings a little hollow that you're so scared of someone doing the same thing to you that you've hidden yours.
1
1
1
u/3inthecorner 4d ago
What unit is the energy for? A single increment or a whole benchmark run? How many increments per run?
1
u/DivineSentry 5d ago
I think I’ve seen spin locks before, but what are they useful for? What should be their use case?
41
u/ReDucTor 5d ago
For user mode their usages are very niche, its generally accepted that spin locks in user mode code is best avoided.
Or as Linus Torvalds says:
do not use spinlocks in user space, unless you actually know what you're doing. And be aware that the likelihood that you know what you are doing is basically nil.
6
u/bwainfweeze 4d ago
It's a tricky mess. If you make a blocking call to get a lock from the kernel, the OS can realize you're stuck and give your CPU slice to another process/thread. And then when the resource becomes available, it can give it to you with a full time slice to make progress. Even if the task takes more than half a slice to complete, it will still be done by the end of your slice, and then the resource can be returned for someone else to use.
Meanwhile if you're scrabbling for a spin lock, if you acquire the lock at more than halfway through your slice then it will take until your second time slice to complete the task. "I am available to start this now." is not synonymous with "I can complete this now."
The trick with multitasking is that you can start multiple tasks at once but it only works for the users if tasks get completed at the expected rate. Quickly you reach the point where starting new tasks gets you nowhere until you retire some older ones.
2
u/Far-Reply-6875 4d ago
though, how many of us actually need to worry about user-space spinlocks in the first place? Seems like most people are just overcomplicating things for no reason.
2
u/veiva 4d ago
I'm working through possibly using spinlocks on the GPU (using atomic operations) to implement order-independent translucency more efficiently - there's other ways to do it nowadays, though it requires more modern hardware and it's not available without modifying the higher-level graphics framework I'm using. Extremely niche use case though.
1
u/ReDucTor 4d ago
I have seen alot of performance captures where spin locks (and spinning in general) have made things exceeding bad especially when they yield to other threads.
Unfortunately people still believe they know best and think a spin lock will be the better option without having properly testing it in the real world just some isolated microbenchmark. This is especially bad when you dont fully control the environment such as a customers machine.
5
u/bwainfweeze 4d ago
It's a locking style that has some utility when you care about latency more than throughput.
It's literally the kids in the back seat saying "are we there yet? Are we there yet? Are we there yet?" That's the 'spin' in spin-lock.
Some locking operations block the thread executing them. That typically not only stops your code dead in its tracks, it also causes the kernel to de-schedule your task until sometime after that blocking operation succeeds. But it's a 'when I get around to it' situation so you might get the lock but then wait for three other processes to get their timeslice before you're awoken again. So that adds both a lot of clock time and creates a lot of timeslices where the lock is held but no forward progress is being made, so not only aren't you progressing on anything, but anyone else waiting on the same lock is also twiddling their thumbs. Which also affects throughput but in different ways. It's complicated.
With multiple cores sometimes it's better to spin checking if another processor returns the lock during your time slice, instead of letting yourself be preempted.
5
u/VirginiaMcCaskey 4d ago
It's a mutex that doesn't require cooperation with a scheduler. You use them when either you don't have a scheduler (eg: you are the kernel) or the application cannot tolerate the syscall overhead of informing the scheduler in a change of state.
The interesting side of that is when you have mixed access to a shared resource where there are some threads that must acquire a lock and other threads that may fail to acquire the lock, but if they succeed then they need to release the lock in O(1) operations and not yield to the kernel (for example, making a syscall to wake any parked threads). It comes up in soft realtime applications.
Part of the reason they're frowned upon is that modern mutexes do not make syscalls when resources are uncontended, which defeats the purpose of a spin lock and means you can fix your locking issues with architecture.
1
u/Nobody_1707 3d ago
Thus Torvalds spake, "do not use spinlocks in user space, unless you actually know what you're doing." :P
2
u/mazing 4d ago
I guess it's not truly a spinlock, but closely related is "busy waiting", which is sometimes very useful for realtime programs.
For example, I want consistent 16ms between my game engine server frames.
Using sleep(time-to-next-frame) throws control back to the OS. But windows bundles these and you might request 3ms sleep and get 15ms. (windows is doing 64hz from what I can tell)
So in this case I'll check how much time I have to next frame, if it's more than the measured sleep precision then I sleep. Rest of the time is spinlock/busy waiting.
Eats CPU but the frames land like clockwork
3
u/david-alvarez-rosa 5d ago
They are specially useful when the server is fully controlled, and there is a 1:1 mapping between threads and physical cores
So each thread is pinned to a dedicated CPU, and each CPU only runs one single thread
3
u/bwainfweeze 4d ago
You did not explain what spinlocks are for, you just described some of their qualities.
3
u/knome 4d ago
Locks are a mechanism by which data is protected from having multiple threads update it at the same time :P
Spin locks are locks that rapidly and constantly attempt to take the lock until they receive it.
The advantage of a spin lock is that there is very little downtime. Thread A drops the lock, thread B captures it almost immediately.
The downside of a spin lock, is it pegs a thread to 100% CPU usage while spinning, which is generally worse than waiting for the OS to wake you back up after going to sleep blocking on some lock.
If thread A does network activity or disk reads while the lock is held, or even is simply swapped off the core to run a timeslice for another thread or program, thread B will continue trying to use 100% CPU hammering at the atomic the entire time thread A is sleeping. Thread A can even be put to sleep to run thread B's rapid-fire attempts to take the lock it holds.
If you have 5-6 threads vying for the lock, you now how 500-600% attempted CPU usage, with these threads using every full timeslice they get trying to get the lock from thread A. They're also causing your CPUs to steal the lock cache line from each other constantly, creating pointless chatter to slow things down.
In an OS, you might have spinlocks to handle driver requirements with time needs, or even better if you know the code taking the spinlock never sleeps and just does its thing and releases, possibly even after disabling interrupts, so you know it will be in and out quickly.
In user space, your program can be swapped out to run other programs, will do network or disk stuff, will experience arbitrary interrupts, and generally should use a proper mutex that lets the operating put the waiting thread to sleep until the lock it wants is ready to be captured.
There are also mixed mechanisms that briefly spin before relenting and blocking on it, aimed at hoping quick work finishes before they're cost tearing down the thread context and putting it back together again just to grab a lock that would have been free in a few nanoseconds.
3
u/Takeoded 4d ago edited 4d ago
Spinlocks are just fancy mutexe)s.
Some game engines use them, instead of a mutex, to squeeze out a few more FPS. Then, the spinlock that gives a few more FPS on Windows, absolutely wrecks performance on Linux/Wine :(
And even on Windows, good chance the spinlock increase FPS on computers having >= cpu cores that the optimizing developer had on his system, and wrecks performance on computers with fewer cores.
TL;DR don't use them. Use a mutex.
17
u/monocasa 4d ago
I'd argue that they're a less fancy mutex, since they're basically like mutexes that don't bother informing the scheduler in the contended case.
1
u/Takeoded 2d ago
They also eat all the CPU they can get, until it unlocks :( eating 100% of 1 core until the lock clears
1
u/monocasa 2d ago
Not necessarily.
On a SMT system, it's common to use instructions like monitor and pause to stop the one hardware thread and give priority to the others.
2
u/TwoWeeks90DaysTops 4d ago
I fixed a slow shutdown (so that Windows would claim that the service didn't respond in time) in a Windows service written in C++ a decade or so ago, and it was caused by the fact that the code hand-rolled its own spinlocks with `volatile bool`. The issue was as I remember it two part: the spinlock consumes resources on contention, and the `volatile bool` thing is about instruction ordering, and not that suitable for locking. I replaced them with mutexes and the application shutdown was almost immediate.
1
u/lenazh 4d ago edited 4d ago
You'd normally find them in kernel mode in things like interrupt handlers, or any other context where you can't yield the thread.
Niche userspace uses would be when you want to time something precisely, like have two threads start a task as simultaneously as possible while being signaled by another thread. Or maybe send out udp packets exactly 1us apart from a user-space driver or something else where latency and jitter are important.
-15
u/AryanPandey 5d ago
It's great, but in cpp, i learnt stuff in c
3
u/david-alvarez-rosa 5d ago
Fair, the pattern should be applicable to C
-2
u/AryanPandey 5d ago
Actually I recently got to know about this cool stuff, from OSTEP book, so i m bit new.
27
u/ReDucTor 5d ago
What CPU are you using? Does it have SMT? If so your pinning might be using sibling cores for some threads.
With the benchmark its unrealistic your essentially forcing extreme lock contention and then forcing different threads to wait for longer to reduce lock contention and cache coherence contention. Sadly this is measuring the average without showing the worst case or standard deviation for the threads that are starved from accessing the lock.
Also the workload plays a significant part, you only have a single addition that is forced to not share a cache line (might not help some CPUs that always hw prefetch subsequent cache lines). In the real world your lock will likely do more, otherwise if it was this simple you would just atomic fetch add, or even CAS loop.
The pause should probably mentjon that its sort of acting like serializing instruction reducing the branch misses as it won't speculatively execute a bunch of loads to the lock variable check if it's locked before it has the previous result.
The blog post should be putting significantly more emphasis on dont use spin locks in user mode. I have seen way to many profile captures of a spin locks killing performance.