Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Fastest Mutexes

justine.lol

Post reply on HN
Print view View original

111–120 of 360 posts

Re: The Fastest Mutexes

#111

Post by foobiekr »

jart wrote: post #14
tombert wrote: post #4

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, jus…

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.

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.

Re: The Fastest Mutexes

#112

Post by ngoldbaum »

pizlonator wrote: post #23

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

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.

Re: The Fastest Mutexes

#113

Post by another-acct »

fefe23 wrote: post #92
jonathrg wrote: post #34

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

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

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

Re: The Fastest Mutexes

#114

Post by PaulDavisThe1st »

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

Earlier quoted context omitted.

To add to this, as the original/lead author of a desktop app that frequently runs with many tens of threads, I'd like to see numbers on performance in non-heavily contended cases . As a real-time (audio) programmer, I am more concerned with (for example) the cost to take the mutex even when it is not already locked (which is the overwhelming situation in our app). Likewise, I want to know the cost of a try-lock opera…

Totally! Pro tip: if you really do know that contention is unlikely, and uncontended acquisition is super important, then it's theoretically impossible to do better than a spinlock. Reason: locks that have the ability to put the thread to sleep on a queue must do compare-and-swap (or at least an atomic RMW) on `unlock`. But spinlocks can get away with just doing a store-release (or just a store with a compiler fence…

We use spinlocks where appropriate. In the 90s I recall that the general rule of thumb was if the lock is held for The more common pattern in rt/audio code is "try to take the lock, but have an alternate code path if that fails". It's not that is never going to be contention, but it will be extremely rare, and when it occurs, it probably matters. RWLocks are also a common pattern, with the RT thread(s) being read-only (and still being required to fall back on an alternate code path if the read lock cannot be taken).

Re: The Fastest Mutexes

#115

Post by tombert »

f1shy wrote: post #19
cogman10 wrote: post #8

Earlier quoted context omitted.

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

Maybe because I had a complete semester of multiprogramming in the uni, I see almost trivial to work in such environments, and cannot comprehend why is so much mystic and voodo. Actually is pretty simple.

I feel like it's not terribly hard to write something that more or less works using mutexes and the like, but I find it exceedingly hard to debug. You're at the mercy of timing and the scheduler, meaning that often just throwing a breakpoint and stepping through isn't as easy as it would be with a sequential program.

I feel like with a queue or messaging abstraction, it can be easier to debug. Generally your actual work is being done on a single thread, meaning that traditional debugging tools work fine, and as I've said in sibling comments, I also just think it's easier to reason about what's going on.

Re: The Fastest Mutexes

#116

Post by pizlonator »

PaulDavisThe1st wrote: post #114
pizlonator wrote: post #106

Earlier 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…

We use spinlocks where appropriate. In the 90s I recall that the general rule of thumb was if the lock is held for The more common pattern in rt/audio code is "try to take the lock, but have an alternate code path if that fails". It's not that is never going to be contention, but it will be extremely rare, and when it occurs, it probably matters. RWLocks are also a common pattern, with the RT thread(s) being read-onl…

These days, fast lock implementations use the following rough idiom, or some idiom that is demonstrably not any slower even for short critical sections.

    if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return;
    for (unsigned i = 0; i
So, the reason to use spinlocks isn't that they are faster for short critical sections, but that they don't have to CAS on unlock - and so they are faster especially in the uncontended case (and in all other cases too).

In other words, the modern rule of thumb is something like: if you're going to grab the lock so frequently that the uncontended lock/unlock time shows up as a significant percentage of your execution time, then use a spinlock. That probably implies that you are probably holding the lock for <100x or even <1000x context switch time, or something around there.

Re: The Fastest Mutexes

#117

Post by miohtama »

ngoldbaum wrote: post #112
pizlonator wrote: post #23

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

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.

Any rough summary?

Re: The Fastest Mutexes

#118

Post by another-acct »

cogman10 wrote: post #31
jart wrote: post #14

Earlier quoted context omitted.

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.

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 t…

Might want to move foo.add() out of the lock scope (assuming foo is a thread-private resource):

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

Re: The Fastest Mutexes

#119

Post by intelVISA »

pizlonator wrote: post #23

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

Fast locks are an oxymoron vs optimized CAS

Re: The Fastest Mutexes

#120

Post by intelVISA »

almostgotcaught wrote: post #69
jonathrg wrote: post #34

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

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

Ironic given the generous size of the average Go binary.
Post reply on HN