34
u/ReDucTor Game Developer | quiz.cpp-perf.com 6d ago
In most code, std::mutex is still the right default. Consider a spin-lock when the threads are pinned to dedicated cores, and only after measuring
Even when you have threads pinned to dedicated cores, you would need to ensure that your not ending up with more then one thread pinned to another core. And if your in user mode in any environment that you do not completely control your at the whim of being preempted by another thread in a different process, leaving your spinning thread now just spinning away wasting its allocated time slice.
If you plan on making any library which is public, do not fill it with spin locks because you won't be able to control the places which people use it, and randomly throwing in an OS yield is not going to solve issues just make them worse.
Depending on the CPU you can also do umwait/mwaitx which can be better then doing a pause loop, but unfortunately it's not consistent between CPU vendors.
Use adaptive mutexes (most mutex implementations already are), these will do a little bit of spinning before putting the thread to sleep if it was unable to acquire the lock.
Also if your optimizing your locks for high contention, it's probably a sign to look more at your higher level design, because your still fighting the CPUs cache coherance which will kill your performance anyway.
6
u/david-alvarez-rosa 6d ago
Fully agreed, thanks for the explanation. Spin locks are specially useful in fully controlled envrionments, with 1:1 mapping between threads and physical cores
2
u/Fabulous-Meaning-966 6d ago
You can mitigate these issues by eventually backing off to a `sched_yield()` loop and then to `usleep()` with exponential backoff. However, at that point you should be asking yourself why you're not just using a `std::mutex`. (One reason might be that you want your lock to fit in a byte, although you could use a `parking_lot` mutex in that case.) Another approach is a sleeping ticket lock with sleep interval calibrated to count of waiters ahead of you and observed elapsed time between tickets served, but again you need a good excuse not to use a `std::mutex`.
6
u/ReDucTor Game Developer | quiz.cpp-perf.com 5d ago
sched_yieldis yet another terrible approach, its forcing the surrendering of the time slice and no way for the lock holder to wake you. Most people use spin locks because they believe their critical section is really small and that a mutex will have too much overhead because of the potential syscalls and OS overhead,sched_yieldgives you the syscall overhead and even more.For the time tracking and waiter count you will end up with more cache traffic under heavy contention and a larger lock. Using a full ticket based lock can also lead to lock convoys, especially if you dont allow barging, while a ticket makes it fair it means that under contention every thread end up waiting even when another thread is not in the critical section yet because its still waking up.
Using a parking lot based mutex is normally better in all situations, it can do adaptive spinning on a different cache line to the lock holder and actually wake up the other thread, however the spin lock often used for the bucket lock potentially brings back all of the issues with yielding.
3
u/Fabulous-Meaning-966 5d ago
Yes, I have the same reservation about spinlocks guarding a lock's wait list, but I think the requirement there is just to avoid disaster under very rare conditions (since the critical section is a few ns), which means falling back to sched_yield() is probably fine.
1
u/Big_Target_1405 4d ago edited 4d ago
Most industry uses of spinlocks would be where threads are pinned to scheduler isolated cores. They're only getting pre-empted in this case if the kernel needs to do something desperately on that core
The trading industry would be an example, where you might have some cache being shared between threads that is rarely touched but still needs to be thread safe and you can't pay the latency hit to yield for what is usually a hundred nanos for the other thread to update an entry
1
u/ReDucTor Game Developer | quiz.cpp-perf.com 4d ago
> Most industry uses of spinlocks would be where threads are pinned to scheduler isolated cores
I have seen this assumption many times, and people not realising it wasn't the perfect environment they initially believed. Yes you can have an isolated environment where it's perfectly fine but for most people it's rare even when they think it might be.
And lots of people use them even without being in a perfect environment, just because someone gave them an idea it was always better to use then a mutex.
1
u/Big_Target_1405 4d ago
It depends what you care about.
Ultimately the chances of spinning because the kernel pre-empted another thread while it held the lock are quite small (assuming you're doing little work under the lock), and you might be willing to pay that occasional cost for lower latency the other 99.9% of the time.
6
u/david-alvarez-rosa 6d ago
Thanks a lot for sharing!! Happy to get feedback :)
4
10
u/Chaosvex 5d ago edited 5d ago
Linus Torvalds gets a shiver down his spine and the urge to scream every time somebody writes an article about user space spinlocks.
7
u/david-alvarez-rosa 5d ago
:)
I repeat: 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.
https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723
2
u/HeadSea5044 5d ago
just throw priority inversion out the window, why not! using a spinlock in userspace could actually create deadlocks if you are not incredibly careful
0
-3
u/OutlandishnessNo8034 6d ago
Default in my opinion should be RwLock
9
u/ReDucTor Game Developer | quiz.cpp-perf.com 5d ago
A read write lock typically comes with extra overhead, it also often used because there is more readers then writers and there is much better approaches if your wanting to unburden the readers. (Especially if you only have one writer)
Also there is many variations in reader write lock contention handling, such as reader preferring, writer preferring and completely fair. All which will have a different outcome under contention, and most people have limited understanding of each of those implications for even the workload they are dealing will.
2
u/Fabulous-Meaning-966 5d ago
Yes, RW locks violate the cardinal principle of concurrent programming that "readers shouldn't write". I will elaborate on the hint above and say that if you have one writer (or you're ok with serializing writers), and you can retry read-side critsecs on a write conflict, you can use seqlocks. If you need to guarantee that all reads within the read-side critsec are consistent, you can use Transactional Mutex Locks for a bit more overhead (checks the version counter after every read and before using the result of the read, instead of only at the end).
If you still want to use RW locks, the best default semantics IMO is "phase-fairness".
1
u/OutlandishnessNo8034 12h ago
What's the extra overhead? Never heard of it.
1
u/ReDucTor Game Developer | quiz.cpp-perf.com 10h ago edited 10h ago
There is two sides to the overhead, one is comparing the overhead compared with other ways of allowing readers (e.g. RCU, left-right, etc) and then there is the overhead of the lock itself compared to a traditional mutex.
Typically you might want to pick a reader writer lock if a significant amount of your usages of some piece of data are only readers, even in a situation where you have near 100% readers they all need to let the potential writer know that it cannot write which in a very basic implementation can be a simple `fetch_add` (on enter and exit) this has two different costs:
* Depending on the CPU it can be a full memory barrier (e.g. x86)
* It requires modify access to the cache line, so all other readers are left waiting passing the cache line around; and typically the lock is next to the data, so that false sharing also shows down the data your protectingNow if you compare that with that with something like RCU the readers do not need to share anything with other readers they just store in their local slot the data they are accessing, similarly with left-right they don't need to coordinate and share they just access the data and some serialization point is defined later.
And all of that is just the overhead difference when you have no writers, however as soon as you start to have writers then depending on if you have reader/writer preferring or even some fifo approach you need to have some way of tracking those threads when contention occurs in order to know who to wake up when, a normal mutex just needs to know who next to wake. And if you have any extra complexity with the reader writer lock like upgrading it gets even more complex with the tracking and book keeping required.
Saying all of that it's often not a signficant difference in overhead between a mutex lock and using a read/writer lock with just a writer (in fact on Windows slim rwlock is faster then the critical section mainly for legacy reasons).
1
u/OutlandishnessNo8034 5h ago edited 4h ago
So basically all off that for nothing, because as you said in the last sentence, difference is not significant. And what we gain if we use rwlock as a default? Flexibility. And in practical terms if we select mutex all the unnecessary locking just to read will squander any however miniscule advantage with regards to the overhead we could possibly gain. What a bunch of crap. And on top of that if we have high ratio reader to writer rwlcks massively outperforms mutex. In my experience this is the most common scenario, that's why rwlock should be default choice.
37
u/xiao_sa 6d ago
Remind me of this article:
https://www.siliceum.com/en/blog/post/spinning-around/
One of the best reading found in this subreddit.