Live data from Hacker News

The Fastest Mutexes

justine.lol

261–270 of 360 posts

Re: The Fastest Mutexes

#261

Earlier quoted context omitted.

Some amount of legacy cruft is not unexpected, but it's sad that it can be seen in new code. In .NET, which has similarly problematic semantics with lock(), linters have been flagging lock(this) for ages. I wonder where this patently bad idea of every object carrying its own publicly accessible mutex originated in the first place. Did Java introduce it, or did it also copy that from somewhere else? And what was the m…

Can't attest to the history of `lock` statement from the top of my head but the API shape of lock and Monitor.Enter/Exit methods it is desugared to looks like Win32's EnterCriticalSection and LeaveCriticalSection. Other Monitor's methods like Wait and Pulse look like pthread's condvar and mutex functions. .NET also has MethodImplOptions.Synchronized like Java does. However, the only place I have ever seen this attrib…

It's not Monitor itself that's problematic. It's that every object is implicitly associated with one, and anyone who holds a reference to an object can lock it. It doesn't matter if the type is internal - it can still be upcast to System.Object and leaked that way.

In practice this means that unless you can guarantee that you never, ever leak a reference anywhere, you don't know who else might be locking it. Which makes it impossible to reason about possible deadlocks. So the only sane way to manage it is to have a separate object used just for locking, which is never ever passed outside of the object that owns the lock.

And yes, this is absolutely bad design. There's no reason why every object needs a lock, for starters - for the vast majority of them, it's just unnecessary overhead (and yes, I know the monitors are lazily created, but every object header still needs space to store the reference to it). Then of course the fact that it's there means that people take the easy path and just lock objects directly instead of creating separate locks, just because it's slightly less code - and then things break. It's almost always the wrong granularity, too.

Thing is, I haven't seen this design anywhere outside of Java and .NET (which copied it from Java along with so many other bad ideas). Everybody else uses the sane and obvious approach of creating locks explicitly if and when they are needed.

Re: The Fastest Mutexes

#262

Earlier quoted context omitted.

Totally! 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 Darwin, it's possible for a pure spinlock to produce a priority inversion deadlock, because Darwin has a quality of service implementation in the kernel that differs from how everyone else handles thread priority. In other kernels, a low-priority thread will still eventually be guaranteed a cpu slice, so if it's holding a spinlock, it will eventually make progress and unlock. On Darwin with Quality of Service, it'…

On Linux you can still easily go extremely slow with plain sched_yield() as there's no guarantee the thread who holds the lock will get to run, especially in numa situations due to a strong bias against migrating threads across numa boundaries. You have to use the e.g. futex API to tell the kernel what you're waiting for.

Bare spinlocks are very bad in this way, unless you have dedicated hardware threads (with SMT you can pin all but one of the threads with the remaining thread being general purpose, though you may want a way to inform the scheduler which cores to currently prefer due to their pinned tasks being more idle).

Re: The Fastest Mutexes

#263

Threads and mutexes are the most complicating things in computer science. I am always skeptical of new implementations until they've been used for several years at scale. Bugs in these threading mechanisms often elude even the most intense scrutiny. When Java hit the scene in the mid 90s it exposed all manner of thread and mutex bugs in Solaris. I don't want the fastest mutex implementation - I want a reliable one.

mutexes are far from the most 'complicated'. There are really not that many way to implement them (efficiently). In most cases there are best avoided, esp. on the read paths.

Re: The Fastest Mutexes

#264
post #3

is comsmopolitan’s mutex also less fair than the other implementations compared?

All primitive performance evaluations should be multidimensional, IMO, with fairness being one of the highest-priority variables.

The importance of fairness varies with the algorithm. For instance, one that alternates between being CPU-bound and disk-bound may use N_workers >>> N_cores. These workers might not care about individual starvation at all.

