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

211–220 of 360 posts

Re: The Fastest Mutexes

#211

Post by jay-barronville »

jonathrg wrote: post #34

> It's still a new C library and it's a little rough around the edges. But it's getting so good, so fast, that I'm starting to view not using it in production as an abandonment of professional responsibility. What an odd statement. I appreciate the Cosmopolitan project, but these exaggerated claims of superiority are usually a pretty bad red flag.

> I appreciate the Cosmopolitan project, but these exaggerated claims of superiority are usually a pretty bad red flag.

In general, I agree with your sentiment, but Justine is simply a different beast. She does tend to use hyperbolic language a fair amount, but she delivers so much awesomeness that I make an exception for her.

Re: The Fastest Mutexes

#212

Post by kristianp »

the-rc wrote: post #36
kccqzy wrote: post #2

> The reason why Cosmopolitan Mutexes are so good is because I used a library called nsync. It only has 371 stars on GitHub, but it was written by a distinguished engineer at Google called Mike Burrows. Indeed this is the first time I've heard of nsync, but Mike Burrows also wrote Google's production mutex implementation at https://github.com/abseil/abseil-cpp/blob/master/absl/synchr... I'm curious why this mutex imp…

Burrows is also responsible for the Burrows Wheeler Transform, Bigtable, Dapper and Chubby, among others.

https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_tran...

> The Burrows-Wheeler transform is an algorithm used to prepare data for use with data compression techniques such as bzip2

Re: The Fastest Mutexes

#213

Post by almostgotcaught »

cycomanic wrote: post #169
almostgotcaught wrote: post #79

Earlier quoted context omitted.

> So I’ve gotta ask: Is there a catch? Are these tools doing something evil to achieve what they’re achieving? it's not that complicated; they're fat binaries (plus i guess a lot of papering over the differences between the platforms) that exploit a quirk of tshell: > One day, while studying old code, I found out that it's possible to encode Windows Portable Executable files as a UNIX Sixth Edition shell script, due…

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?

Re: The Fastest Mutexes

#214

Post by int_19h »

aidenn0 wrote: post #64
zozbot234 wrote: post #35

Earlier quoted context omitted.

The "volatile" keyword should never be used for C/C++ multithreaded code. It's specifically intended for access to device-mapped addresses and does not account for any specific memory model, so using it for multithreading will lead to breakage. Please use the C/C++ memory model facilities instead. (As a contrast, note that in Java the "volatile" keyword can be used for multithreading, but again this does not apply to…

> Please use the C/C++ memory model facilities instead I should point out that for more than half of my professional career, those facilities did not exist, so volatile was the most portable way of implementing e.g. a spinlock without the compiler optimizing away the check. There was a period after which compilers were aggressively inlining and before C11 came out in which it could be otherwise quite hard to otherwis…

The problem is that volatile alone never portably guaranteed atomicity nor barriers, so such a spinlock would simply not work correctly on many architectures: other writes around it might be reordered in a way that make the lock useless.

