14 ms·

The Fastest Mutexes

896 points by jart 2y ago

kccqzy 2y ago
> 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/synchronization/mutex.h https://github.com/abseil/abseil-cpp/blob/master/absl/synchr... I'm curious why this mutex implementation is absent from the author's benchmarks. By the way if the author farms out to __ulock on macOS, this could be more simply achieved by just using the wait(), notify_one() member functions in the libc++'s atomic library. A while ago there was also a giant thread related to improving Rust's mutex implementation at https://github.com/rust-lang/rust/issues/93740#issuecomment-1041391284 https://github.com/rust-lang/rust/issues/93740#issuecomment-.... What's interesting is that there's a detailed discussion of the inner workings of almost every popular mutex implementation.
- diedyesterday 2y ago
  He seems to have won an ACM award also and there as a (possible) picture of him there. https://awards.acm.org/award-recipients/burrows_9434147 https://awards.acm.org/award-recipients/burrows_9434147
- tialaramex 2y ago
  Although it does get there eventually, that Rust thread is about Mara's work, which is why it eventually mentions her January 2023 book. The current Rust mutex implementation (which that thread does talk about later) landed earlier this year and although if you're on Linux it's not (much?) different, on Windows and Mac I believe it's new work. That said, Mara's descriptions of the guts of other people's implementations is still interesting, just make sure to check if they're out-dated for your situation.
  - SkiFire13 2y ago
    > although if you're on Linux it's not (much?) different AFAIK one reason to switch was that mutexes on Linux and MacOS were not guaranteed to be moveable, so every rust's Mutex had to box the underlying os mutex and was not const-constructible. So this makes a considerable change.
    - tialaramex 2y ago
      That's the reason for Mara's Mutex. I know, it doesn't seem like five minutes, but Mara's is now the previous version of the Rust Mutex implementation. std::sync::Mutex::new became const in 1.63, which was over two years ago.
      - lilyball 2y ago
        It looks like Mara also did the work to make it const-constructible, so it's still her implementation, no? https://github.com/rust-lang/rust/pull/97647 https://github.com/rust-lang/rust/pull/97647
        tialaramex 2y ago
        Sorry, maybe I was unclear, when I pointed out that this work was in 2022 that's not because I was trying to say it's recent, that's two years ago. The current work was in 2024. Here's the 2024 rework of Windows Mutex: https://github.com/rust-lang/rust/pull/121956/ https://github.com/rust-lang/rust/pull/121956/ Edited to add: Since we're going back and forth I read the blame log, the Linux implementation, with which I'm most familiar, is still 85% Mara's although with some meaningful changes from 2024.
- the-rc 2y ago
  Burrows is also responsible for the Burrows Wheeler Transform, Bigtable, Dapper and Chubby, among others.
  - lokar 2y ago
    Also a really nice person. And funny.
  - kristianp 2y ago
    https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform 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
- loeg 2y ago
  > I'm curious why [Abseil's] mutex implementation is absent from the author's benchmarks. Possibly because it's C++ (as opposed to C)? I am speculating.
  - vitus 2y ago
    > Possibly because it's C++ (as opposed to C)? MSVC 2022's std::mutex is listed, though. (That said, GCC's / clang's std::mutex is not listed for Linux or macOS.) absl::Mutex does come with some microbenchmarks with a handful of points of comparison (std::mutex, absl::base_internal::SpinLock) which might be useful to get an approximate baseline. https://github.com/abseil/abseil-cpp/blob/master/absl/synchronization/mutex_benchmark.cc https://github.com/abseil/abseil-cpp/blob/master/absl/synchr...
    - kccqzy 2y ago
      std::mutex is rarely used. In libc++ for example it was just pthread_mutex_t. So it's not different from just benchmarking pthread. I was talking about the wait() and notify_one() member functions for std::atomic. See https://en.cppreference.com/w/cpp/atomic/atomic/wait https://en.cppreference.com/w/cpp/atomic/atomic/wait and https://en.cppreference.com/w/cpp/atomic/atomic/notify_one https://en.cppreference.com/w/cpp/atomic/atomic/notify_one
- BryantD 2y ago
  Mike was a legend by the time I got to AV. The myth was that any time the search engine needed to be faster, he came in and rewrote a few core functions and went back to whatever else he was doing. Might be true, I just can't verify it personally. Extremely smart engineer who cares about efficiency. We did not, however, run on one server for any length of time.
rnrn 2y ago
is comsmopolitan’s mutex also less fair than the other implementations compared?
- cogman10 2y ago
  It's not fair, but (from the description) it does make some effort to be fairish. It'll queue up waiters in a linked list that is fairly fair, but new people can jump ahead of the line and grab the CAS before the list is processed. However, it has added logic to start chunking through the queue after 30 wakeups from a waiter. With that, waiting isn't indefinite, but it also isn't fair. I have no idea how that compares to other implementation's fairness. I know the JDK recently abandoned fairness because of the overhead and complexity it added around mutex handling.
  - tialaramex 2y ago
    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 (though not always) be faster but some people cannot tolerate an unstable sort so it's useless for them. On the other hand, maybe it's an attractive nuisance and if you offered this you'd find most users took your FairMutex, and then were angry because of the inevitable problems from fairness, even though the unfair one was right there...
    - greiskul 2y ago
      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?
      - DSMan195276 2y ago
        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.
tombert 2y ago
I have to admit that I have an extremely visceral, negative feeling whenever I see a mutex, simply because I've had to debug enough code written by engineers who don't really know how to use them, so a large part of previous jobs has been to remove locks from code and replace with some kind of queue or messaging abstraction [1]. It's only recently that I've been actively looking into different locking algorithms, just because I've been diving in head-first to a lot of pure concurrency and distributed computing theory, a lot of which is about figuring out clever ways of doing mutexes with different tradeoffs. I've gotten a lot better with them now, and while I still personally will gravitate towards messaging-based concurrency over locks, I do feel the need to start playing with some of the more efficient locking tools in C, like nsync (mentioned in this article). [1] Before you give me shit over this, generally the replacement code runs at roughly the same speed, and I at least personally think that it's easier to reason about.
- aidenn0 2y ago
  I feel the similarly about C"s "volatile" (when used in multithreaded code rather than device drivers). I've seen people scatter volatile around randomly until the problem goes away. Given that volatile significantly disturbs the timing of a program, any timing sensitive bugs can be masked by adding it around randomly.
  - cogman10 2y ago
    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 parts of the java memory model. The worst things I usually find when reviewing concurrent code is people either not using locks when they should, using locks when they shouldn't, and having inconsistent data guards. I've seen people throw in random locks to guard local non-shared state which is just crazy town but "Multiple threads are running this code, so I'm adding a lock". I certainly prefer message passing over shared state. However, it's a little baffling to me why it's so hard for devs to grasp how to properly maintain shared state. Instead of just learning the basic rules, it gets couched in "It's just too hard to understand so keep adding things until it works". [1] https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz/dp/0321349601 https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz...
