The Fastest Mutexes

by jart • 2 years ago

896 345 2 years ago

kccqzy4• 2 years 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/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-.... What's interesting is that there's a detailed discussion of the inner workings of almost every popular mutex implementation.

tialaramex11• 2 years 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• 2 years 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.

the-rc• 2 years ago

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

lokar• 2 years ago

Also a really nice person. And funny.

kristianp• 2 years ago

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

loeg9• 2 years 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.

vitus2• 2 years 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/synchr...

BryantD• 2 years 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.

diedyesterday• 2 years 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

rnrn• 2 years ago

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

cogman109• 2 years 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.

tialaramex11• 2 years 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...

pizlonator16• 2 years ago

Most fast locks these days are unfair. It turns out the perf advantage of unfairness is so massive that it’s just Better (TM).

worstspotgain• 2 years ago

All primitive performance evaluations should be multidimensional, IMO, with fairness being one of the highest-priority variables.

The importance of fairness varies with the algorithm. For instance, one that alternates between being CPU-bound and disk-bound may use N_workers >>> N_cores. These workers might not care about individual starvation at all.

At the other end, consider a strictly CPU-bound algorithm with N_workers==N_cores, and a rogue-ish worker that ends up hogging an important mutex by spinning around it (e.g. the one written by author of the benchmark.) If the other well-behaved workers briefly lock the mutex once prior to each job, but end up getting woken up only once every 30 locks (as this implementation apparently does,) you might end up with core utilization <<< 100%.

This in turn means that APIs that let you customize the behavior can win out even if they're not #1 on any benchmark.

tombert8• 2 years 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.

aidenn03• 2 years 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.

cogman109• 2 years 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...

tialaramex11• 2 years ago

In most cases (in a C or C++ compiler, not Java) it's just straight up incorrect to use volatile for something other than memory mapped I/O. Yes, POSIX guarantees that in a specific case (signal handling IIRC) it'll do what you meant if you use volatile int. That's nice, but more generally this is not the right choice.

Unfortunately Microsoft enshrined the situation (on Windows, on their compiler, on x86 and x86-64 only) that volatile primitive types are effectively atomics with Acquire-Release ordering. This is of course awkward when Microsoft tries to bring people to a non-x86 architecture and it can't just give them this because it would suck really hard, so finally they have to grow up and teach their developers about actual atomics.

!! Edited to fix: Previously this said Relaxed ordering, the ordering guaranteed by Microsoft is in fact Acquire-Release, hence it's expensive to provide for architectures where that's not the default.

zozbot2342• 2 years ago

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 C/C++.)

senderista9• 2 years ago

If you only use volatile in C without any atomic operations or fences, then your multithreaded code is certainly incorrect.

jart15• 2 years ago

What are some examples of people using mutexes wrong? I know one gotcha is you need to maintain a consistent hierarchy. Usually the easiest way to not get snagged by that, is to have critical sections be small and pure. Java's whole MO of letting people add a synchronized keyword to an entire method was probably not the greatest idea.

cogman109• 2 years ago

When, how, and why.

The biggest part of mutexes and how to properly use them is thinking of the consistency of the data that you are working with.

Here's a really common bug (psuedocode)

    if (lock {data.size()} > 0) {
      value = lock { data.pop() }
      lock { foo.add(value) }
    }

The issue here is size can change, pop can change, and foo can change in unexpected ways between each of the acquired locks.

The right way to write this code is

    lock {
      if (data.size() > 0) {
        value = data.pop()
        foo.add(value)
      }
    }

That ensures the data is all in a consistent state while you are mutating it.

Now, what does make this tricky is someone well-meaning might have decided to push the lock down a method.

Imagine, for example, you have a `Foo` where all methods operate within a mutex.

This code is also (likely) incorrect.

    value = foo.bar()
    if (value.bat()) {
      foo.baz(value)
    }

