Live data from Hacker News

The Fastest Mutexes

justine.lol

331–340 of 360 posts

Re: The Fastest Mutexes

#331

Earlier quoted context omitted.

The more useful question is has it been expunged from the JDK and common libraries. I think it's been more like 10-12 years since it really started being talked about in more than certain subcommunities and that's almost 20 years' worth of existing libraries. OpenTelemetry is a fairly recent library. Even if you ignore some test fakes (where, let's face it, who cares), it still uses it in a few places, and uses lock…

Some amount of legacy cruft is not unexpected, but it's sad that it can be seen in new code. In .NET, which has similarly problematic semantics with lock(), linters have been flagging lock(this) for ages. I wonder where this patently bad idea of every object carrying its own publicly accessible mutex originated in the first place. Did Java introduce it, or did it also copy that from somewhere else? And what was the m…

Monitors came from Tony Hoare in the 70s and Java put an OO spin on them.

Re: The Fastest Mutexes

#332
post #64

Earlier quoted context omitted.

> Please use the C/C++ memory model facilities instead I should point out that for more than half of my professional career, those facilities did not exist, so volatile was the most portable way of implementing e.g. a spinlock without the compiler optimizing away the check. There was a period after which compilers were aggressively inlining and before C11 came out in which it could be otherwise quite hard to otherwis…

The problem is that volatile alone never portably guaranteed atomicity nor barriers, so such a spinlock would simply not work correctly on many architectures: other writes around it might be reordered in a way that make the lock useless. It does kinda sorta work on x86 due its much-stronger-than-usual guarantees wrt move instructions even in the absence of explicit barriers. And because x86 was so dominant, people co…

There's a lot to unpack here.

TL;DR: The compiler can reorder memory accesses and the CPU can reorder memory accesses. With a few notable exceptions, you usually don't have to worry about the latter on non-SMP systems, and volatile does address the former.

The volatile qualifier makes any reads or writes to that object a side-effect. This means that the compiler is not free to reorder or eliminate the accesses with respect to other side-effects.

If you have all 3 of:

A) A type that compiles down to a single memory access

B) within the same MMU mapping (e.g. a process)

C) With a single CPU accessing the memory (e.g. a non-SMP system)

Then volatile accomplishes the goal of read/writes to a shared value across multiple threads being visible. This is because modern CPUs don't have any hardware concept of threads; it's just an interrupt that happens to change the PC and stack pointer.

If you don't have (A) then even with atomics and barriers you are in trouble and you need a mutex for proper modifications.

If you don't have (B) then you may need to manage the caches (e.g. ARMv5 has virtually tagged caches so the same physical address can be in two different cache lines)

If you don't have (C) (e.g. an SMP system) then you need to do something architecture specific[1]. Prior to C language support for barriers that usually means a CPU intrinsic, inline assembly, or just writing your shared accesses in assembly and calling them as functions.

Something else I think you are referring to is if you have two shared values and only one is volatile, then the access to the other can be freely reordered by the compiler. This is true. It also is often masked by the fact that shared values are usually globals, and non-inlined functions are assumed by most compilers to be capable of writing to any global so a function call will accidentally become a barrier.

1: As you mention, on the x86 that "something" is often "nothing." But most other architectures don't work that way.

Re: The Fastest Mutexes

#333
post #48

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

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.

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.

Re: The Fastest Mutexes

#334

Earlier quoted context omitted.

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

This doesn't seem to add anything over and above what std::mutex in C++ or a synchronized block in Java offer?

Less than C++. defer() is strictly inferior to RAII.

Re: The Fastest Mutexes

#335
post #5
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…

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.

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

Re: The Fastest Mutexes

#336

> 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

from a self-aggrandizing wikipedia article, I presume?

Re: The Fastest Mutexes

#337

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

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

Re: The Fastest Mutexes

#338
post #48

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

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.

Re: The Fastest Mutexes

#339
post #315

Earlier quoted context omitted.

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…

> 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. Yeah, and maybe also consider changing your design because usually this isn't needed.

This is (in my experience) a byproduct of good design, so changing the design wouldn't be a great idea.

Every time I've seen this happen it's in code that scales really well to lots of CPUs while having a lot of shared state, and the way it gets there is that it's using very fine-grained locks combined with smart load balancing. The idea is that the load balancer makes it improbable-but-not-impossible that two processors would ever want to touch the same state. And to achieve that, locks are scattered throughout, usually protecting tiny critical sections and tiny amounts of state.

Whenever I've gotten into that situation or found code that was in that situation, the code performed better than if it had coarser locks and better than if it used lock-free algorithms (because those usually carry their own baggage and "tax"). They performed better than the serial version of the code that had no locks.

So, the situation is: you've got code that performs great, but does in fact spend maybe ~2% of its time in the CAS to lock and unlock locks. So... you can get a tiny bit faster if you use a spinlock, because then unlocking isn't a CAS, and you run 1% faster.

Re: The Fastest Mutexes

#340

Earlier quoted context omitted.

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…

Keep in mind that while try_lock() is realtime-safe, the following unlock() may not, as it may need to wake threads that have been blocked in the meantime! So I would only use this pattern for situations where the very fact that a NRT thread tries to acquire the lock already means that RT safety is not a concern anymore (e.g. a device has been disconnected)

Excellent reminder. Yes, this is both a design defect of try/unlock that can't really be solved, and an implementation defect on several platforms that makes it worse than it actually needs to be (Windows, I'm looking at you)
Post reply on HN