alberth 2y ago
Are there any Linux distro's built/using Cosmo? (like Alpine use of musl)
- gavindean90 2y ago
  Not yet
752963e64 2y ago
[dead]
forrestthewoods 2y ago
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.
- jart 2y ago
  What do you consider a good benchmark test case for mutexes?
  - pizlonator 2y ago
    Very large multithreaded programs with lots of diverse uses of locks, including: - uncontended, mildly contended, and horrifically contended - short and long critical sections - contention among small numbers of threads and large numbers of threads - contention that happens when other locks are held recursively and those are also contended on (like, thread A wants a lock held by thread B, but thread B is trying to get a lock held by thread C) Different lock algos work well or badly depending on how the locks are used, so it’s important to pick real programs as your benchmark rather than trying to cook a synthetic benchmark.
- convolvatron 2y ago
  what else would you measure? certainly the uncontended case is important and a baseline, but otherwise this is kind of weak point for mutexes - that if you don't handle contention well then you have idle hardware or lots of additional scheduler work or kernel crossings. [edit - I forget to even mention one of the most important things, that locks that reform poorly under contention can have really negative systemic effects like hot spotting the memory network, and that would show up here too]
  - tialaramex 2y ago
    Uncontended is crucial. If you want to benchmark other things that's excellent, but if MutexA has crap uncontended performance then I'm on a loser if we pick MutexA unless I am absolutely sure we will have a lot of contention. Since contention is never desirable, that's rare. Think of this like the random input case for a sort benchmark. Do I want stuff like all-ascending, all-descending, zig-zag and so on? Sure, those are nice. But without the random input case the benchmark is not very helpful. I might sort a zig-zag, I might sort data that's already in ascending order, but I will sort random data, that's going to happen or else I would not need a sort function.
joelthelion 2y ago
Could established libcs adopt this? If not, why not?
- loeg 2y ago
  Maybe. nsync is Apache licensed.
pizlonator 2y ago
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, and varying levels of contention. (Source: I wrote the fast locks that WebKit uses, I’m the person who invented the ParkingLot abstraction for lock impls (now also used in Rust and Unreal Engine), and I previously did research on fast locks for Java and have a paper about that.)
- deleted 2y ago
  [deleted]
