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

131–140 of 360 posts

Re: The Fastest Mutexes

#131

Post by lilyball »

tialaramex wrote: post #81
SkiFire13 wrote: post #77

Earlier quoted context omitted.

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

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 .

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

Re: The Fastest Mutexes

#132

Post by cogman10 »

kccqzy wrote: post #123
cogman10 wrote: post #17

Earlier quoted context omitted.

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

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

Yup.

Message passing has allocation pressure and cache consistency pressure not present in using a shared message location. Especially as the amount of memory in question goes up, the benefit of a shared location increases in terms of the performance impact.

Sure, for something silly like writing to an int, there is negative benefit in a shared location, but when you start talking about a dictionary with 1 million entries, the shared location becomes much more of a benefit vs all the copying and allocating you'd have to do if you tried to do the same thing with message passing.

For some datastructures, it's the optimal way to move data around. For example, LMAX disruptor is about the fastest way to pass messages because of the shared memory and well tuned locks.

Re: The Fastest Mutexes

#133

Post by ngoldbaum »

miohtama wrote: post #117
ngoldbaum wrote: post #112

Earlier quoted context omitted.

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?

https://github.com/numpy/numpy/issues/26510#issuecomment-229...

And now that I look at that again I realize I forgot to finish that up!

Re: The Fastest Mutexes

#134

Post by forrestthewoods »

cogman10 wrote: post #17
forrestthewoods wrote: post #11

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

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

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.

Re: The Fastest Mutexes

#135

Post by pizlonator »

lilyball wrote: post #125
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…

On Darwin, it's possible for a pure spinlock to produce a priority inversion deadlock, because Darwin has a quality of service implementation in the kernel that differs from how everyone else handles thread priority. In other kernels, a low-priority thread will still eventually be guaranteed a cpu slice, so if it's holding a spinlock, it will eventually make progress and unlock. On Darwin with Quality of Service, it'…

I’ve shipped code on Darwin that spinlocks and gets away with it without any noticeable cases of this happening.

I know it can happen in theory. But theory and practice ain’t the same.

I worked for Apple when I shipped this too lmao

Re: The Fastest Mutexes

#136

Post by jcranmer »

cogman10 wrote: post #52
tialaramex wrote: post #37

Earlier quoted context omitted.

> Not too sure what the basic rules are and I'm not able to find any list of such rules. The actual rules are completely terrifying because they involve the physics of microprocessors. If you've watched Grace Hopper's lectures where she gives out physical nanoseconds (pieces of wire that are the same length as the distance light travels in a nanosecond, thus, the maximum possible distance data could travel in that ti…

Are there popular languages that don't have memory models which make reasoning about concurrent models easier? A language with a notion of threading and shared state is going to have something akin to read/write barriers built into the language memory model to tame the beast.

I think tialaramex is overselling the complexity of concurrent memory models in practice, at least for end users. In reality, all modern memory models are based on the data-race-free theorem, which states that in the absence of data races--if your program is correctly synchronized--you can't tell that the hardware isn't sequentially consistent (i.e., what you naïvely expected it to do).

Correct synchronization is based on the happens-before relation; a data race is defined as a write and a conflicting read or write such that neither happens-before the other. Within a thread, happens-before is just regular program order. Across a thread, the main happens-before that is relevant is that an release-store on a memory location happens-before an acquire-load on that memory location (this can be generalized to any memory location if they're both sequentially-consistent, but that's usually not necessary).

The real cardinal rule of concurrent programming is to express your semantics in the highest-possible level of what you're trying to do, and find some library that does all the nitty-grityy of the implementation. Can you express it with fork-join parallelism? Cool, use your standard library's implementation of fork-join and just don't care about it otherwise.

Re: The Fastest Mutexes

#137

Post by samatman »

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…

This is one of the areas where Zig's combination of anonymous blocks and block-based defer really pay off. To create a locked region of code is just this

    {
        mutex.lock();
        defer mutex.unlock();
        // Do mutex things
    }
It's possible to get this wrong still, of course, but both the anonymous scope and the use of `defer` make it easier to get things right.

Nothing can prevent poor engineering around mutex use though. I'd want a critical path for a concurrent hashmap to look like this:

    {
        shared_map.lock();
        defer shared_map.unlock();
        if (shared_map.getOrNull(foo) == null) {
            shared_map.put(foo, new_val);
        }
    }
Where the SharedMap type has an internal mutex, and a way to check it, and all operations panic if no lock has been acquired. It could have `shared_map.lockAndGet(OrNull?)(...)`, so that the kind of problem pattern you're describing would stand out on the page, but it's still a one-liner to do an atomic get when that's all you need the critical path to perform.

I don't think these invariants are overly onerous to uphold, but one does have to understand that they're a hard requirement.

Re: The Fastest Mutexes

#138

Post by bjourne »

hyperion2010 wrote: post #107
amiga386 wrote: post #82

Earlier quoted context omitted.

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

> Most people We'll I'm used to not being most people, but I'd much rather be able to produce a single identical binary for my users that works everywhere than the platform specific nonsense I have to go through right now. Having to maintain different special build processes for different platforms is a stupid waste of time. Frankly this is how it always should have worked except for the monopolistic behavior of vari…

The binary is only one part of the puzzle (and largely solved by WSL). Installation/uninstallation and desktop integration is just as much of a hassle.

Re: The Fastest Mutexes

#139

Post by hinkley »

foobazgt wrote: post #87
hinkley wrote: post #50

Earlier quoted context omitted.

Composing locks is where Java usually blows up. And computeIfAbsent can end up holding the lock for too long if the function is slow.

Composing locks isn't a Java problem - it's a fundamental abstraction problem with locks. This is one of the reasons why you usually reach for higher level abstractions than mutexes. > And computeIfAbsent can end up holding the lock for too long if the function is slow. How is this different from any other lock-holding code written anywhere?

I’m saying Java is exceptionally bad at this because every object is its own mutex.

And you end up having to trade single core performance for multi core by deciding to speculatively calculate the object. If there’s no object to make the critical section is very small. But as the object sprouts features you start smashing face first into Amdahl.

Re: The Fastest Mutexes

#140

Post by jhatemyjob »

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…

I digress but my autistic brain couldn't help itself. Provided that it's a recursive lock you could do this instead of adding a new method `foo.BarBaz`

    foo.lock {
        value = foo.bar() // foo.lock within this method is ignored
        if(value.bat()) {
            foo.baz() // foo.lock within this method is ignored
        }
    }
Also, to catch this bug early, you could assert foo is locked in `value.bat` or something. But that may or may not be feasible depending on how the codebase is structured
Post reply on HN