Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Fastest Mutexes

justine.lol

Post reply on HN
Print view View original

311–320 of 360 posts

Re: The Fastest Mutexes

#311

Post by menaerus »

wrsh07 wrote: post #238
aseipp wrote: post #183

Earlier quoted context omitted.

Those projects often have dozens of other priorities beyond just one specific API, and obsessing over individual APIs isn't a good way to spend the limited time they have. In any case, as a concrete example to disprove your claim, you can look at malloc and string routines in your average libc on Linux. glibc's malloc is tolerable but fails handily to more modern alternatives in overall speed and scalability (it frag…

Another example is hash maps: all the large companies built better maps in cpp (folly, absl), but the number of apps that are performance sensitive and still use std::unordered_map will be astounding forever. (Why not upstream? ABI compatibility which is apparently a sufficient veto reason for anything in cpp)

No, that's rubbish that became a meme. There is no universally the best design of a hash-map. Each design always comes with its own trade-offs and so is the case with open-addressing vs separate chaining in conflict resolution. Iterator instability and memory-bandwidth intensive rehashing just to name a few.

Design of your hash-map, or any other algorithm or data-structure, is always and only dictated by your workload. Microbenchmark suite from xyz company/person will hardly represent that reality.

So the more generous answer would be it's not because of "ABI" meme but because std::unordered_map is just fine for the most cases out there. And this is what general purpose standard library is ought to be able to support.

Re: The Fastest Mutexes

#312

Post by plesner »

kagrt wrote: post #288
ngoldbaum wrote: post #112

Earlier quoted context omitted.

This 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.

I 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.

I'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?

Re: The Fastest Mutexes

#313

Post by loeg »

epcoa wrote: post #302
secondcoming wrote: post #286

Earlier quoted context omitted.

No you should spin on a read. Once you see the value you want you then try the CMPXCHG. If that succeeds you exit. If it fails you go back to spinning on the read.

What is the difference between a read and a “load” here?

Read and load mean the same thing. (I think GP just missed the end of your comment.)

You care about exchange vs read/load because of cache line ownership. Every time you try to do the exchange, the attempting CPU must take exclusive ownership of the cacheline (stealing it from the lock owner). To unlock, the lock owner must take it back.

If the attempting CPU instead only reads, the line ownership stays with the lock holder and unlock is cheaper. In general you want cache line ownership to change hands as few times as possible.

Re: The Fastest Mutexes

#314

Post by pizlonator »

epcoa wrote: post #304
pizlonator wrote: post #296

Earlier quoted context omitted.

Spinning with pause is slower than spinning with sched_yield according to every test I’ve ever done

For what it is worth it seems the library in question does both, uses an exponential retry loop, busy read looping 2^i times for the first 7 attempts before then yielding. It seems like there must be some threshold where latency is improved by retrying before yielding, but I don’t test these things for a living. https://github.com/google/nsync/blob/c6205171f084c0d3ce3ff51...

My data says that always yielding is better than ever busy spinning, except on microbenchmarks, where depending on the microbenchmarks you can get any answer your heart desires.

Re: The Fastest Mutexes

#315

Post by loeg »

pizlonator wrote: post #116
PaulDavisThe1st wrote: post #114

Earlier quoted context omitted.

We use spinlocks where appropriate. In the 90s I recall that the general rule of thumb was if the lock is held for 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-onl…

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…

> 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.

Yeah, and maybe also consider changing your design because usually this isn't needed.

Re: The Fastest Mutexes

#316

Post by wrsh07 »

menaerus wrote: post #311
wrsh07 wrote: post #238

Earlier quoted context omitted.

Another example is hash maps: all the large companies built better maps in cpp (folly, absl), but the number of apps that are performance sensitive and still use std::unordered_map will be astounding forever. (Why not upstream? ABI compatibility which is apparently a sufficient veto reason for anything in cpp)

No, that's rubbish that became a meme. There is no universally the best design of a hash-map. Each design always comes with its own trade-offs and so is the case with open-addressing vs separate chaining in conflict resolution. Iterator instability and memory-bandwidth intensive rehashing just to name a few. Design of your hash-map, or any other algorithm or data-structure, is always and only dictated by your workloa…

Lol this is so incorrect it's almost funny. Google saved something like single digit % of CPU and memory fleet wide by switching to this map. That's not a micro benchmark

Re: The Fastest Mutexes

#317

Post by loeg »

SleepyMyroslav wrote: post #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…

Totally agree. Debugging features -- e.g. deadlock detection / introspection -- easily pay for themselves. If you're actually acquiring locks so frequently they matter, you should revisit your design. Sharing mutable state between thread should be avoided.

Re: The Fastest Mutexes

#318

Post by davidtgoldblatt »

gpderetta wrote: post #303
davidtgoldblatt wrote: post #300

Earlier quoted context omitted.

There's two I've tried to do this: - On the wait side, do the CAS to set the "waiter present" bit. Down unlock, do a (relaxed) read of the lock word, and if "waiter present" isn't set, just do a release store to unlock (and go down some slow CAS-y wake path if a waiter is present). On the wait side, never do an un-timed futex wait; just do a series of timed waits, with increasing wait times (so that you still eventua…

> Split out the "waiter present" bit into its own byte, do a store-load sequence (with just a compiler reordering fence) to check for waiters, and have waiters either do a membarrier() syscall or wait "long enough" that they're sure they've gotten the same effect. (This gets tricky w.r.t. mutex lifetime though; you either need out of band lifetime knowledge or to use RCU or whatever and indirect through pointers). If…

It kinda depends; you only do the membarrier when you're about to sleep anyways, and the non-expedited membarrier() call is just a synchronize_rcu(), so it's not that drastically more expensive than a futex wait.

You don't necessarily want a biased lock for all this kind of stuff, because "sparsely contended" doesn't necessarily imply thread-associated. E.g. one place I was looking at this for was locks for pages of virtual memory in a heap; no thread "owns" any given heap page, but it was very uncommon to get unlucky and have two threads touching adjacent pages at the exact same time. These kind of "sloppy mutexes" get half the fast-path speedup of biased locks but without the heavily asymmetric performance costs. (At least, that was the theory; like I said it didn't really pan out to be that useful in practice).

Re: The Fastest Mutexes

#319

Post by E39M5S62 »

almostgotcaught wrote: post #213
cycomanic wrote: post #169

Earlier quoted context omitted.

Correct me if I'm wrong, but I always thought Apple universal binaries are fat binaries? So why did Apple build this ability if nobody wants it?

> So why did Apple build this ability if nobody wants it? did you miss the part where they transitioned from x86 to arm64 in 2020?

And PowerPC to x86 before that.

Re: The Fastest Mutexes

#320

Post by Animats »

epcoa wrote: post #304
pizlonator wrote: post #296

Earlier quoted context omitted.

Spinning with pause is slower than spinning with sched_yield according to every test I’ve ever done

For what it is worth it seems the library in question does both, uses an exponential retry loop, busy read looping 2^i times for the first 7 attempts before then yielding. It seems like there must be some threshold where latency is improved by retrying before yielding, but I don’t test these things for a living. https://github.com/google/nsync/blob/c6205171f084c0d3ce3ff51...

I've tried to figure out where that goes wrong. Read the bug report linked. I've caught this situation in gdb with 20 threads in spinlocks inside realloc, performance in a game down to 1 frame every 2 seconds, and very little getting done. But I don't understand how the three levels of locking involved cause that. Nor do the Wine people.

Works fine on Microsoft Windows. Only fails on Wine.

Post reply on HN