- PaulDavisThe1st 2y ago
  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 operation that will fail, not what happens when N threads are contending. Of course, with Cosmopolitan being open source and all, I could do these measurements myself, but still ...
  - ataylor284_ 2y ago
    The writeup suggests this implementation is optimized for the not-locked case: > uses an optimistic CAS (compare and swap) immediately, so that locking happens quickly when there's no contention
  - pizlonator 2y ago
    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)`).
gok 2y ago
Consider adopting `os_sync_wait_on_address()` on Darwin for your futex needs
- jart 2y ago
  I've used that. It's just as good as ulock although relatively new. The issue is that using this API makes cancelation points no longer atomic. SIGTHR needs to be able to know the exact instruction in memory where an asynchronous signal is delivered when interrupting a wait operation and that's not possible if it's inside an opaque library.
deleted 2y ago
[deleted]
jonathrg 2y ago
> 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.
- tredre3 2y ago
  I'd like to point out that Justine's claims are usually correct. It's just her shtick (or personality?) to use hyperbole and ego-stroking wording. I can see why some might see it as abrasive (it has caused drama before, namely in llamacpp).
  - jancsika 2y ago
    This case isn't abrasive, but it's certainly incoherent. Name a single case where professional responsibility would require C code advertised as "rough around the edges" to be used anywhere near production. (The weasel words "starting to" do not help the logic of that sentence.) I can definitely understand how OP could view this as a red flag. The author should amend it.
  - another-acct 2y ago
    I also meant to comment about the grandstanding in her post. Technical achievement aside, when a person invents something new, the burden is on them to prove that the new thing is a suitable replacement of / improvement over the existing stuff. "I'm starting to view /not/ using [cosmo] in production as an abandonment of professional responsibility" is emotional manipulation -- it's guilt-tripping. Professional responsibility is the exact opposite of what she suggests: it's not jumping on the newest bandwagon. "a little rough around the edges" is precisely what production environments don't want; predictability/stability is frequently more important than peak performance / microbenchmarks. Furthermore, > The C library is so deeply embedded in the software supply chain, and so depended upon, that you really don't want it to be a planet killer. This is just underhanded. She implicitly called glibc and musl "planet killers". First, technically speaking, it's just not true; and even if the implied statement were remotely true (i.e., if those mutex implementations were in fact responsible for a significant amount of cycles in actual workloads), the emotional load / snide remark ("planet killer") is unjustified. Second, she must know very well that whenever efficiency of computation is improved, we don't use that for running the same workloads as before at lower cost / smaller environmental footprint. Instead, we keep all CPUs pegged all the time, and efficiency improvements only ever translate to larger profit. A faster mutex too translates to more $$$ pocketed, and not to less energy consumed. I find her tone of voice repulsive.
stonethrowaway 2y ago
> In 2012, Tunney started working for Google as a software engineer.[4] In March 2014, Tunney petitioned the US government on We the People to hold a referendum asking for support to retire all government employees with full pensions, transfer administrative authority to the technology industry, and appoint the executive chairman of Google Eric Schmidt as CEO of America. the absolute madman
- Dansvidania 2y ago
  I wonder what they (Tunney) think of that now.
- 01HNNWZ0MV43FF 2y ago
  Wild. Then again, in 2012 I was on a grippy sock vacation.
- senderista 2y ago
  from a self-aggrandizing wikipedia article, I presume?
wallstprog 2y ago
" I also managed to make contended nsync mutexes go 30% faster than nsync upstream on AARCH64, by porting it to use C11 atomics." Curious about this -- so what does C11 atomics use to implement? At least in Linux, C++11 atomics use pthreads (not the other way around).
- rcxdude 2y ago
  It depends on what atomics. In principle most of them should map to an underlying CPU primitive, and only fallback to a mutex if it's not supported on the platform.
- loeg 2y ago
  Atomics mostly map to underlying compiler / CPU intrinsics, not pthreads.
- jeffbee 2y ago
  I am also curious about this and the ambiguity of "AARCH64". There are 64-bit ARM ISA versions without atomic primitives and on these what looks like an atomic op is actually a library retry loop with potentially unbounded runtime. The original AWS Graviton CPU had this behavior. The version of the ISA that you target can have significant performance impact.
- jart 2y ago
  nsync has wrapper macros for all the various atomics libraries that prevented it from using two things. 1. Weak CAS. nsync always uses strong CAS upstream to make the portability abstraction simpler. Being able to use weak CAS when appropriate helps avoid code being generated for an additional loop. 2. Updating the &expected parameter. nsync upstream always manually does another relaxed load when a CAS fails. This isn't necessary with the C11 atomics API, because it gives you a relaxed load of the expected value for free when it fails. Being able to exploit those two features resulted in a considerable improvement in nsync's mu_test.c benchmark for the contended mutex case, which I measured on RPI5.
- tialaramex 2y ago
  C++ insists on providing a generic std::atomic type wrapper. So despite my type Goose being almost four kilobytes, std::atomic<Goose> works in C++ Of course your CPU doesn't actually have four kilobyte atomics. So, this feature actually just wraps the type with a mutex. As a result, you're correct in this sense atomics "use pthreads" to get a mutex to wrap the type. C++ also provides specializations, and indeed it guarantees specializations for the built-in integer types with certain features. On real computers you can buy today, std::atomic<int> is a specialization which will not in fact be a mutex wrapper around an ordinary int, it will use the CPU's atomics to provide an actual atomic integer. In principle C++ only requires a single type to be an actual bona fide atomic rather than just a mutex wrapper, std::atomic_flag -- all the integers and so on might be locked by a mutex. In practice on real hardware many obvious atomic types are "lock free", just not std::atomic<Goose> and other ludicrous things.
bjourne 2y ago
I made a benchmark on this last year when I didn't know how slow pthread mutexes were: https://stackoverflow.com/questions/76965112/why-are-pthread-spinlocks-so-much-faster-than-mutexes https://stackoverflow.com/questions/76965112/why-are-pthread... For my use case, the mutex wait amounted to roughly 40% of the total runtime and spinlocks were way faster. Perhaps nsync or Cosmopolitan would have made my code much faster. I still believe the FUD around spinlocks is overstated. For "normal" hpc code the number of threads should be <= the number of cores. In that scenario spinlocking will minimize the latency which likely is what you care about the most. It beats having your performance ruined by dvfs.
- gpderetta 2y ago
  If I'm understanding correctly, you measured pthread_lock as having about twice the overhead of a spin lock. As discussed elsethread, this is expected on x86 as a spinlock only needs an expensive CAS on lock and a cheap store on unlock, while a pthread_lock needs a CAS on both lock and unlock.
  - bjourne 2y ago
    Actually, in the micro benchmark the mutexes were five times slower than the spinlocks. In a real hpc application I reduced the runtime by 30-40% just by replacing them with spinlocks.
- senderista 2y ago
  You can make spinlocks safe enough by backing off with sched_yield and timed sleeps, but at that point I'd probably rather use a ticket lock since I can roughly predict the wait time until my turn.
amiga386 2y ago
If it's so good, why haven't all C libraries adopted the same tricks? My betting is that its tricks are only always-faster for certain architectures, or certain CPU models, or certain types of workload / access patterns... and a proper benchmarking of varied workloads on all supported hardware would not show the same benefits. Alternatively, maybe the semantics of the pthread API (that cosmopolitan is meant to be implementing) are somehow subtly different and this implementation isn't strictly compliant to the spec? I can't imagine it's that the various libc authors aren't keeping up in state-of-the-art research on OS primitives...
- jitl 2y ago
  > 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")
  - amiga386 2y ago
    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.
    - tialaramex 2y ago
      This is nowhere near as common as you seem to think, and mostly only happens for the narrow cases where somebody is obsessed with a particular problem so that they'd actually want to read other people's solutions. Most of the implementers do not have that sort of relationship to a problem they solved in the past. If in December you make a general purpose stable sort that's 25% faster than his, Orson Peters is probably going to read your code and try to apply ideas from it. But sorting is the thing Peters really cares about, the people who wrote the stable sort in say Microsoft's STL (their C++ standard library implementation) even if they still work there won't care enough to go back and change that unless told to do so.
Uehreka 2y ago
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 mention of Cosmo/ape/redbean I’ve ever seen is from Justine’s site. So I’ve gotta ask: Is there a catch? Are these tools doing something evil to achieve what they’re achieving? Is the whole thing a tom7-esque joke/troll that I don’t get because I’m not as deep into compilers/runtimes? Or are these really just ingenious tools that haven’t caught on yet?
- almostgotcaught 2y ago
  > 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 to the fact that the Thompson Shell didn't use a shebang line. (https://justine.lol/ape.html https://justine.lol/ape.html) so the answer is simple: i can't think of anyone that wants to ship fat binaries.
  - fragmede 2y ago
    Anyone focused on customer experience wants to ship a binary that just works, without customers having to know what a fat binary even is.
    - thefaux 2y ago
      I don't think macos will allow you to run a downloaded cosmo binary without going into security settings and enabling it. That's not an experience I'd want my customers to have personally which means if you care about mac normies, this isn't a viable approach.
1st1 2y ago
> I've even had the opportunity to make upstream contributions. For example, I found and fixed a bug in his mutex unlock function that had gone undiscovered for years. I see a stream of improvements to the vendored in nsync inside the cosmopolitan project [1]. Are you planning on upstreaming most of those too? A separate question -- is using the upstream nsync as safe as using your fork? [1] https://github.com/jart/cosmopolitan/commits/master/third_party/nsync/mu.c https://github.com/jart/cosmopolitan/commits/master/third_pa...
- jart 2y ago
  If Burrows wants my C11 atomics refactoring then he shall have it. Beyond that, my changes mostly concern libc integration, systems integration, and portability. Our projects have different goals in those areas, so I'm not sure he needs them.
yshui 2y ago
I had the pleasure of reverse-engineering win32 SRWLOCKs, and based on the author description of nsync it is very close to how SRWLOCK works internally. Kind of surprised how much faster nsync is compared to SRWLOCK.
- TinkersW 2y ago
  The post doesn't include any benchmarks for the uncontended case, where I've found SRWLock is also very fast, I'm curious why this wasn't included. At least for what I use locks for, the uncontended case is like 10000x more common, I actually don't think I have any super heavy contention such as the case shown in the post, as this is simply something to be avoided--as no no matter how good the mutex this won't play well with the memory system.
betimsl 2y ago
And here I thought musl was better than libc sigh
- favorited 2y ago
  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.
  - EasyMark 2y ago
    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?
    - favorited 2y ago
      Sure, and lots of projects do. I was just trying to make the point that there isn't one "good" libc that is universally better – each project has costs and benefits that are tied to its priorities.
akira2501 2y ago
Production isn't about speed, efficiency, or obviously "clever hacks." If I have to sacrifice 50% of my efficiency to ensure that I never get called on Sunday at 3am to fix a broken system, no kidding, I'll make that trade every time. Production is about _reliability_. And writing reliable code is 10x harder than writing "fast" code.
kgeist 2y ago
>Contention is where mutex implementations show their inequality. Mark was so impressed by Microsoft's SRWLOCK that he went on to recommend Linux and FreeBSD users consider targeting Windows if mutex contention is an issue. Interesting, I remember reading a detailed article where they found that there's a lot of severe contention in the Windows kernel, compared to Linux. I think it was when they were trying to parallelize Chrome builds?
- TinkersW 2y ago
  Maybe they weren't using SRWLock, at least last time I checked std::mutex didn't use it with MS STL(They were stuck with critical section because of binary compatibility).
  - markdoubleyou 2y ago
    I'm the Mark who's referenced there. When I did that original benchmark I discovered that the underlying mutex used by MSVCRT did change between versions. For example, in Visual C++ 2013, they used the Windows Concurrency Runtime, which was awful under heavy contention. Newer MSVCRT versions use SRWLOCK. (And I wouldn't characterize myself as being overly impressed... for my particular scenario I wrote, "if you have a poorly written app that's bottlenecked on a lock, then consider targeting Windows to make the best of a bad situation." A better approach, of course, would be to just improve your code!)
- andreareina 2y ago
  https://randomascii.wordpress.com/2017/07/09/24-core-cpu-and-i-cant-move-my-mouse/ https://randomascii.wordpress.com/2017/07/09/24-core-cpu-and...
dumdood 2y ago
Threads and mutexes are the most complicating things in computer science. I am always skeptical of new implementations until they've been used for several years at scale. Bugs in these threading mechanisms often elude even the most intense scrutiny. When Java hit the scene in the mid 90s it exposed all manner of thread and mutex bugs in Solaris. I don't want the fastest mutex implementation - I want a reliable one.
- xxs 2y ago
  mutexes are far from the most 'complicated'. There are really not that many way to implement them (efficiently). In most cases there are best avoided, esp. on the read paths.
flymasterv 2y ago
Mutices.
Akhilmurali 2y ago
Just curious how the wall time is lesser than the sum of system time and user time?
- yencabulator 2y ago
  More than one core.
petermcneeley 2y ago
This sounds like EAThread's futex. https://github.com/electronicarts/EAThread/blob/master/source/eathread_futex.cpp https://github.com/electronicarts/EAThread/blob/master/sourc...
scudsworth 2y ago
is it weird to compare a 96 and 24 core threadripper? i didn't see anything about spawning more threads to make up for the additional cores or anything like that..
deleted 2y ago
[deleted]
SleepyMyroslav 2y ago
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 code starts as 'lets slap a lock here and try to pass the milestone'. Even fast locks will be unpredictably slow and will destroy realtime guarantees if there were any. They can be fast on average but the tail end is never going to go away. I don't want to be that guy who will come back to it chasing 'oh our game has hitches' but I am usually that guy. Use slow locks people. The ones that show big red in profiler. Refactor them out when you see them being hit. I know its a tall order. I can count people who know how to use profiler by fingers on AAA production. And it always like that no matter how many productions I see :) ps. sorry for a rant. Please, continue good research into fast concurrency primitives and algorithms.
- simonask 2y ago
  Even more tangentially: This is one of the reasons I'm having a great time developing a game in Rust. You never want lock contention in a game if at all avoidable, and in a lot of cases taking a lock is provably unnecessary. For example: Each frame is divided into phases, and mutable access to some shared resource only needs to happen in one specific phase (like the `update()` function before `render()`, or when hot-reloading assets). With scoped threads and Rust's borrowing rules, you can structure things to not even need a mutex, and be completely certain that you will receive a stern compiler error if the code changes in way so you do. When possible, I'd always love to take a compiler error over a spike in the profiler.
- loeg 2y ago
  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.
FooBarWidget 2y ago
I don't get it. Aren't most of these nsync tricks also implemented in glibc mutexes? The only thing in that list that's new to me, is long waiting. But even then I don't get it: futexes are already supposed to handle contended waiting.
mareko 2y ago
If anyone's interested in this general subject matter, a while back I did some academic research on highly scalable locks where we came up with some very high performance reader-writer locks: https://people.csail.mit.edu/mareko/spaa09-scalablerwlocks.pdf https://people.csail.mit.edu/mareko/spaa09-scalablerwlocks.p...
Hendrikto 2y ago
> 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. A bit over the top…
c1b 2y ago
Its simple -- you see a justine.lol url, you click immediately
peter_d_sherman 2y ago
Related: https://en.wikipedia.org/wiki/C10k_problem https://en.wikipedia.org/wiki/C10k_problem https://web.archive.org/web/20130722134723/http://www.kegel.com/c10k.html https://web.archive.org/web/20130722134723/http://www.kegel....
carowl 2y ago
[flagged]
deviantbit 2y ago
This code benchmarks mutex contention, not mutex lock performance. If you're locking like this, you should reevaluate your code. Each thread locks and unlocks the mutex for every increment of g_chores. This creates an overhead of acquiring and releasing the mutex frequently (100,000 times per thread). This overhead masks the real performance differences between locking mechanisms because the benchmark is dominated by lock contention rather than actual work. Benchmarks such as this one are useless.
raggi 2y ago
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!

896 points by jart 2y ago

> 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/synchronization/mutex.h https://github.com/abseil/abseil-cpp/blob/master/absl/synchr... I'm curious why this mutex implementation is absent from the author's benchmarks. By the way if the author farms out to __ulock on macOS, this could be more simply achieved by just using the wait(), notify_one() member functions in the libc++'s atomic library. A while ago there was also a giant thread related to improving Rust's mutex implementation at https://github.com/rust-lang/rust/issues/93740#issuecomment-1041391284 https://github.com/rust-lang/rust/issues/93740#issuecomment-.... What's interesting is that there's a detailed discussion of the inner workings of almost every popular mutex implementation.

diedyesterday 2y ago
He seems to have won an ACM award also and there as a (possible) picture of him there. https://awards.acm.org/award-recipients/burrows_9434147 https://awards.acm.org/award-recipients/burrows_9434147
tialaramex 2y ago
Although it does get there eventually, that Rust thread is about Mara's work, which is why it eventually mentions her January 2023 book. The current Rust mutex implementation (which that thread does talk about later) landed earlier this year and although if you're on Linux it's not (much?) different, on Windows and Mac I believe it's new work. That said, Mara's descriptions of the guts of other people's implementations is still interesting, just make sure to check if they're out-dated for your situation.
- SkiFire13 2y ago
  > although if you're on Linux it's not (much?) different AFAIK one reason to switch was that mutexes on Linux and MacOS were not guaranteed to be moveable, so every rust's Mutex had to box the underlying os mutex and was not const-constructible. So this makes a considerable change.
  - tialaramex 2y ago
    That's the reason for Mara's Mutex. I know, it doesn't seem like five minutes, but Mara's is now the previous version of the Rust Mutex implementation. std::sync::Mutex::new became const in 1.63, which was over two years ago.
    - lilyball 2y ago
      It looks like Mara also did the work to make it const-constructible, so it's still her implementation, no? https://github.com/rust-lang/rust/pull/97647 https://github.com/rust-lang/rust/pull/97647
      - tialaramex 2y ago
        Sorry, maybe I was unclear, when I pointed out that this work was in 2022 that's not because I was trying to say it's recent, that's two years ago. The current work was in 2024. Here's the 2024 rework of Windows Mutex: https://github.com/rust-lang/rust/pull/121956/ https://github.com/rust-lang/rust/pull/121956/ Edited to add: Since we're going back and forth I read the blame log, the Linux implementation, with which I'm most familiar, is still 85% Mara's although with some meaningful changes from 2024.
the-rc 2y ago
Burrows is also responsible for the Burrows Wheeler Transform, Bigtable, Dapper and Chubby, among others.
- lokar 2y ago
  Also a really nice person. And funny.
- kristianp 2y ago
  https://en.m.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform 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
loeg 2y ago
> I'm curious why [Abseil's] mutex implementation is absent from the author's benchmarks. Possibly because it's C++ (as opposed to C)? I am speculating.
- vitus 2y ago
  > Possibly because it's C++ (as opposed to C)? MSVC 2022's std::mutex is listed, though. (That said, GCC's / clang's std::mutex is not listed for Linux or macOS.) absl::Mutex does come with some microbenchmarks with a handful of points of comparison (std::mutex, absl::base_internal::SpinLock) which might be useful to get an approximate baseline. https://github.com/abseil/abseil-cpp/blob/master/absl/synchronization/mutex_benchmark.cc https://github.com/abseil/abseil-cpp/blob/master/absl/synchr...
  - kccqzy 2y ago
    std::mutex is rarely used. In libc++ for example it was just pthread_mutex_t. So it's not different from just benchmarking pthread. I was talking about the wait() and notify_one() member functions for std::atomic. See https://en.cppreference.com/w/cpp/atomic/atomic/wait https://en.cppreference.com/w/cpp/atomic/atomic/wait and https://en.cppreference.com/w/cpp/atomic/atomic/notify_one https://en.cppreference.com/w/cpp/atomic/atomic/notify_one
BryantD 2y ago
Mike was a legend by the time I got to AV. The myth was that any time the search engine needed to be faster, he came in and rewrote a few core functions and went back to whatever else he was doing. Might be true, I just can't verify it personally. Extremely smart engineer who cares about efficiency. We did not, however, run on one server for any length of time.

rnrn 2y ago

is comsmopolitan’s mutex also less fair than the other implementations compared?

cogman10 2y ago
It's not fair, but (from the description) it does make some effort to be fairish. It'll queue up waiters in a linked list that is fairly fair, but new people can jump ahead of the line and grab the CAS before the list is processed. However, it has added logic to start chunking through the queue after 30 wakeups from a waiter. With that, waiting isn't indefinite, but it also isn't fair. I have no idea how that compares to other implementation's fairness. I know the JDK recently abandoned fairness because of the overhead and complexity it added around mutex handling.
- tialaramex 2y ago
  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 (though not always) be faster but some people cannot tolerate an unstable sort so it's useless for them. On the other hand, maybe it's an attractive nuisance and if you offered this you'd find most users took your FairMutex, and then were angry because of the inevitable problems from fairness, even though the unfair one was right there...
  - greiskul 2y ago
    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?
    - DSMan195276 2y ago
      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.

tombert 2y ago

I have to admit that I have an extremely visceral, negative feeling whenever I see a mutex, simply because I've had to debug enough code written by engineers who don't really know how to use them, so a large part of previous jobs has been to remove locks from code and replace with some kind of queue or messaging abstraction [1]. It's only recently that I've been actively looking into different locking algorithms, just because I've been diving in head-first to a lot of pure concurrency and distributed computing theory, a lot of which is about figuring out clever ways of doing mutexes with different tradeoffs. I've gotten a lot better with them now, and while I still personally will gravitate towards messaging-based concurrency over locks, I do feel the need to start playing with some of the more efficient locking tools in C, like nsync (mentioned in this article). [1] Before you give me shit over this, generally the replacement code runs at roughly the same speed, and I at least personally think that it's easier to reason about.

aidenn0 2y ago
I feel the similarly about C"s "volatile" (when used in multithreaded code rather than device drivers). I've seen people scatter volatile around randomly until the problem goes away. Given that volatile significantly disturbs the timing of a program, any timing sensitive bugs can be masked by adding it around randomly.
- cogman10 2y ago
  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 parts of the java memory model. The worst things I usually find when reviewing concurrent code is people either not using locks when they should, using locks when they shouldn't, and having inconsistent data guards. I've seen people throw in random locks to guard local non-shared state which is just crazy town but "Multiple threads are running this code, so I'm adding a lock". I certainly prefer message passing over shared state. However, it's a little baffling to me why it's so hard for devs to grasp how to properly maintain shared state. Instead of just learning the basic rules, it gets couched in "It's just too hard to understand so keep adding things until it works". [1] https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz/dp/0321349601 https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz...

alberth 2y ago

Are there any Linux distro's built/using Cosmo? (like Alpine use of musl)

gavindean90 2y ago
Not yet

752963e64 2y ago

[dead]

forrestthewoods 2y ago

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.

jart 2y ago
What do you consider a good benchmark test case for mutexes?
- pizlonator 2y ago
  Very large multithreaded programs with lots of diverse uses of locks, including: - uncontended, mildly contended, and horrifically contended - short and long critical sections - contention among small numbers of threads and large numbers of threads - contention that happens when other locks are held recursively and those are also contended on (like, thread A wants a lock held by thread B, but thread B is trying to get a lock held by thread C) Different lock algos work well or badly depending on how the locks are used, so it’s important to pick real programs as your benchmark rather than trying to cook a synthetic benchmark.
convolvatron 2y ago
what else would you measure? certainly the uncontended case is important and a baseline, but otherwise this is kind of weak point for mutexes - that if you don't handle contention well then you have idle hardware or lots of additional scheduler work or kernel crossings. [edit - I forget to even mention one of the most important things, that locks that reform poorly under contention can have really negative systemic effects like hot spotting the memory network, and that would show up here too]
- tialaramex 2y ago
  Uncontended is crucial. If you want to benchmark other things that's excellent, but if MutexA has crap uncontended performance then I'm on a loser if we pick MutexA unless I am absolutely sure we will have a lot of contention. Since contention is never desirable, that's rare. Think of this like the random input case for a sort benchmark. Do I want stuff like all-ascending, all-descending, zig-zag and so on? Sure, those are nice. But without the random input case the benchmark is not very helpful. I might sort a zig-zag, I might sort data that's already in ascending order, but I will sort random data, that's going to happen or else I would not need a sort function.

joelthelion 2y ago

Could established libcs adopt this? If not, why not?

loeg 2y ago
Maybe. nsync is Apache licensed.

pizlonator 2y ago

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, and varying levels of contention. (Source: I wrote the fast locks that WebKit uses, I’m the person who invented the ParkingLot abstraction for lock impls (now also used in Rust and Unreal Engine), and I previously did research on fast locks for Java and have a paper about that.)

deleted 2y ago
[deleted]
PaulDavisThe1st 2y ago
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 operation that will fail, not what happens when N threads are contending. Of course, with Cosmopolitan being open source and all, I could do these measurements myself, but still ...
- ataylor284_ 2y ago
  The writeup suggests this implementation is optimized for the not-locked case: > uses an optimistic CAS (compare and swap) immediately, so that locking happens quickly when there's no contention
- pizlonator 2y ago
  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)`).

