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

351–360 of 360 posts

Re: The Fastest Mutexes

#351

Post by spacechild1 »

PaulDavisThe1st wrote: post #340
spacechild1 wrote: post #256

Earlier quoted context omitted.

Keep in mind that while try_lock() is realtime-safe, the following unlock() may not, as it may need to wake threads that have been blocked in the meantime! So I would only use this pattern for situations where the very fact that a NRT thread tries to acquire the lock already means that RT safety is not a concern anymore (e.g. a device has been disconnected)

Excellent reminder. Yes, this is both a design defect of try/unlock that can't really be solved, and an implementation defect on several platforms that makes it worse than it actually needs to be (Windows, I'm looking at you)

One thing I've been using is a spinlock where the RT thread only uses try_lock() + fallback path and the NRT thread(s) call try_lock() in a loop with pause instructions and occasional thread yielding (or even sleeping). This might waste lots of CPU cycles when a NRT thread tries to acquire a lock that is already held by the RT thread, but assuming this only happens occasionally/rarely, it's a reasonable trade-off.

Re: The Fastest Mutexes

#352

Post by wbl »

pizlonator wrote: post #342
wbl wrote: post #341

Earlier quoted context omitted.

You did say uncontended!

So you want uncontended unlocks to make a syscall to wake the threads that aren’t there? That syscall will be worse than a CAS just because it’s a syscall. Not to mention it’ll have to lock some kernel data structure just to figure out that there aren’t any threads to wake.

I think I'm not doing a great job of explaining it.

There are three states of the mutex: locked=1, unlocked=0, and sleeping=2. A thread comes along to a locked mutex, and atomically moves it to sleeping and sleeps via futex. The freeing thread unconditionally writes 0 and atomically sees the old value: if 2 wake all, if 1 no need to wake anybody.

Maybe that is equally expensive to a CAS, but I don't think it ultimately is.

Re: The Fastest Mutexes

#353

Post by pizlonator »

wbl wrote: post #352
pizlonator wrote: post #342

Earlier quoted context omitted.

So you want uncontended unlocks to make a syscall to wake the threads that aren’t there? That syscall will be worse than a CAS just because it’s a syscall. Not to mention it’ll have to lock some kernel data structure just to figure out that there aren’t any threads to wake.

I think I'm not doing a great job of explaining it. There are three states of the mutex: locked=1, unlocked=0, and sleeping=2. A thread comes along to a locked mutex, and atomically moves it to sleeping and sleeps via futex. The freeing thread unconditionally writes 0 and atomically sees the old value: if 2 wake all, if 1 no need to wake anybody. Maybe that is equally expensive to a CAS, but I don't think it ultimate…

“Atomically sees the old value” means you’re doing an atomic RMW, which is more expensive than just a store with a release fence.

Atomic RMW is almost as expensive as CAS. Exactly as expensive as CAS on some cpus.

Re: The Fastest Mutexes

#354

Post by exikyut »

Animats wrote: post #173
pizlonator wrote: post #106

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…

I know NQP here isn't Not Quite Perl, but I'm not sure what it *is*. Seeking enlightenment!

Re: The Fastest Mutexes

#355

Post by wrsh07 »

menaerus wrote: post #329
wrsh07 wrote: post #316

Earlier quoted context omitted.

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

Learn to read with understanding and learn to have some respect as well. Never have I said that it cannot make a difference but that it's not universal and that it depends on the workload.

Microbenchmark suite is very different from fleet wide profiling

The whole point of switching every single use of unordered map to node/flat hash map is because it is always better. It always uses less memory (much less memory per node).

Edit: what did I say that was disrespectful? I called you out for being wrong because you're very wrong

Re: The Fastest Mutexes

#356

Post by wrsh07 »

menaerus wrote: post #329
wrsh07 wrote: post #316

Earlier quoted context omitted.

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

Learn to read with understanding and learn to have some respect as well. Never have I said that it cannot make a difference but that it's not universal and that it depends on the workload.

Ok let me try to unpack what I'm saying so that we're on the same page:

1. Until c++ [toolchains] do an abi break, you will find better performance in libraries like boost/folly/absl than in the STL. Titus wrote about this in "abi now or never" ~4 years ago. His thesis was "the language is leaving performance on the table, and by default if you care about performance you should not use the STL." Afaict this is all still true. If you think this is a meme, you're wrong, it's existential for companies like Google.

