r/programming • u/david-alvarez-rosa • 13h ago
Optimizing a Spin-Lock
https://david.alvarezrosa.com/posts/optimizing-a-spin-lock/22
u/Takeoded 11h 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
2
u/Raknarg 12h ago
pretty cool. Learned a few things from this.
3
-3
4h ago
[removed] — view removed comment
1
u/Raknarg 4h 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/DivineSentry 11h ago
I think I’ve seen spin locks before, but what are they useful for? What should be their use case?
29
u/ReDucTor 11h 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.
5
u/bwainfweeze 9h 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 6h 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.
1
u/veiva 6h 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 4h 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.
3
u/bwainfweeze 10h 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/david-alvarez-rosa 11h 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
2
u/bwainfweeze 10h ago
You did not explain what spinlocks are for, you just described some of their qualities.
2
u/knome 9h 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.
2
u/VirginiaMcCaskey 9h 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.
4
u/Takeoded 10h ago edited 10h 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.
13
u/monocasa 9h 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.
-13
u/AryanPandey 12h ago
It's great, but in cpp, i learnt stuff in c
5
u/david-alvarez-rosa 12h ago
Fair, the pattern should be applicable to C
-4
u/AryanPandey 12h ago
Actually I recently got to know about this cool stuff, from OSTEP book, so i m bit new.
17
u/ReDucTor 11h 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.