gok 2y ago

Consider adopting `os_sync_wait_on_address()` on Darwin for your futex needs

jart 2y ago
I've used that. It's just as good as ulock although relatively new. The issue is that using this API makes cancelation points no longer atomic. SIGTHR needs to be able to know the exact instruction in memory where an asynchronous signal is delivered when interrupting a wait operation and that's not possible if it's inside an opaque library.

deleted 2y ago

[deleted]

jonathrg 2y ago

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

tredre3 2y ago
I'd like to point out that Justine's claims are usually correct. It's just her shtick (or personality?) to use hyperbole and ego-stroking wording. I can see why some might see it as abrasive (it has caused drama before, namely in llamacpp).
- jancsika 2y ago
  This case isn't abrasive, but it's certainly incoherent. Name a single case where professional responsibility would require C code advertised as "rough around the edges" to be used anywhere near production. (The weasel words "starting to" do not help the logic of that sentence.) I can definitely understand how OP could view this as a red flag. The author should amend it.
- another-acct 2y ago
  I also meant to comment about the grandstanding in her post. Technical achievement aside, when a person invents something new, the burden is on them to prove that the new thing is a suitable replacement of / improvement over the existing stuff. "I'm starting to view /not/ using [cosmo] in production as an abandonment of professional responsibility" is emotional manipulation -- it's guilt-tripping. Professional responsibility is the exact opposite of what she suggests: it's not jumping on the newest bandwagon. "a little rough around the edges" is precisely what production environments don't want; predictability/stability is frequently more important than peak performance / microbenchmarks. Furthermore, > The C library is so deeply embedded in the software supply chain, and so depended upon, that you really don't want it to be a planet killer. This is just underhanded. She implicitly called glibc and musl "planet killers". First, technically speaking, it's just not true; and even if the implied statement were remotely true (i.e., if those mutex implementations were in fact responsible for a significant amount of cycles in actual workloads), the emotional load / snide remark ("planet killer") is unjustified. Second, she must know very well that whenever efficiency of computation is improved, we don't use that for running the same workloads as before at lower cost / smaller environmental footprint. Instead, we keep all CPUs pegged all the time, and efficiency improvements only ever translate to larger profit. A faster mutex too translates to more $$$ pocketed, and not to less energy consumed. I find her tone of voice repulsive.