2. You mention a bunch of things that one might consider when picking a hashmap. "There might be a workload where I need one map vs another." Yes, that's true. However, my original statement was saying: if you care about performance you should not use unordered map. This is sort of like saying "if you care about performance you should not use bubble sort." Of course there are lots of considerations when choosing a sorting algorithm. Does it need to be cache tuned/oblivious? Do you have a lot of runs in your data (eg is it mostly sorted?)? HOWEVER, I will happily tell you to prefer a gently optimized quick sort over bubble sort for ~all workloads, and if you need further performance then go consider those things.

The performance of the absl/folly maps is not a joke. It's the basis for the rust hash map. These are good, general purpose hash maps. That's not a meme. It's also not a meme to say that the cpp working groups are generally unwilling to make ABI breaks for small improvements (indeed, in the past decade they haven't made an ABI break to bundle large improvements)

Re: The Fastest Mutexes

#357

Post by senderista »

jart wrote: post #347
senderista wrote: post #330

Earlier quoted context omitted.

> You have Doug Lea to thank for that. Wait, you don't mean your allocator is based on dlmalloc, do you?

Yes. Is there something wrong with that? If your program links pthread_create() then cosmo creates a dlmalloc arena for each core on your computer and uses sched_getcpu() to index them combined with raw nsync locks.

I thought that’s pretty much what ptmalloc did (glibc malloc is forked ptmalloc3)?

Re: The Fastest Mutexes

#358

Post by krackers »

ninkendo wrote: post #343
scottlamb wrote: post #324

Earlier quoted context omitted.

> The company had a pretty widely spread internal article trying to whack people over the head to stop abusing lock primitives in this way, but we just kept shipping code with this issue. It sounds like this is relevant when developing user app code, not just the kernel or core libraries. Is there an external version of this article? I would be very interested to read more.

TL;DR: Never, ever, ever, ever do this: let valueIWant: String? = nil let sem = DispatchSemaphore(value: 0) someAsyncFunction() { result in // this is called in another thread valueIWant = result sem.signal() } sem.wait() assert(valueIWant != nil) Note, this is mostly about semaphores, so it’s a bit offtopic from the original discussion here which is about spinlocks. But basically, never lock something in expectation…

But wouldn't the same apply to condition variables, not just semaphores?

Also I found another reference to that internal post here https://cohost.org/Catfish-Man/post/913314-a-love-letter-to-...

Re: The Fastest Mutexes

#359

Post by ninkendo »

krackers wrote: post #358
ninkendo wrote: post #343

Earlier quoted context omitted.

TL;DR: Never, ever, ever, ever do this: let valueIWant: String? = nil let sem = DispatchSemaphore(value: 0) someAsyncFunction() { result in // this is called in another thread valueIWant = result sem.signal() } sem.wait() assert(valueIWant != nil) Note, this is mostly about semaphores, so it’s a bit offtopic from the original discussion here which is about spinlocks. But basically, never lock something in expectation…

But wouldn't the same apply to condition variables, not just semaphores? Also I found another reference to that internal post here https://cohost.org/Catfish-Man/post/913314-a-love-letter-to-...

It applies to any concurrency primitive that can be used across threads, yes. NSLock and os_unfair_lock can only be unlocked by the thread that locked them, so you can’t abuse them to turn async code into sync code in this manner in the first place.

Basically people recommend os_unfair_lock because of what it can’t do.

Re: The Fastest Mutexes

#360

Post by SJC_Hacker »

Maxatar wrote: post #143
SJC_Hacker wrote: post #71

Earlier quoted context omitted.

> For me the biggest challenge when sharing state is that the only benefit I can see for parallelism is performance, so if I'm not gaining performance there is no reason to use parallelism. Aside from performance, another very common reason is to not lock the UI from the user. Even in UI-less programs, the ability to abort some operation which is taking too long. Another is averaging out performance of compute tasks,…

>Aside from performance, another very common reason is to not lock the UI from the user. This is not a good fit for parallelism, this is pretty much always accomplished using concurrency ie. async/await.

async/await uses threads underneath. And sometimes even that paradigm is not sufficient.
Post reply on HN