The problem here is exactly the same problem as above. Between `foo.bar()` and `foo.baz()` the state of foo may have changed such that running `foo.baz(value)` is now a mistake. That's why the right thing to do is likely to have a `foo.barBaz()` method that encapsulates the `if` logic to avoid inconsistency (or to add another mutex).

In java, the most common manifestation (that I see) of this looks like this

    var map = new ConcurrentHashMap();
    if (map.get(foo) == null)
      map.put(foo, new Value());

Because now, you have a situation where the value of `foo` in the map could be 2 or more values depending on who gets it. So, if someone is mutating `Value` concurrently you have a weird hard to track down data race.

The solution to this problem in java is

    map.computeIfAbsent(foo, (unused)->new Value());

tombert8• 2 years ago

Personally I've had issues with performance because of people using `synchronized` too liberally, where they end up locking a lot more code than necessary. I've also had issues with fairly typical circular-dependencies, causing deadlock, or at least pauses that aren't strictly necessary. Deadlock doesn't happen nearly as often as textbooks have led me to believe, but it can happen with sloppily written code.

In regards to Java, at this point I almost never use the `synchronized` keyword anymore and instead (if I can't easily map to some kind of queuing abstraction) use the ReentrantLock object simply because of the ability to have lock acquisition time out, and also letting you opt-in to fairness if you'd like. It's not as pretty but it's more flexible and as far as I'm aware it doesn't affect performance much.

For the most part, though, in Java, you can get away without (explicit) locks by simply abusing the built-in data structures. I know they're using their own synchronization techniques behind the scenes, but I trust those to be correct more than some ad-hoc stuff I'd write as an engineer.

foobazgt6• 2 years ago

Java's take on monitors was definitely not great, and people were emulating mutexes with them even in the language's earliest days.

Still there are a lot of things that can go wrong with mutexes: forgetting to unlock in the case of exceptions, priority inversion, recursive locking, deadlock, needlessly high contention, etc.

Java has had an excellent concurrency runtime with abstractions that are typically a better fit than a bare mutex for over 20 years now (c.f. Doug Lea). Synchronized still exists, because of Java's excellent backwards compatibility.

foobiekr• 2 years ago

I've always disliked that lock cyclic dependencies is discussed as a hierarchy when what it really comes down to is a linear order of locks.

The problem with lock _hierarchies_ as a concept is that a lock really should represent serialization of access to a particular pool of data, and should make no assumptions that it being held implies some other lock's domain is also held. The code that results when people do not maintain this kind of rigor is quite terrible, but hierarchies tend to steer people into thinking that way because they imply recursively taking locks.

Stated differently: locks should be taken and released in a fixed order - so locks are ranked - but there should not be a model where all lower-ranked locks must be held for a given lock to be taken. The lock protects its domain and the ordering of take and release is to prevent deadlock, but there's no requirement for completeness.

bob1029• 2 years ago

some kind of queue or messaging abstraction

Agreed. I find things like LMAX Disruptor much easier to reason about.

tombert8• 2 years ago

Even within Java, something like BlockingQueue will get you pretty far, and that's built into the runtime.

If I am allowed to use libraries, I end up using Vert.x for nearly everything. I think that their eventbus abstraction is easy enough to reason about, and even without using it simply using the non-blocking stuff it provides ends up being pretty handy.

jeffbee2• 2 years ago

Message passing is just outsourcing the lock, right? For example a Go channel is internally synchronized, nothing magic about it.

Most of the mutex tragedies I have seen in my career have been in C, a useless language without effective scopes. In C++ it's pretty easy to use a scoped lock. In fact I'd say I have had more trouble with people who are trying to avoid locks than with people who use them. The avoiders either think their program order is obviously correct (totally wrong on modern CPUs) or that their atomics are faster (wrong again on many CPUs).

loeg9• 2 years ago

Message passing is just outsourcing the lock, right?

More or less, yeah. You can write an MPSC queue that doesn't explicitly use a lock (or even anything that looks like a lock).

tombert8• 2 years ago

It's definitely doing synchronization behind the scenes, no argument here. BlockingQueues in Java seem to use ReentrantLocks everywhere. It's outsourcing the lock to people who understand locks better.

It just abstracts this detail away for me, and I personally trust the libraries implementing these abstractions to be more correct than some ad hoc thing I write. It's an abstraction that I personally find a lot easier to reason about, and so my thinking is this: if my reasoning is more likely to be correct because of the easier abstraction, and the internal synchronization is more likely to be correct, then it's more likely that my code will be correct.

I don't do super low-level stuff at all, most of my stuff ends up touching a network, so the small differences between the built-in synchronized structures vs the regular ones really don't matter since any small gains I'd get on that will be eaten the first time I hit the network, so a considerably higher ROI for me is almost always figuring out how to reduce latency.

If I did C or C++, I'd probably have different opinions on this stuff.

foobazgt6• 2 years ago

Every abstraction is about outsourcing the thing it's abstracting away. If using a queue solves your problem, you no longer have to deal with all the headaches that you can run into using a bare mutex.

another-acct7• 2 years ago

C, a useless language without effective scopes

Mutexes can be handled safely in C. It's "just another flavor" of resource management, which does take quite a bit of discipline. Cascading error paths / exit paths help.

sgarland• 2 years ago

C, a useless language

You misspelled “fast as fuck” and “lingua franca of all architectures.”

adgjlsfhk1• 2 years ago

Message passing is just outsourcing the lock, right?

Kind of. If you can architect such that each channel has exactly 1 reader and 1 writer, you can send messages in a single direction with no locks. The basic idea is that you have a circular buffer with a start index and an end index. The writer can write an element and increment the end index (as long as end index+1<start index which doesn't have to be done atomically), while the reader can just read an element and increment the start index (as long as start index +1 < end index). This strategy needs to use atomic operations (which are basically free when uncontested, which they will be as long as the queue has a few elements in it)

another-acct7• 2 years ago

remove locks from code and replace with some kind of queue or messaging abstraction

Shared-nothing message passing reflects the underlying (modern) computer architecture more closely, so I'd call the above a good move. Shared memory / symmetric multiprocessing is an abstraction that leaks like a sieve; it no longer reflects how modern computers are built (multiple levels of CPU caches, cores, sockets, NUMA, etc).

tombert8• 2 years ago

That's good to hear! I am pretty removed from underlying hardware now, so it makes me happy to hear that better way of doing things is catching on even in low-level land.

gpderetta6• 2 years ago

If you are doing pure shared nothing message passing, you do not need coherent caches; in fact cache coherency gets in the way of pure message passing.

Viceversa if you do pure message passing you are not benefitting from hardware accelerated cache coherency and leaving performance (and usability) on the floor.

intelVISA3• 2 years ago

Shared-nothing is typically The Right Choice in my experience as well. Maybe the odd atomic...

alberth• 2 years ago

Are there any Linux distro's built/using Cosmo?

(like Alpine use of musl)

gavindean902• 2 years ago

Not yet

forrestthewoods3• 2 years 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.

jart15• 2 years ago

What do you consider a good benchmark test case for mutexes?

pizlonator16• 2 years 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• 2 years 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]

tialaramex11• 2 years 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.

cogman109• 2 years ago

You should never have a bunch of threads constantly spamming the same mutex.

I'm not sure I agree with this assessment. I can think of a few cases where you might end up with a bunch of threads challenging the same mutex.

A simple example would be something like concurrently populating some data structure (list/dict/etc). Yes, you could accomplish this with message passing, but that uses more memory and would be slower than just having everything wait to write to a shared location.

kccqzy4• 2 years ago

would be slower than just having everything wait to write to a shared location

Nope.

forrestthewoods3• 2 years ago

If you’re trying to mutate a dictionary many times from many threads you’re going to have a bad time. The fix isn’t a faster mutex, it’s don’t do that.

Salgat2• 2 years ago

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.

another-acct7• 2 years ago

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.

joelthelion• 2 years ago

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

loeg9• 2 years ago

Maybe. nsync is Apache licensed.

pizlonator16• 2 years 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.)