stonethrowaway 2y ago

> In 2012, Tunney started working for Google as a software engineer.[4] In March 2014, Tunney petitioned the US government on We the People to hold a referendum asking for support to retire all government employees with full pensions, transfer administrative authority to the technology industry, and appoint the executive chairman of Google Eric Schmidt as CEO of America. the absolute madman

Dansvidania 2y ago
I wonder what they (Tunney) think of that now.
01HNNWZ0MV43FF 2y ago
Wild. Then again, in 2012 I was on a grippy sock vacation.
senderista 2y ago
from a self-aggrandizing wikipedia article, I presume?

wallstprog 2y ago

" I also managed to make contended nsync mutexes go 30% faster than nsync upstream on AARCH64, by porting it to use C11 atomics." Curious about this -- so what does C11 atomics use to implement? At least in Linux, C++11 atomics use pthreads (not the other way around).

rcxdude 2y ago
It depends on what atomics. In principle most of them should map to an underlying CPU primitive, and only fallback to a mutex if it's not supported on the platform.
loeg 2y ago
Atomics mostly map to underlying compiler / CPU intrinsics, not pthreads.
jeffbee 2y ago
I am also curious about this and the ambiguity of "AARCH64". There are 64-bit ARM ISA versions without atomic primitives and on these what looks like an atomic op is actually a library retry loop with potentially unbounded runtime. The original AWS Graviton CPU had this behavior. The version of the ISA that you target can have significant performance impact.
jart 2y ago
nsync has wrapper macros for all the various atomics libraries that prevented it from using two things. 1. Weak CAS. nsync always uses strong CAS upstream to make the portability abstraction simpler. Being able to use weak CAS when appropriate helps avoid code being generated for an additional loop. 2. Updating the &expected parameter. nsync upstream always manually does another relaxed load when a CAS fails. This isn't necessary with the C11 atomics API, because it gives you a relaxed load of the expected value for free when it fails. Being able to exploit those two features resulted in a considerable improvement in nsync's mu_test.c benchmark for the contended mutex case, which I measured on RPI5.
tialaramex 2y ago
C++ insists on providing a generic std::atomic type wrapper. So despite my type Goose being almost four kilobytes, std::atomic<Goose> works in C++ Of course your CPU doesn't actually have four kilobyte atomics. So, this feature actually just wraps the type with a mutex. As a result, you're correct in this sense atomics "use pthreads" to get a mutex to wrap the type. C++ also provides specializations, and indeed it guarantees specializations for the built-in integer types with certain features. On real computers you can buy today, std::atomic<int> is a specialization which will not in fact be a mutex wrapper around an ordinary int, it will use the CPU's atomics to provide an actual atomic integer. In principle C++ only requires a single type to be an actual bona fide atomic rather than just a mutex wrapper, std::atomic_flag -- all the integers and so on might be locked by a mutex. In practice on real hardware many obvious atomic types are "lock free", just not std::atomic<Goose> and other ludicrous things.