At the other end, consider a strictly CPU-bound algorithm with N_workers==N_cores, and a rogue-ish worker that ends up hogging an important mutex by spinning around it (e.g. the one written by author of the benchmark.) If the other well-behaved workers briefly lock the mutex once prior to each job, but end up getting woken up only once every 30 locks (as this implementation apparently does,) you might end up with core utilization This in turn means that APIs that let you customize the behavior can win out even if they're not #1 on any benchmark.

Re: The Fastest Mutexes

#265
Completely tangential:

As gamedev I came to love slow mutexes that do a lot of debug things in all 'developer' builds. Have debug names/IDs, track owners, report time spent in contention to profiler, report ownership changes to profiler...

People tend to structure concurrency differently and games came to some patterns to avoid locks. But they are hard to use and require programmer to restructure things. Most of the code starts as 'lets slap a lock here and try to pass the milestone'. Even fast locks will be unpredictably slow and will destroy realtime guarantees if there were any. They can be fast on average but the tail end is never going to go away. I don't want to be that guy who will come back to it chasing 'oh our game has hitches' but I am usually that guy.

Use slow locks people. The ones that show big red in profiler. Refactor them out when you see them being hit.

I know its a tall order. I can count people who know how to use profiler by fingers on AAA production. And it always like that no matter how many productions I see :)

ps. sorry for a rant. Please, continue good research into fast concurrency primitives and algorithms.

Re: The Fastest Mutexes

#266

Earlier quoted context omitted.

Totally! 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…

> just make sure you `sched_yield` before each retry Assuming `sched_yield` does something. There's a futex congestion problem inside Wine's memory allocator. There are several levels of locks. If you're growing a buffer, in the sense of C's "realloc", and no buffer is available, memory allocation is locked during the allocation of a bigger buffer, copying of the contents, and release of the old buffer. "Push" type o…

if YieldProcessor() actually did switch it'd be awfully expensive, like mentioned "rep; nop", is not just a "nop".

OTOH, the usual way to lock via a busy loop/spin, does require some attempts then backoff with a random duration.

Re: The Fastest Mutexes

#267

Earlier quoted context omitted.

> just make sure you `sched_yield` before each retry Assuming `sched_yield` does something. There's a futex congestion problem inside Wine's memory allocator. There are several levels of locks. If you're growing a buffer, in the sense of C's "realloc", and no buffer is available, memory allocation is locked during the allocation of a bigger buffer, copying of the contents, and release of the old buffer. "Push" type o…

`rep; nop;` is actually the `pause` instruction. On older CPUs it’s a standard nop, but on newer CPUs it’s a more efficient nop. Spinning on the CMPXCHG is also a bad idea. You should spin on the read and only then attempt the CMPXCHG.

Just to clarify: the spinning on CMPXCHG is not also a bad idea, the YieldProcessor is correct (a pause), but inside the CMPXCHG loop it should be spinning on a pure unlocked load. Is that correct?

Re: The Fastest Mutexes

#268

Earlier quoted context omitted.

Totally! 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…

> just make sure you `sched_yield` before each retry Assuming `sched_yield` does something. There's a futex congestion problem inside Wine's memory allocator. There are several levels of locks. If you're growing a buffer, in the sense of C's "realloc", and no buffer is available, memory allocation is locked during the allocation of a bigger buffer, copying of the contents, and release of the old buffer. "Push" type o…

Has WINE considered using mremap() for its realloc() implementation? It allows you to make realloc() of a sufficient size basically cost nothing. See this screenshot https://x.com/JustineTunney/status/1837663502619889875 On other platforms like MacOS you can achieve the same thing as mremap() by mapping to random addresses, and then using MAP_FIXED to append.

Re: The Fastest Mutexes

#269
I don't get it. Aren't most of these nsync tricks also implemented in glibc mutexes? The only thing in that list that's new to me, is long waiting. But even then I don't get it: futexes are already supposed to handle contended waiting.

Re: The Fastest Mutexes

#270

Earlier quoted context omitted.

These 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 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…

Huh, interesting. TIL. Thanks for that!

Lots of code is 'lock free' and uses the same pattern (more or less). Attempt the change optimistically, if it fails spin it, if it keeps failing (Massive Contention), back off.
Post reply on HN