The Fastest Mutexes
301–310 of 360 posts
Re: The Fastest Mutexes
#302Earlier quoted context omitted.
Just to clarify: the spinning on CMPXCHG is not also a bad idea, the YieldProcessor is correct (a pause), but inside the CMPXCHG loop it should be spinning on a pure unlocked load. Is that correct?
No you should spin on a read. Once you see the value you want you then try the CMPXCHG. If that succeeds you exit. If it fails you go back to spinning on the read.
What is the difference between a read and a “load” here?
Re: The Fastest Mutexes
#303Earlier quoted context omitted.
> 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`. This is something I've thinking about a lot over time, that the CAS is only there to atomically determine if there are any sleeping waiters on unlock and you h…
There's two I've tried to do this: - On the wait side, do the CAS to set the "waiter present" bit. Down unlock, do a (relaxed) read of the lock word, and if "waiter present" isn't set, just do a release store to unlock (and go down some slow CAS-y wake path if a waiter is present). On the wait side, never do an un-timed futex wait; just do a series of timed waits, with increasing wait times (so that you still eventua…
> Split out the "waiter present" bit into its own byte, do a store-load sequence (with just a compiler reordering fence) to check for waiters, and have waiters either do a membarrier() syscall or wait "long enough" that they're sure they've gotten the same effect. (This gets tricky w.r.t. mutex lifetime though; you either need out of band lifetime knowledge or to use RCU or whatever and indirect through pointers).
If you are doing this, given the cost of membarrier, you are optimizing for almost always uncontended locks. At this point you can make your lock default-owned by the first thread to lock it and have the owner lock and unlock be basically free until it is contended. This is basically the biased locking optimization that Java implements (or used to).
Re: The Fastest Mutexes
#304Earlier quoted context omitted.
Just to clarify: the spinning on CMPXCHG is not also a bad idea, the YieldProcessor is correct (a pause), but inside the CMPXCHG loop it should be spinning on a pure unlocked load. Is that correct?
Spinning with pause is slower than spinning with sched_yield according to every test I’ve ever done
For what it is worth it seems the library in question does both, uses an exponential retry loop, busy read looping 2^i times for the first 7 attempts before then yielding. It seems like there must be some threshold where latency is improved by retrying before yielding, but I don’t test these things for a living.
https://github.com/google/nsync/blob/c6205171f084c0d3ce3ff51...
Re: The Fastest Mutexes
#305Earlier quoted context omitted.
To add to this, as the original/lead author of a desktop app that frequently runs with many tens of threads, I'd like to see numbers on performance in non-heavily contended cases . As a real-time (audio) programmer, I am more concerned with (for example) the cost to take the mutex even when it is not already locked (which is the overwhelming situation in our app). Likewise, I want to know the cost of a try-lock opera…
Totally! Pro tip: if you really do know that contention is unlikely, and uncontended acquisition is super important, then it's theoretically impossible to do better than a spinlock. Reason: locks that have the ability to put the thread to sleep on a queue must do compare-and-swap (or at least an atomic RMW) on `unlock`. But spinlocks can get away with just doing a store-release (or just a store with a compiler fence…
biased locking can be faster than spinlocking, in the uncontended case
unbiasing/re-biasing a lock can be quite heavy, though. JVM did it by pausing threads (or waiting for GC to do so)
Re: The Fastest Mutexes
#306Earlier quoted context omitted.
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.
Mozilla’s llamafile is primarily developed by jart. I wouldn’t view it as anyone else actually using cosmo/ape
Yes I should have mentioned that, even when I originally interpreted the OP to be asking about other projects using it, not necessarily other people. But they almost certainly meant other people not other projects, so my point is kind of void.
Although in fairness, the Mozilla org choosing Justine/cosmo is basically the kind of sign-off from a 3rd party that OP was looking for.
Re: The Fastest Mutexes
#307[flagged]
Re: The Fastest Mutexes
#308This 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.
Re: The Fastest Mutexes
#309Earlier quoted context omitted.
Lots of code is 'lock free' and uses the same pattern (more or less). Attempt the change optimistically, if it fails spin it, if it keeps failing (Massive Contention), back off.
A properly lock-free architecture wouldn’t have spin-locks, no?
A properly lock-free architecture is a spin-lock :-)
Re: The Fastest Mutexes
#310Earlier quoted context omitted.
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…
> just make sure you `sched_yield` before each retry Assuming `sched_yield` does something. There's a futex congestion problem inside Wine's memory allocator. There are several levels of locks. If you're growing a buffer, in the sense of C's "realloc", and no buffer is available, memory allocation is locked during the allocation of a bigger buffer, copying of the contents, and release of the old buffer. "Push" type o…
> But the actual code for YieldProcessor is a NOP on x86:[2]
> __asm__ __volatile__( "rep; nop" : : : "memory" );
It might look like a NOP, but "REP NOP" is not a real NOP, it's the PAUSE instruction (which very old processors from the 1990s treated as a normal NOP).