bjourne 2y ago

I made a benchmark on this last year when I didn't know how slow pthread mutexes were: https://stackoverflow.com/questions/76965112/why-are-pthread-spinlocks-so-much-faster-than-mutexes https://stackoverflow.com/questions/76965112/why-are-pthread... For my use case, the mutex wait amounted to roughly 40% of the total runtime and spinlocks were way faster. Perhaps nsync or Cosmopolitan would have made my code much faster. I still believe the FUD around spinlocks is overstated. For "normal" hpc code the number of threads should be <= the number of cores. In that scenario spinlocking will minimize the latency which likely is what you care about the most. It beats having your performance ruined by dvfs.

gpderetta 2y ago
If I'm understanding correctly, you measured pthread_lock as having about twice the overhead of a spin lock. As discussed elsethread, this is expected on x86 as a spinlock only needs an expensive CAS on lock and a cheap store on unlock, while a pthread_lock needs a CAS on both lock and unlock.
- bjourne 2y ago
  Actually, in the micro benchmark the mutexes were five times slower than the spinlocks. In a real hpc application I reduced the runtime by 30-40% just by replacing them with spinlocks.
senderista 2y ago
You can make spinlocks safe enough by backing off with sched_yield and timed sleeps, but at that point I'd probably rather use a ticket lock since I can roughly predict the wait time until my turn.

