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

101–110 of 360 posts

Re: The Fastest Mutexes

#101

Post by jitl »

amiga386 wrote: post #76
jitl wrote: post #66

Earlier quoted context omitted.

> I can't imagine it's that the various libc authors aren't keeping up in state-of-the-art research on OS primitives... is this sarcasm? (I don't know any libc maintainers, but as a maintainer of a few thingies myself, I do not try to implement state-of-the-art research, I try to keep my thingies stable and ensure the performance is acceptable; implementing research is out of my budget for "maintenance")

But if you maintain a few thingies, you'd probably know about rival thingies that do a similar thing, right? If the rival thingies got a speed boost recently, and they were open source, you'd want to have a look at how they did it and maybe get a similar speed boost for yourself.

It depends on the calculus about (time) budget and stability. Maybe I consider performance already acceptable, and don't have time budget to investigate beyond that. Maybe I look at "nsync", see its mutex (may) change the fairness semantics, and then decide not to adopt it because this may break my callers; or its enough that it may change the fairness semantics, and I don't have the budget to test nsync or a new implementation based on the nsync algorithm to determine if the semantics differ.

Re: The Fastest Mutexes

#102

Post by jkachmar »

Uehreka wrote: post #68

So on the one hand, all this Cosmo/ape/redbean stuff sounds incredible, and the comments on these articles are usually pretty positive and don’t generally debunk the concepts. But on the other hand, I never hear mention of anyone else using these things (I get that not everyone shares what they’re doing in a big way, but after so many years I’d expect to have seen a couple project writeups talk about them). Every men…

reposting my comment from another time this discussion came up:

"Cosmopolitan has basically always felt like the interesting sort of technical loophole that makes for a fun blog post which is almost guaranteed to make it to the front page of HN (or similar) purely based in ingenuity & dedication to the bit.

as a piece of foundational technology, in the way that `libc` necessarily is, it seems primarily useful for fun toys and small personal projects.

with that context, it always feels a little strange to see it presented as a serious alternative to something like `glibc`, `musl`, or `msvcrt`; it’s a very cute hack, but if i were to find it in something i seriously depend on i think i’d be a little taken aback."

Re: The Fastest Mutexes

#103

Post by DSMan195276 »

greiskul wrote: post #53
tialaramex wrote: post #16

Earlier quoted context omitted.

Fairness is known to cause serious problems such as convoys, so while "unfair" isn't itself a desirable property, you might choose to be unfair because the alternatives are worse for some applications. Probably a specifically Fair version of any concurrent primitive which can be fair is worth giving a distinct name, the way you'd offer both a stable and an unstable sort, knowing that the unstable sort will often (tho…

In a lot of cases, programmers don't even care about fairness, but do care about starvation. Is there a word for structures like the one discussed here, that are unfair but appear to prevent unlimited starvation?

I don't think this lock is _guaranteed_ to prevent starvation, it just makes an effort at it. There's only two priority levels and a hard-coded 30 wake-ups required to enter high priority - if waiters were continually joining then there could always be more than one entry in high priority and an entry could get stuck there forever. Typically it won't matter, but if you have high contention then this might not be good enough.

Re: The Fastest Mutexes

#104

Post by jonathrg »

fefe23 wrote: post #92
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.

Have you considered that you may have a different kind of humor than Justine? Why would you even post this here? Who do you think this is helping?

It doesn't clearly come across as a joke.

Re: The Fastest Mutexes

#105

Post by ataylor284_ »

almostgotcaught wrote: post #69
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.

It's especially a red-flag since an enormous number of projects (almost all of them?) will never tolerate shipping fat binaries (ie what cosmopolitan C is in reality).

The core of this a library called nsync. It appears most of the improvements by Justine are upstreamed into nsync itself which doesn't have any of the baggage of cosmopolitan. Whatever your opinion of the project or author, they've made good effort to not lock you in.

Re: The Fastest Mutexes

#106

Post by pizlonator »

PaulDavisThe1st wrote: post #85
pizlonator wrote: post #23

Always cool to see new mutex implementations and shootouts between them, but I don’t like how this one is benchmarked. Looks like a microbenchmark. Most of us who ship fast locks use very large multithreaded programs as our primary way of testing performance. The things that make a mutex fast or slow seem to be different for complex workloads with varied critical section length, varied numbers of threads contending,…

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 on X86) to `unlock`.