PaulDavisThe1st3• 2 years 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_2• 2 years 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

pizlonator16• 2 years 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)`).

fulafel• 2 years ago

I'm sure you know but this is the opposite of what real-time conventionally means (you have hard deadlines -> worst case is the chief concern).

uvdn7• 2 years ago

I was thinking the same. There are many mutexes out there, some are better at certain workloads than the rest. DistributedMutex and SharedMutex come to mind (https://github.com/facebook/folly/blob/main/folly/synchroniz..., https://github.com/facebook/folly/blob/main/folly/SharedMute...) Just like hashmaps, it's rarely the case that a single hashmap is better under _all_ possible workloads.

pizlonator16• 2 years ago

Yeah.

I should say, though, that if you're on Windows then I have yet to find a real workload where SRWLock isn't the fastest (provided you're fine with no recursion and with a lock that is word-sized). That lock has made some kind of deal with the devil AFAICT.

ngoldbaum3• 2 years ago

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.

miohtama• 2 years ago

Any rough summary?

0xDEADFED5• 2 years ago

Can I use PyMutex from my own Python code?

kagrt• 2 years ago

I wonder how much it will help in real code. The no-gil build is still easily 50% slower and the regular build showed a slowdown of 50% for Sphinx, which is why the incremental garbage collector was removed just this week.

Python development is in total chaos on all social and technical fronts due to incompetent and malicious leadership.

intelVISA3• 2 years ago

Fast locks are an oxymoron vs optimized CAS

xxs8• 2 years ago

Indeed, b/c locks need to have their CAS.

ot3• 2 years ago

Yeah, that specific benchmark is actually likely to prefer undesirable behaviors, for example pathological unfairness: clearly the optimal scheduling of those threads runs first all the increments from the first thread, then all of the second thread, etc... because this will minimize inter-processor traffic.

A mutex that sleeps for a fixed amount (for example 100us) on lock failure acquisition will probably get very close to that behavior (since it almost always bunches), and "win" the benchmark. Still, that would be a terrible mutex for any practical application where there is any contention.

This is not to say that this mutex is not good (or that pthread mutexes are not bad), just that the microbenchmark in question does not measure anything that predicts performance in a real application.

pizlonator16• 2 years ago

Yeah! For all we know this performs great on real programs.

And for all we know it’s absolute trash on real programs.

lovidico• 2 years ago

Definitely a microbenchmark and probably wouldn’t be generally representative of performance. This page gives pretty good standards for OS benchmarking practic, although admittedly geared more for academia https://gernot-heiser.org/benchmarking-crimes.html

gok• 2 years ago

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

jart15• 2 years 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.

jonathrg3• 2 years 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• 2 years 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• 2 years 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-acct7• 2 years 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.

asveikau• 2 years ago

She claimed posix changed for her use case, and it's not true, posix disallows what she said.

Indeed the first few bullet points of her writeup on how the lock works (compare and swap for uncontended, futex for contended) is already how everybody implements locks for about 20 years since the futex was introduced for exactly this. Win32 critsec from even longer ago works the same way.

__turbobrew__• 2 years ago

The drama in llamacpp was not due to language, it was due to jart making false claims and having absolutely no idea how memory maps work in addition to needlessly changing file headers to contain her name in vanity.

I don’t think anybody can deny that jart is a smart person, but I think there is more to it than just language abbrasiveness which people take issue with.

almostgotcaught4• 2 years ago

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

another-acct7• 2 years ago

Agreed; this is what I've always (silently) thought of those fat binaries. Absolute stroke of genius, no doubt, and also a total abomination (IMO) from a sustainability perspective.

ataylor284_2• 2 years ago

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.

intelVISA3• 2 years ago

Ironic given the generous size of the average Go binary.

pmarreck• 2 years ago

I feel that there’s a certain amount of hubris that comes along with spending long periods of time solo-coding on a computer, and perhaps unwittingly starved of social contact. Without any checks on you or your work’s importance (normally provided by your bog-standard “job”), your achievements take on a grandeur that they might not have broadly earned, as impressive as they might be.

An example is APE (which I otherwise feel is a very impressive hack). One criticism might be “oh, so I not only get to be insecure on one platform, I can be insecure on many all at once?”

The longer you spend in technology, the more you realize that there are extremely few win-wins and a very many win-somes, lose-somes (tradeoffs)

fefe23• 2 years ago

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?

jonathrg3• 2 years ago

It doesn't clearly come across as a joke.

another-acct7• 2 years ago

I think it's fair to comment not only on the subject, but on the writing itself, too.

And it might help Justine improve her writing (and reach a larger audience -- after all, blog posts intend to reach some audience, don't they?). Of course you can always say, "if you find yourself alienated, it's your loss".

gr4vityWall• 2 years ago

It came off as humor to me, at least.

orochimaaru• 2 years ago

I agree. It seemed like humor to me. I have been accused of using off color humor with hyperbole before. So maybe the appeal is limited.

jay-barronville• 2 years ago

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.

kelnos• 2 years ago

Justine seems like a fairly brilliant and creative person, but in production I don't think I'd want to use a libc that's "new" or "rough around the edges".

Getting "so fast" is not my first priority when I run things in production. That's stability, predictability, and reliability. Certainly performance is important: better-performing code can mean smaller infrastructure, which is great from a cost and environmental perspective. But fast comes last.

stonethrowaway• 2 years 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• 2 years ago

I wonder what they (Tunney) think of that now.

01HNNWZ0MV43FF2• 2 years ago

Wild. Then again, in 2012 I was on a grippy sock vacation.

senderista9• 2 years ago

from a self-aggrandizing wikipedia article, I presume?

wallstprog• 2 years 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• 2 years 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.

loeg9• 2 years ago

Atomics mostly map to underlying compiler / CPU intrinsics, not pthreads.

jeffbee2• 2 years 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.

jart15• 2 years 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.

tialaramex11• 2 years 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.

senderista9• 2 years ago

At least in Linux, C++11 atomics use pthreads (not the other way around).

I have no idea what you can possibly mean here.

Edit: Oh, you must have meant the stupid default for large atomic objects that just hashes them to an opaque mutex somewhere. An invisible performance cliff like this is not a useful feature, it's a useless footgun. I can't imagine anyone serious about performance using this thing (that's why I always static_assert() on is_always_lock_free() for my atomic types).

bjourne4• 2 years 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... 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.

gpderetta6• 2 years 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.

bjourne4• 2 years 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.

senderista9• 2 years 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.

amiga3863• 2 years 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...

jitl2• 2 years 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")

amiga3863• 2 years 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.

dist-epoch• 2 years ago

Politics, not-invented-here syndrome, old maintainers.

It takes forever to change something in glibc, or the C++ equivalent.

There are many kinds of synchronization primitives. pthreads only supports a subset. If you are limiting yourself to them, you are most likely leaving performance on the table, but you gain portability.

aseipp• 2 years ago

Those projects often have dozens of other priorities beyond just one specific API, and obsessing over individual APIs isn't a good way to spend the limited time they have. In any case, as a concrete example to disprove your claim, you can look at malloc and string routines in your average libc on Linux.

glibc's malloc is tolerable but fails handily to more modern alternatives in overall speed and scalability (it fragments badly and degrades over time, not to mention it has a dozen knobs that can deeply impact real life workloads like MALLOC_ARENA_MAX). musl malloc is completely awful in terms of performance at every level; in a multithreaded program, using musl's allocator will destroy your performance so badly that it nearly qualifies as malpractice, in my experience.

musl doesn't even have things like SIMD optimized string comparison routines. You would be shocked at how many CPU cycles in a non-trivial program are spent on those tasks, and yes it absolutely shows up in non-trivial profiles, and yes improving this improves all programs nearly universally. glibc's optimized routines are good, but they can always, it seems, become faster.

These specific things aren't "oh, they're hyper specific optimizations for one architecture that don't generalize". These two things in particular -- we're talking 2-5x wall clock reduction, and drastically improved long-term working set utilization, in nearly all workloads for any given program. These are well explored and understood spaces with good known approaches. So why didn't they take them? Because, as always, they probably had other things to do (or conflicting priorities like musl prioritizing simplicity over peak performance, even when that philosophy is actively detrimental to users.)

I'm not blaming these projects or anything. Nobody sets out and says "My program is slow as shit and does nothing right, and I designed it that way and I'm proud of it." But the idea that the people working on them have made only the perfect pareto frontier of design choices just isn't realistic in the slightest and doesn't capture the actual dynamics of how most of these projects are run.

jart15• 2 years ago

musl doesn't even have things like SIMD optimized string comparison routines. You would be shocked at how many CPU cycles in a non-trivial program are spent on those tasks

Building GNU Make with Cosmo or glibc makes cold startup go 2x faster for me on large repos compared to building it with Musl, due to vectorized strlen() alone (since SIMD is 2x faster than SWAR). I sent Rich a patch last decade adding sse to strlen(), since I love Musl, and Cosmo is based on it. But alas he didn't want it. Even though he seems perfectly comfortable using ARM's strlen() assembly.

glibc's malloc is tolerable but fails handily to more modern alternatives in overall speed and scalability

The focus and attention I put into cosmo mutexes isn't unique. I put that care into everything else too, and malloc() is no exception. Cosmo does very well at multi-threaded memory allocation. I can pick benchmark parameters where it outperforms glibc and jemalloc by 100x. I can also pick params where jemalloc wins by 100x. But I'm reasonably certain cosmo can go faster than glibc and musl in most cases while using less memory too. You have Doug Lea to thank for that.

Every day is a good day working on cosmo, because I can always find an opportunity to dive into another rabbit hole. Even ones as seemingly unimportant as clocks: https://github.com/jart/cosmopolitan/commit/dd8544c3bd7899ad...

wrsh074• 2 years ago

Another example is hash maps: all the large companies built better maps in cpp (folly, absl), but the number of apps that are performance sensitive and still use std::unordered_map will be astounding forever.

(Why not upstream? ABI compatibility which is apparently a sufficient veto reason for anything in cpp)

Const-me• 2 years ago

My guess is, because what’s in these current standard libraries and OSes are good enough.

Synchronizing multiple CPU cores together is fundamentally slow, there’s no ways around it. They are far apart on the chip, and sometimes even on different chips with some link between. When measuring time with CPU cycles that latency is rather slow.

Possible to avoid with good old software engineering, and over time people who wanted to extract performance from their multi-core CPUs became good at it.

When you’re computing something parallel which takes minutes, you’ll do great if you update the progress bar at a laughable 5 Hz. Synchronizing cores 5 times each second costs nothing regardless of how efficient is the mutex.

When you’re computing something interactive like a videogame, it’s often enough to synchronize cores once per rendered frame, which often happens at 60Hz.

Another notable example is multimedia frameworks. These handle realtime data coming at high frequencies like 48 kHz for audio, and they do non-trivial compute in these effect transforms and codecs so they need multiple cores. But they can tolerate a bit of latency so they’re just batching these samples. This dramatically saves IPC costs because you only need to lock these mutexes at 100Hz when batching 480 samples = 10ms of audio.

astrange• 2 years ago

They are far apart on the chip, and sometimes even on different chips with some link between.

They aren't always. On a NUMA machine some are closer than others; M-series is an example. The cores are in clusters where some of the cache is shared, so atomics are cheap as long as it doesn't leave the cluster.

monocasa• 2 years ago

When you’re computing something interactive like a videogame, it’s often enough to synchronize cores once per rendered frame, which often happens at 60Hz.

That's not really the right way to do it. If you're actually using multiple cores in your code, you want to build a data dependency graph and let the cores walk that graph. Max node size ends up being something loosely like 10k items to be processed. You'll typically see hundreds of synchronization points per frame.

This is the base architecture of stuff like Thread Building Blocks and rust's rayon library.

leni536• 2 years ago

Are there ABI considerations for changing a pthread mutex implementation?

pnt12• 2 years ago

If it's so good, why haven't all C libraries adopted the same tricks?

A man and a statiscian are walking down the street when they see a 50€ bill. The statistician keeps walking but the man stops and says "hey, look at this cash on the floor?". But the statistician, uninpressed, says: "must be fake, or someone would have already picked it up". And continues walking. The other man grabs the cash and takes it.

Uehreka• 2 years 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?

almostgotcaught4• 2 years 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)

so the answer is simple: i can't think of anyone that wants to ship fat binaries.

fragmede4• 2 years 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.

cycomanic3• 2 years ago

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?

amiga3863• 2 years ago

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 delightful... but the 3-ways-executable magic trick of APE, while really clever, doesn't inspire confidence it'll work forever, and for the most part it doesn't gain you anything. Each platform has their own packaging/signing requirements. You might as well compile a different target for each platform.

0x1ceb00da• 2 years ago

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

fragmede4• 2 years ago

Most people producing cross-platform software don't want a single executable that runs on every platform

They don't? Having one file to download instead of a maze of "okay so what do you have" is way easier than the current mess. It would be very nice not to have to ask users what platform they're on, they just click a link and get the thing.

hyperion2010• 2 years ago

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.

cyberax2• 2 years ago

With that in mind that respect, languages like go letting you cross compile for all your targets (provided you avoid CGO)

Even that is not a big deal in most of cases, if you use zig to wrap CC: https://dev.to/kristoff/zig-makes-go-cross-compilation-just-...

karel-3d• 2 years ago

what worked for me for cross-compiling go:

https://github.com/elastic/golang-crossbuild docker images for macos and windows (not linux though)

https://github.com/rust-cross/rust-musl-cross docker images for linux (yes, it's possible to use the same one for go, you just need to put go binary there) so it's static with musl libc and sure to not have some weird issues with old/new libc on old/new/whatever linuxes

(it might be over the top and the zig thing might effectively do the same thing, but I never got it to compile)

oh and apple-codesign rust cargo to get through the signing nonsense

jkachmar• 2 years ago

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

wmf• 2 years ago

But what's actually bad about it?

sublimefire2• 2 years ago

The problem with this take is that it is not grounded in facts that should determine if the thing is good or bad.

Logically having one thing instead of multiple makes sense as it simplifies the distribution and bytes stored/transmitted. I think the issue here is that it is not time tested. I believe multiple people in various places around the globe think about it and will try to test it. With time this will either bubble up or be stale.

blenderob2• 2 years ago

Is there a catch?

I am only speaking for myself here. While cosmo and ape do seem very clever, I do not need this type of clever stuff in my work if the ordinary stuff already works fine.

Like for example if I can already cross-compile my project to other OSes and platforms or if I've got the infra to build my project for other OSes and platforms, I've no reason to look for a solution that lets me build one binary that works everywhere.

There's also the thing that ape uses clever hacks to be able to run on multiple OSes. What if those hacks break someday due to how executable formats evolve? What if nobody has the time to patch APE to make it compatible with those changes?

But my boring tools like gcc, clang, go, rust, etc. will continue to get updated and they will continue to work with evolving OSes. So I just tend to stick with the boring. That's why I don't bother with the clever because the boring just works for me.

sublimefire2• 2 years ago

If the executable format changes then it would affect more than just ape/cosmopolitan. All of the old binaries would just stop working.

tangus• 2 years ago

Last year I needed to make a small webapp to be hosted on a Windows server, and I thought RedBean would be ideal for it. Unfortunately it was too buggy (at least on Windows).

I don't know whether RedBean is production-ready now, but a year and a half ago, that was the catch.

jart15• 2 years ago

Give the latest nightly build a try: https://cosmo.zip/pub/cosmos/bin/ Windows has been a long hard march, but we've recently hit near feature completion. As of last month, the final major missing piece of the puzzle was implemented, which is the ability to send UNIX signals between processes. Cosmopolitan does such a good job on Windows now that it's not only been sturdy for redbean, but much more mature and complicated software as well, like Emacs, GNU Make, clang, Qt, and more.

dundarious2• 2 years ago

Mozilla llamafile uses it. Bundles model weights and an executable into a single file, that can be run from any cosmo/ape platform, and spawns a redbean http server for you to interact with the LLM. Can also run it without the integrated weights, and read weights from the filesystem. It's the easiest "get up and go" for local LLMs you could possibly create.

cowsandmilk• 2 years ago

Mozilla’s llamafile is primarily developed by jart. I wouldn’t view it as anyone else actually using cosmo/ape

sfn42• 2 years ago

Most people aren't writing C as far as I know. We use Java, C#, Go, Python etc, some lunatics even use Node.

We generally don't care if some mutex is 3x faster than some other mutex. Most of the time if I'm even using a mutex which is rare in itself, the performance of the mutex is generally the least of my concerns.

I'm sure it matters to someone, but most people couldn't give two shits if they know what they're doing. We're not writing code where it's going to make a noticeable difference. There are thousands of things in our code we could optimize that would make a greater impact than a faster mutex, but we're not looking at those either because it's fast enough the way it is.

secondcoming3• 2 years ago

What a pointless contribution

int_19h12• 2 years ago

Mozilla has a project called Llamafile (https://github.com/Mozilla-Ocho/llamafile) that's based on Cosmopolitan libc. And they do regularly publish popular models repackaged in that format on Hugging Face: https://huggingface.co/models?search=llamafile.

Whether that in turn has any practical use beyond quickly trying out small models is another question.

gavindean902• 2 years ago

Tbh I don’t know that there is a catch except that there is one core person behind whole project. I like that there are fresh ideas in the C space.

fragmede4• 2 years ago

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?

If I went up to you in 2008, and said, hey, lets build a database that doesn't do schemas, isn't relational, doesn't do SQL, isn't ACID compliant, doesn't to joins, has transactions as an afterthought, and only does indexing sometimes, you'd think I was trolling you. And then in 2009, Mongodb came out and caught on in various places. So only time will tell if these are ingenious tools that haven't caught on yet. There's definitely a good amount of genius behind it, though only time will tell if it's remembered in the vein of tom7's harder drives or if it sees wider production use. I'll say that if golang supported it as a platform, I'd switch my build pipelines at work over to it, since it makes their output less complicated to manage as there's only a single binary to deal with instead of 3-4.

1st1• 2 years 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_pa...

jart15• 2 years 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• 2 years 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.

TinkersW2• 2 years 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• 2 years ago

And here I thought musl was better than libc sigh

favorited2• 2 years 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• 2 years 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?

akira2501• 2 years 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• 2 years 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?

TinkersW2• 2 years 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• 2 years 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• 2 years ago

https://randomascii.wordpress.com/2017/07/09/24-core-cpu-and...

dumdood• 2 years 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.

xxs8• 2 years 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• 2 years ago

Mutices.

Akhilmurali• 2 years ago

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

yencabulator3• 2 years ago

More than one core.

petermcneeley• 2 years ago

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

scudsworth• 2 years 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..

SleepyMyroslav• 2 years 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• 2 years 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.

loeg9• 2 years 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• 2 years 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• 2 years 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.p...

Hendrikto• 2 years 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• 2 years ago

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

peter_d_sherman• 2 years ago

https://en.wikipedia.org/wiki/C10k_problem

https://web.archive.org/web/20130722134723/http://www.kegel....

deviantbit• 2 years 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• 2 years 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!

The Fastest Mutexes

Related Stories