amiga386 2y ago

If it's so good, why haven't all C libraries adopted the same tricks? My betting is that its tricks are only always-faster for certain architectures, or certain CPU models, or certain types of workload / access patterns... and a proper benchmarking of varied workloads on all supported hardware would not show the same benefits. Alternatively, maybe the semantics of the pthread API (that cosmopolitan is meant to be implementing) are somehow subtly different and this implementation isn't strictly compliant to the spec? I can't imagine it's that the various libc authors aren't keeping up in state-of-the-art research on OS primitives...

jitl 2y ago
> 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")
- amiga386 2y ago
  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.
  - tialaramex 2y ago
    This is nowhere near as common as you seem to think, and mostly only happens for the narrow cases where somebody is obsessed with a particular problem so that they'd actually want to read other people's solutions. Most of the implementers do not have that sort of relationship to a problem they solved in the past. If in December you make a general purpose stable sort that's 25% faster than his, Orson Peters is probably going to read your code and try to apply ideas from it. But sorting is the thing Peters really cares about, the people who wrote the stable sort in say Microsoft's STL (their C++ standard library implementation) even if they still work there won't care enough to go back and change that unless told to do so.

Uehreka 2y ago

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 mention of Cosmo/ape/redbean I’ve ever seen is from Justine’s site. So I’ve gotta ask: Is there a catch? Are these tools doing something evil to achieve what they’re achieving? Is the whole thing a tom7-esque joke/troll that I don’t get because I’m not as deep into compilers/runtimes? Or are these really just ingenious tools that haven’t caught on yet?

almostgotcaught 2y ago
> 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 to the fact that the Thompson Shell didn't use a shebang line. (https://justine.lol/ape.html https://justine.lol/ape.html) so the answer is simple: i can't think of anyone that wants to ship fat binaries.
- fragmede 2y ago
  Anyone focused on customer experience wants to ship a binary that just works, without customers having to know what a fat binary even is.
  - thefaux 2y ago
    I don't think macos will allow you to run a downloaded cosmo binary without going into security settings and enabling it. That's not an experience I'd want my customers to have personally which means if you care about mac normies, this isn't a viable approach.

1st1 2y ago

> I've even had the opportunity to make upstream contributions. For example, I found and fixed a bug in his mutex unlock function that had gone undiscovered for years. I see a stream of improvements to the vendored in nsync inside the cosmopolitan project [1]. Are you planning on upstreaming most of those too? A separate question -- is using the upstream nsync as safe as using your fork? [1] https://github.com/jart/cosmopolitan/commits/master/third_party/nsync/mu.c https://github.com/jart/cosmopolitan/commits/master/third_pa...

jart 2y ago
If Burrows wants my C11 atomics refactoring then he shall have it. Beyond that, my changes mostly concern libc integration, systems integration, and portability. Our projects have different goals in those areas, so I'm not sure he needs them.