Spinlocks also have excellent throughput under most contention scenarios, though at the cost of power and being unkind to other apps on the system. If you want your spinlock to be hella fast on contention just make sure you `sched_yield` before each retry (or `SwitchToThread` on Windows, and on Darwin you can do a bit better with `thread_switch(MACH_PORT_NULL, SWITCH_OPTION_DEPRESS, 1)`).

Re: The Fastest Mutexes

#107

Post by hyperion2010 »

amiga386 wrote: post #82
Uehreka wrote: post #68

So on the one hand, all this Cosmo/ape/redbean stuff sounds incredible, and the comments on these articles are usually pretty positive and don’t generally debunk the concepts. But on the other hand, I never hear mention of anyone else using these things (I get that not everyone shares what they’re doing in a big way, but after so many years I’d expect to have seen a couple project writeups talk about them). Every men…

APE works through cunning trickery that might get patched out any day now (and in OpenBSD, it has been). Most people producing cross-platform software don't want a single executable that runs on every platform, they want a single codebase that works correctly on each platform they support. With that in mind that respect, languages like go letting you cross compile for all your targets (provided you avoid CGO) is deli…

> Most people

We'll I'm used to not being most people, but I'd much rather be able to produce a single identical binary for my users that works everywhere than the platform specific nonsense I have to go through right now. Having to maintain different special build processes for different platforms is a stupid waste of time.

Frankly this is how it always should have worked except for the monopolistic behavior of various platforms in the past.

Re: The Fastest Mutexes

#108

Post by another-acct »

Salgat wrote: post #26
forrestthewoods wrote: post #11

Hrm. Big fan of Justine and their work. However this is probably the least interesting benchmark test case for a Mutex. You should never have a bunch of threads constantly spamming the same mutex. So which mutex implementation best handles this case isn’t particularly interesting, imho.

I'd say the vast majority of cases where I use a lock/semaphore is around very expensive resources, where the utilization of that resource vastly outweighs any performance overhead of the lock.

This is how it should be. IIRC -- apologies, can't find a source --, Ulrich Drepper wrote somewhere about NPTL that its mutexes were not particularly lightweight, but that you should design your program for low contention anyways.

For highly contended data structures, spinlocks (and nowadays explicit atomics) are likely better.

Re: The Fastest Mutexes

#109

Post by tombert »

hinkley wrote: post #56
cogman10 wrote: post #8

Earlier quoted context omitted.

There seems to be a lot of voodoo beliefs around concurrent programming that lead to really bad things. One of the best books I've read on it is Java concurrency in practice [1]. It does an excellent job of dispelling these occultic beliefs and letting the reader know exactly when and how concurrency should be implemented. It is applicable to more languages than just java, especially since many have adopted large par…

I loved concurrent code when I was starting out. I’d taken a pretty good distributed computing class which started the ball rolling. They just fit into how my brain worked very well. Then I had to explain my code to other devs, either before or after they broke it, and over and over I got the message that I was being too clever. I’ve been writing Grug-brained concurrent code for so long I’m not sure I can still do th…

That's something I'm afraid of for my latest project. I did some concurrent stuff that wasn't 100% clear would actually work, and I had to write a PlusCal spec to exhaustively prove to myself that what I was doing is actually OK.

It works pretty well, and I'm getting decent speeds, but I'm really scared someone is going to come and "fix" all my code by doing it the "normal" way, and thus slow everything down. I've been trying to comment the hell out of everything, and I've shared the PlusCal spec, but no one else on my team knows PlusCal and I feel like most engineers don't actually read comments, so I think it's an inevitability that my baby is killed.

Post reply on HN