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

321–330 of 360 posts

Re: The Fastest Mutexes

#321

Post by bpfrh »

bcoates wrote: post #130
0x1ceb00da wrote: post #89

Earlier quoted context omitted.

Wasn't elf format modified by upstream to accomodate for cosmo? That makes it kinda official. Still hard to see a use case for it. If you want everyone to be able to run your program, just write a web app, a win32 program, or a java applet. 20 years old java applets still run on modern JVMs.

You can't reasonably assume the end user system has a system JVM installed (they probably don't, in fact) so they're not really an alternative to a fat binary -- if you can install dependencies, you can just pick a single-target binary while you're at it.

but you can provide that JVM for different plattforms in a zip file/installer.

The more difficult problem with cross plattform apps are always native look and feel and calling native apis in an idiomatic and performant ways.

Re: The Fastest Mutexes

#322

Post by oriolid »

cycomanic wrote: post #227
almostgotcaught wrote: post #213

Earlier quoted context omitted.

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

I don't get your point. People were arguing that one doesn't need fat binaries because cross compiling and having different binaries is fine. Apple clearly thought differently when they transitioned from x86 to arm (not their first architecture transition either). So now you're saying because apple finished the transition fat binaries are useless again? What about other platforms?

> apple finished the transition fat binaries are useless again?

Is the transition really finished? I'm writing this on a x86_64 Macbook with a browser that is distributed as x86_64/arm64 universal binary.

Re: The Fastest Mutexes

#323

Post by raggi »

I went in half expecting to see another spin heavy solution, so glad to find futexes used properly, cache line sharding and so on. Yay, practically scalable mutexes rather than microbenchmark winning hacks!

Re: The Fastest Mutexes

#324

Post by scottlamb »

ninkendo wrote: post #291
pizlonator wrote: post #135

Earlier quoted context omitted.

I’ve shipped code on Darwin that spinlocks and gets away with it without any noticeable cases of this happening. I know it can happen in theory. But theory and practice ain’t the same. I worked for Apple when I shipped this too lmao

Also worked for Apple for 13 years: there is a lot (and I mean a LOT) of priority inversions and abuse of locks in the codebase. Breaking out the internal profiler and actually having a look at whether you were running at the priority you thought can be a very illuminating thing. One particular app had a particularly nasty habit of losing priority because most of its work was done in a set of daemons and not in the U…

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

Re: The Fastest Mutexes

#325

Post by senderista »

xxs wrote: post #274
spacechild1 wrote: post #253

Earlier quoted context omitted.

> If you want your spinlock to be hella fast on contention just make sure you `sched_yield` before each retry Shouldn't you rather use pause instructions (_mm_pause, __yield, ISB, etc.) instead of thread switching? That's what I have seen in most spin lock implementations. Maybe it depends on the use case?

start with few attempts w/o pause, just busy CAS, then CAS + pause, then yield (and backoff/sleep with random duration)

No, you shouldn’t be calling CAS in a tight loop, but rather a relaxed load to check if a CAS might be successful, with PAUSE equivalent after each load. After spinning for ~context switch latency you should back off with sched_yield before retrying the spin loop (and eventually start sleeping on backoff with exponential jitter etc).

Re: The Fastest Mutexes

#326

Post by xxs »

senderista wrote: post #325
xxs wrote: post #274

Earlier quoted context omitted.

start with few attempts w/o pause, just busy CAS, then CAS + pause, then yield (and backoff/sleep with random duration)

No, you shouldn’t be calling CAS in a tight loop, but rather a relaxed load to check if a CAS might be successful, with PAUSE equivalent after each load. After spinning for ~context switch latency you should back off with sched_yield before retrying the spin loop (and eventually start sleeping on backoff with exponential jitter etc).

of course, there is very rarely any a naked CAS

Re: The Fastest Mutexes

#327

Post by foobazgt »

foobazgt wrote: post #232
hinkley wrote: post #164

Earlier quoted context omitted.

> Not true in any practical sense. This is going to put a damper on any further conversation. Even with coarsening and elision every synchronized function closes a lock on the enclosing object.

"every synchronized function" Right. Synchronized is the key word here. The vast majority of code doesn't involve synchronized, and therefore the vast majority of objects don't have locks associated with them. That's quite important. Those classes which do use synchronized were just going to create a ReentrantLock held for the duration of the call anyway, in which case it's all monitorEnter and monitorExit, regardles…

> in which case it's all monitorEnter and monitorExit, regardless.

Oops, I need to correct myself!

ReentrantLock doesn't depend upon monitorEnter/Exit, but rather AbstractQueuedSynchronizer and LockSupport, which ultimately delegate to Unsafe methods like park/unpark and CAS (*compareAndSet*). Don't know why I had that confused in my head.

In any case, the point holds that "synchronized" as a language feature has mostly a zero cost for code that doesn't use it. It's a red herring when discussing modern Java concurrency.

Re: The Fastest Mutexes

#328

Post by epcoa »

Animats wrote: post #320
epcoa wrote: post #304

Earlier quoted context omitted.

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.

It seems like the loop around InterlockedCompareExchange is a bad idea since this is a bus lock in a tight loop. Rather the inner spinning loop that is yielding should just be reading the value surrounded by the cmpxchg. As for whether sched_yield should just be called in the inner loop or a short nop/pause loop should be attempted for microcontention reasons, the expert opinion here is don't bother with the nop loop. However while the nop loop might not be real world optimal I doubt that would be causing a catastrophic performance issue.

Re: The Fastest Mutexes

#329

Post by menaerus »

wrsh07 wrote: post #316
menaerus wrote: post #311

Earlier quoted context omitted.

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

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.

Re: The Fastest Mutexes

#330

Post by senderista »

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

> musl doesn't even have things like SIMD optimized string comparison routines. You would be shocked at how many CPU cycles in a non-trivial program are spent on those tasks Building GNU Make with Cosmo or glibc makes cold startup go 2x faster for me on large repos compared to building it with Musl, due to vectorized strlen() alone (since SIMD is 2x faster than SWAR). I sent Rich a patch last decade adding sse to str…

> You have Doug Lea to thank for that.

Wait, you don't mean your allocator is based on dlmalloc, do you?

Post reply on HN