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

171–180 of 360 posts

Re: The Fastest Mutexes

#171

Post by pizlonator »

ot wrote: post #168
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…

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

You do need a fence in the unlock path though (at least a release fence).

I think the issue is that if you ask the CPU to just store something (like in a spin lock), whether or not there’s a fence, it’s an operation with limited data flow dependencies so it’s easy for the CPU to execute. Even the fence can be handled using wacky speculation tricks.

But if you want to do something like, “store this value but only if the old value satisfies some predicate”, then there’s a load and the whole thing is dependent on the load. So you’re asking the CPU to load, then run a predicate, then store, and for that to be fenced, and atomic.

Strictly more work. I don’t think there’s any trick to make it faster than just the store release.

Re: The Fastest Mutexes

#172

Post by 01HNNWZ0MV43FF »

stonethrowaway wrote: post #38

> 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

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

Re: The Fastest Mutexes

#173

Post by Animats »

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…

> 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 operations can force this. Two orders of magnitude performance drops ensue when multi-threaded programs are contending for that lock.[1]

Inside one of the lock loops is a call to "YieldProcessor".

    static void spin_lock( LONG *lock )
    {
         while (InterlockedCompareExchange( lock, -1, 0 ))
             YieldProcessor();
    }
But the actual code for YieldProcessor is a NOP on x86:[2]

    static FORCEINLINE void YieldProcessor(void)
    {
        #ifdef __GNUC__
        #if defined(__i386__) || defined(__x86_64__)
             __asm__ __volatile__( "rep; nop" : : : "memory" );
        #elif defined(__arm__) || defined(__aarch64__)
            __asm__ __volatile__( "dmb ishst\n\tyield" : : : "memory" );
        #else
            __asm__ __volatile__( "" : : : "memory" );
        #endif
        #endif
    }
}

Wine devs are aware of this, but the mess is bad enough that no one has tackled it. This is down in the core of what "malloc" calls, so changes there could have unexpected effects on many programs. Needs attention from someone really into mutexes.

[1] https://forum.winehq.org/viewtopic.php?t=37688

[2] https://gitlab.winehq.org/wine/wine/-/blob/HEAD/include/winn...

Re: The Fastest Mutexes

#174

Post by sgarland »

jeffbee wrote: post #49
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…

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

> C, a useless language

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

Re: The Fastest Mutexes

#175

Post by vitus »

loeg wrote: post #54
kccqzy wrote: post #2

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

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

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

Re: The Fastest Mutexes

#176

Post by dwattttt »

jrockway wrote: post #149
cyberax wrote: post #141

Earlier quoted context omitted.

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

Does this still work? The article is from 2021 but when I last tried it this year, Go appeared to (newly) depend on headers that Zig doesn't need and thus it doesn't work. The Github issue was something like "yeah, we don't need those, so I guess Go doesn't work anymore". Without the actual error message I can't find the issue, however, so maybe I imagined this.

I believe these are the issues: https://github.com/golang/go/issues/52690 https://github.com/ziglang/zig/issues/14989

Re: The Fastest Mutexes

#177

Post by cogman10 »

forrestthewoods wrote: post #134
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…

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.

Depends on the dictionary implementation. There's a number of thread safe dictionaries in the wild with varying degrees of parallelism performance. Pretty much all of them benefit from faster mutexes.

For example, some thread safe dictionaries will segment their underlying key/value pairs which allows them to have concurrent reads and writes for a given segment which significantly improves performance.

Re: The Fastest Mutexes

#178

Post by sfn42 »

Uehreka wrote: post #68

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

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.

Re: The Fastest Mutexes

#179

Post by loeg »

jart wrote: post #75
loeg wrote: post #63

Earlier quoted context omitted.

Uh, why do you say a naive spin lock would use xchg instead of cmpxchg? I don't think you could make a valid spinlock using xchg.

On x86 you can. When xchg is used with a memory parameter it locks the bus. This is true even in the absence of a lock prefix. I included a spinlock implementation in the blog post. If you see any errors with it, then please let me know!

Oh, sure, your 1-bit spinlock with no other state works.

Re: The Fastest Mutexes

#180

Post by markdoubleyou »

TinkersW wrote: post #166
kgeist wrote: post #158

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

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

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

Post reply on HN