It does kinda sorta work on x86 due its much-stronger-than-usual guarantees wrt move instructions even in the absence of explicit barriers. And because x86 was so dominant, people could get away with that for a while in "portable" code (which wasn't really portable).

Re: The Fastest Mutexes

#215

Post by cogman10 »

kccqzy wrote: post #208
cogman10 wrote: post #132

Earlier quoted context omitted.

Yup. Message passing has allocation pressure and cache consistency pressure not present in using a shared message location. Especially as the amount of memory in question goes up, the benefit of a shared location increases in terms of the performance impact. Sure, for something silly like writing to an int, there is negative benefit in a shared location, but when you start talking about a dictionary with 1 million en…

You are talking about writes to a data structure such as a list or a dictionary from multiple threads. Nobody uses advanced message passing techniques for that. A list is basically the poster child of why you avoid mutexes: each thread writes to its own version of a sublist, with no use of mutexes, and then at the end of the processing every thread's lists are merged together. Merging a list takes O(1) time by manipu…

> Merging a list takes O(1) time

Depends on the list implementation. I assume we are talking C++ lists? in that case yeah, I can see how you'd instead do a `splice` of sublists.

I was thinking more in terms of something like a `vector` in which case adding the sublists in requires copying values from one vector to the source vector. That (especially if done wrong) can involve allocating potentially more than once to drop the results in.

But, for the record, there are lock free algorithms that don't require a mutex to add values into a list. You basically CAS the tail pointer with your new value.

That being said, I concede that for a list a mutex is probably the wrong choice. It's a better choice in Java which has constraints that prevent (easily) splicing together 2 lists.

For the dictionary, implementation is key. A good segmented dictionary is going to be hard to beat.

Re: The Fastest Mutexes

#216

Post by int_19h »

jart wrote: post #205
int_19h wrote: post #197

Earlier quoted context omitted.

A web app is, well, a web app. Many things don't fit this format, e.g. command line tools. A Win32 program will not run out of the box on either Linux or macOS. Neither will a Java app. The nice thing about Cosmopolitan is that it "just works" as far as end user is concerned. But without firm support from the OSes involved, it is inevitably a hack with questionable long-term stability prospects. What we really need i…

Yes that's exactly what we need. And we'll be laughing to the bank when we bundle a browser toolbar with adware into its installer ten years down the road. Oh wait Java already did this. OTOH Cosmopolitan gives you complete autonomy. You don't need a JVM to run a simple native command line program on multiple OSes and I proved that.

JVM bytecode is obviously not what I was talking about - it is neither low-level (if you can't efficiently compile the entirety of C into it, it's not good enough for this purpose), nor did it ever have universal first-class OS support.

And stuff like https://github.com/jart/cosmopolitan/issues/1263 shows that just because it works today, it doesn't mean that it'll work tomorrow. What's the guarantee that the same won't happen on Linux or macOS eventually?

Don't get me wrong, APE is a hell of a hack, and I love it for that. But it can't be a truly stable platform without guarantees from the underlying OSes to keep all of that machinery working the same way. And if we could actually get them to agree on something like that, why not get them to agree on an actual portable executable format that is future-proof also wrt new CPU architectures?

(Note, by the way, that this is orthogonal to the whole notion of fat binaries that contain arch-specific code. That is still a useful optimization to have in practice even if one has portable bytecode, alongside said portable bytecode.)

Re: The Fastest Mutexes

#217

Post by wbl »

pizlonator wrote: post #106
PaulDavisThe1st wrote: post #85

Earlier quoted context omitted.

To 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 opera…

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…

Atomic RMW is all you need. Imagine 3 state futex lock of taken, sleeping, and unlocked. Waking thread just needs to see old value but writes unlocked unconditionally.

I don't think this is more expensive than release certainly not because of the line where the write goes in most cache coherency protocols.

Granted this lock does wake up too many people but you did say usually uncontended.

Re: The Fastest Mutexes

#218

Post by ngoldbaum »

0xDEADFED5 wrote: post #154
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.

Can I use PyMutex from my own Python code?

No, it wouldn’t make sense to. Use threading.Lock for that. PyMutex is available in the CPython C API.

Re: The Fastest Mutexes

#219

Post by EasyMark »

favorited wrote: post #152
betimsl wrote: post #144

And here I thought musl was better than libc sigh

musl is a libc, and while it is superior in some ways, it is inferior in others. If you want a statically linked libc, or a permissively licensed libc, musl is a fantastic choice. If you want a libc with the fastest malloc implementation, you'll probably want to look elsewhere.

Can’t you sub in your own malloc like the one in the article or jemalloc if you don’t like the performance of the original in your app?

Re: The Fastest Mutexes

#220

Post by bobmcnamara »

secondcoming wrote: post #187
Animats wrote: post #173

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.

Bingo. Spinning on CMPXCHG can cause livelock.
Post reply on HN