yshui 2y ago

I had the pleasure of reverse-engineering win32 SRWLOCKs, and based on the author description of nsync it is very close to how SRWLOCK works internally. Kind of surprised how much faster nsync is compared to SRWLOCK.

TinkersW 2y ago
The post doesn't include any benchmarks for the uncontended case, where I've found SRWLock is also very fast, I'm curious why this wasn't included. At least for what I use locks for, the uncontended case is like 10000x more common, I actually don't think I have any super heavy contention such as the case shown in the post, as this is simply something to be avoided--as no no matter how good the mutex this won't play well with the memory system.

betimsl 2y ago

And here I thought musl was better than libc sigh

favorited 2y ago
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.
- EasyMark 2y ago
  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?
  - favorited 2y ago
    Sure, and lots of projects do. I was just trying to make the point that there isn't one "good" libc that is universally better – each project has costs and benefits that are tied to its priorities.

akira2501 2y ago

Production isn't about speed, efficiency, or obviously "clever hacks." If I have to sacrifice 50% of my efficiency to ensure that I never get called on Sunday at 3am to fix a broken system, no kidding, I'll make that trade every time. Production is about _reliability_. And writing reliable code is 10x harder than writing "fast" code.

kgeist 2y ago

>Contention is where mutex implementations show their inequality. Mark was so impressed by Microsoft's SRWLOCK that he went on to recommend Linux and FreeBSD users consider targeting Windows if mutex contention is an issue. Interesting, I remember reading a detailed article where they found that there's a lot of severe contention in the Windows kernel, compared to Linux. I think it was when they were trying to parallelize Chrome builds?

TinkersW 2y ago
Maybe they weren't using SRWLock, at least last time I checked std::mutex didn't use it with MS STL(They were stuck with critical section because of binary compatibility).
- markdoubleyou 2y ago
  I'm the Mark who's referenced there. When I did that original benchmark I discovered that the underlying mutex used by MSVCRT did change between versions. For example, in Visual C++ 2013, they used the Windows Concurrency Runtime, which was awful under heavy contention. Newer MSVCRT versions use SRWLOCK. (And I wouldn't characterize myself as being overly impressed... for my particular scenario I wrote, "if you have a poorly written app that's bottlenecked on a lock, then consider targeting Windows to make the best of a bad situation." A better approach, of course, would be to just improve your code!)
andreareina 2y ago
https://randomascii.wordpress.com/2017/07/09/24-core-cpu-and-i-cant-move-my-mouse/ https://randomascii.wordpress.com/2017/07/09/24-core-cpu-and...

dumdood 2y ago

Threads and mutexes are the most complicating things in computer science. I am always skeptical of new implementations until they've been used for several years at scale. Bugs in these threading mechanisms often elude even the most intense scrutiny. When Java hit the scene in the mid 90s it exposed all manner of thread and mutex bugs in Solaris. I don't want the fastest mutex implementation - I want a reliable one.

xxs 2y ago
mutexes are far from the most 'complicated'. There are really not that many way to implement them (efficiently). In most cases there are best avoided, esp. on the read paths.

flymasterv 2y ago

Mutices.

Akhilmurali 2y ago

Just curious how the wall time is lesser than the sum of system time and user time?

yencabulator 2y ago
More than one core.

petermcneeley 2y ago

This sounds like EAThread's futex. https://github.com/electronicarts/EAThread/blob/master/source/eathread_futex.cpp https://github.com/electronicarts/EAThread/blob/master/sourc...

scudsworth 2y ago

is it weird to compare a 96 and 24 core threadripper? i didn't see anything about spawning more threads to make up for the additional cores or anything like that..

deleted 2y ago

[deleted]

SleepyMyroslav 2y ago

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 code starts as 'lets slap a lock here and try to pass the milestone'. Even fast locks will be unpredictably slow and will destroy realtime guarantees if there were any. They can be fast on average but the tail end is never going to go away. I don't want to be that guy who will come back to it chasing 'oh our game has hitches' but I am usually that guy. Use slow locks people. The ones that show big red in profiler. Refactor them out when you see them being hit. I know its a tall order. I can count people who know how to use profiler by fingers on AAA production. And it always like that no matter how many productions I see :) ps. sorry for a rant. Please, continue good research into fast concurrency primitives and algorithms.

simonask 2y ago
Even more tangentially: This is one of the reasons I'm having a great time developing a game in Rust. You never want lock contention in a game if at all avoidable, and in a lot of cases taking a lock is provably unnecessary. For example: Each frame is divided into phases, and mutable access to some shared resource only needs to happen in one specific phase (like the `update()` function before `render()`, or when hot-reloading assets). With scoped threads and Rust's borrowing rules, you can structure things to not even need a mutex, and be completely certain that you will receive a stern compiler error if the code changes in way so you do. When possible, I'd always love to take a compiler error over a spike in the profiler.
loeg 2y ago
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.

FooBarWidget 2y ago

I don't get it. Aren't most of these nsync tricks also implemented in glibc mutexes? The only thing in that list that's new to me, is long waiting. But even then I don't get it: futexes are already supposed to handle contended waiting.

mareko 2y ago

If anyone's interested in this general subject matter, a while back I did some academic research on highly scalable locks where we came up with some very high performance reader-writer locks: https://people.csail.mit.edu/mareko/spaa09-scalablerwlocks.pdf https://people.csail.mit.edu/mareko/spaa09-scalablerwlocks.p...

Hendrikto 2y ago

c1b 2y ago

Its simple -- you see a justine.lol url, you click immediately

peter_d_sherman 2y ago

Related: https://en.wikipedia.org/wiki/C10k_problem https://en.wikipedia.org/wiki/C10k_problem https://web.archive.org/web/20130722134723/http://www.kegel.com/c10k.html https://web.archive.org/web/20130722134723/http://www.kegel....

carowl 2y ago

[flagged]

deviantbit 2y ago

This code benchmarks mutex contention, not mutex lock performance. If you're locking like this, you should reevaluate your code. Each thread locks and unlocks the mutex for every increment of g_chores. This creates an overhead of acquiring and releasing the mutex frequently (100,000 times per thread). This overhead masks the real performance differences between locking mechanisms because the benchmark is dominated by lock contention rather than actual work. Benchmarks such as this one are useless.

raggi 2y ago

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!