6 ms·
Always cool to see new mutex implementations and shootouts between them, but I don’t like how this one is benchmarked. Looks like a microbenchmark. Most of us
by pizlonator 2y ago
Always cool to see new mutex implementations and shootouts between them, but I don’t like how this one is benchmarked. Looks like a microbenchmark.
Most of us who ship fast locks use very large multithreaded programs as our primary way of testing performance. The things that make a mutex fast or slow seem to be different for complex workloads with varied critical section length, varied numbers of threads contending, and varying levels of contention.
(Source: I wrote the fast locks that WebKit uses, I’m the person who invented the ParkingLot abstraction for lock impls (now also used in Rust and Unreal Engine), and I previously did research on fast locks for Java and have a paper about that.)
- deleted 2y ago[deleted]
- PaulDavisThe1st 2y agoTo add to this, as the original/lead author of a desktop app that frequently runs with many tens of threads, I'd like to see numbers on performance in non-heavily contended cases. As a real-time (audio) programmer, I am more concerned with (for example) the cost to take the mutex even when it is not already locked (which is the overwhelming situation in our app). Likewise, I want to know the cost of a try-lock operation that will fail, not what happens when N threads are contending. Of course, with Cosmopolitan being open source and all, I could do these measurements myself, but still ...
- ataylor284_ 2y agoThe writeup suggests this implementation is optimized for the not-locked case: > uses an optimistic CAS (compare and swap) immediately, so that locking happens quickly when there's no contention
- pizlonator 2y agoTotally! Pro tip: if you really do know that contention is unlikely, and uncontended acquisition is super important, then it's theoretically impossible to do better than a spinlock. Reason: locks that have the ability to put the thread to sleep on a queue must do compare-and-swap (or at least an atomic RMW) on `unlock`. But spinlocks can get away with just doing a store-release (or just a store with a compiler fence on X86) to `unlock`. Spinlocks also have excellent throughput under most contention scenarios, though at the cost of power and being unkind to other apps on the system. If you want your spinlock to be hella fast on contention just make sure you `sched_yield` before each retry (or `SwitchToThread` on Windows, and on Darwin you can do a bit better with `thread_switch(MACH_PORT_NULL, SWITCH_OPTION_DEPRESS, 1)`).
- PaulDavisThe1st 2y agoWe use spinlocks where appropriate. In the 90s I recall that the general rule of thumb was if the lock is held for <10x the context switch time, spinlocks are generally a better choice. Not sure if that's still true of contemporary architectures. The more common pattern in rt/audio code is "try to take the lock, but have an alternate code path if that fails". It's not that is never going to be contention, but it will be extremely rare, and when it occurs, it probably matters. RWLocks are also a common pattern, with the RT thread(s) being read-only (and still being required to fall back on an alternate code path if the read lock cannot be taken).
- pizlonator 2y agoThese days, fast lock implementations use the following rough idiom, or some idiom that is demonstrably not any slower even for short critical sections. if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return; for (unsigned i = 0; i < 40; ++i) { /* spin for a bounded a mount of time */ if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return; sched_yield(); } ... /* actual full lock algo goes here */ So, the reason to use spinlocks isn't that they are faster for short critical sections, but that they don't have to CAS on unlock - and so they are faster especially in the uncontended case (and in all other cases too). In other words, the modern rule of thumb is something like: if you're going to grab the lock so frequently that the uncontended lock/unlock time shows up as a significant percentage of your execution time, then use a spinlock. That probably implies that you are probably holding the lock for <100x or even <1000x context switch time, or something around there.
- fulafel 2y agoI'm sure you know but this is the opposite of what real-time conventionally means (you have hard deadlines -> worst case is the chief concern).
- uvdn7 2y agoI was thinking the same. There are many mutexes out there, some are better at certain workloads than the rest. DistributedMutex and SharedMutex come to mind (https://github.com/facebook/folly/blob/main/folly/synchronization/DistributedMutex.h https://github.com/facebook/folly/blob/main/folly/synchroniz..., https://github.com/facebook/folly/blob/main/folly/SharedMutex.h https://github.com/facebook/folly/blob/main/folly/SharedMute...) Just like hashmaps, it's rarely the case that a single hashmap is better under _all_ possible workloads.
- pizlonator 2y agoYeah. I should say, though, that if you're on Windows then I have yet to find a real workload where SRWLock isn't the fastest (provided you're fine with no recursion and with a lock that is word-sized). That lock has made some kind of deal with the devil AFAICT.
- ngoldbaum 2y agoThis style of mutex will also power PyMutex in Python 3.13. I have real-world benchmarks showing how much faster PyMutex is than the old PyThread_type_lock that was available before 3.13.
- miohtama 2y agoAny rough summary?
- ngoldbaum 2y agohttps://github.com/numpy/numpy/issues/26510#issuecomment-2294179545 https://github.com/numpy/numpy/issues/26510#issuecomment-229... And now that I look at that again I realize I forgot to finish that up!
- 0xDEADFED5 2y agoCan I use PyMutex from my own Python code?
- ngoldbaum 2y agoNo, it wouldn’t make sense to. Use threading.Lock for that. PyMutex is available in the CPython C API.
- kagrt 2y agoI wonder how much it will help in real code. The no-gil build is still easily 50% slower and the regular build showed a slowdown of 50% for Sphinx, which is why the incremental garbage collector was removed just this week. Python development is in total chaos on all social and technical fronts due to incompetent and malicious leadership.
- plesner 2y agoI'm very ready to believe your description of the state of python is true but I've been out of the loop on python for a while. I'm interested in more details. Can you expand or point to any articles that give more details?
- intelVISA 2y agoFast locks are an oxymoron vs optimized CAS
- xxs 2y agoIndeed, b/c locks need to have their CAS.
- ot 2y agoYeah, that specific benchmark is actually likely to prefer undesirable behaviors, for example pathological unfairness: clearly the optimal scheduling of those threads runs first all the increments from the first thread, then all of the second thread, etc... because this will minimize inter-processor traffic. A mutex that sleeps for a fixed amount (for example 100us) on lock failure acquisition will probably get very close to that behavior (since it almost always bunches), and "win" the benchmark. Still, that would be a terrible mutex for any practical application where there is any contention. This is not to say that this mutex is not good (or that pthread mutexes are not bad), just that the microbenchmark in question does not measure anything that predicts performance in a real application.
- pizlonator 2y agoYeah! For all we know this performs great on real programs. And for all we know it’s absolute trash on real programs.
- lovidico 2y agoDefinitely a microbenchmark and probably wouldn’t be generally representative of performance. This page gives pretty good standards for OS benchmarking practic, although admittedly geared more for academia https://gernot-heiser.org/benchmarking-crimes.html https://gernot-heiser.org/benchmarking-crimes.html