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

241–250 of 360 posts

Re: The Fastest Mutexes

#241

Post by gpderetta »

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…

As far as I know it is a fundamental limitation. You need to release the mutex, then check that there were no waiters in this order not to miss wakeups. As the mutex release must be globally visible before the load, release ordering on the mutex is not sufficient as the load could be reordered before the unlock; hence you need a StoreLoad fence which is always the most expensive barrier.

Consider the implementation of Dekker's algorithm for example.

Re: The Fastest Mutexes

#242

Post by [deleted] »

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…

[deleted]

Re: The Fastest Mutexes

#243

Post by leni536 »

amiga386 wrote: post #58

If it's so good, why haven't all C libraries adopted the same tricks? My betting is that its tricks are only always-faster for certain architectures, or certain CPU models, or certain types of workload / access patterns... and a proper benchmarking of varied workloads on all supported hardware would not show the same benefits. Alternatively, maybe the semantics of the pthread API (that cosmopolitan is meant to be imp…

Are there ABI considerations for changing a pthread mutex implementation?

Re: The Fastest Mutexes

#244

Post by favorited »

EasyMark wrote: post #219
favorited wrote: post #152

Earlier quoted context omitted.

musl is a libc, and while it is superior in some ways, it is inferior in others. If you want a statically linked libc, or a permissively licensed libc, musl is a fantastic choice. If you want a libc with the fastest malloc implementation, you'll probably want to look elsewhere.

Can’t you sub in your own malloc like the one in the article or jemalloc if you don’t like the performance of the original in your app?

Sure, and lots of projects do. I was just trying to make the point that there isn't one "good" libc that is universally better – each project has costs and benefits that are tied to its priorities.

Re: The Fastest Mutexes

#246

Post by neonsunset »

int_19h wrote: post #228
hinkley wrote: post #223

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…

Can't attest to the history of `lock` statement from the top of my head but the API shape of lock and Monitor.Enter/Exit methods it is desugared to looks like Win32's EnterCriticalSection and LeaveCriticalSection. Other Monitor's methods like Wait and Pulse look like pthread's condvar and mutex functions.

.NET also has MethodImplOptions.Synchronized like Java does. However, the only place I have ever seen this attribute was on TextWriter.Synchronized implementation in CoreLib and nowhere else.

Java itself has `Lock` and `Condition`. In the end, most synchronization primitives do the same high-level actions and bound to end up having similar API.

As for `lock(this)`, much like with many other historically abused techniques that have become frowned upon - it's not bad per se if you own the type and know that it is internal and will not be observed outside of the assembly it is defined in, provided it is small enough. It's footgun-prone, but generally very few code paths will lock an arbitrary object instance at all, so most of the time it's something you see so rarely it has become "just write a comment why and move on" when using it. Of course this requires more deliberation and it's easier to default to blanket policies that ignore context. It can be difficult to get people to "use the appropriate tool" mentality.

.NET is also getting it's a separate `Lock` type, on top of all the existing synchronization primitives, to move a little further away from other legacy aspects of `lock`ing on object instances.

Re: The Fastest Mutexes

#247

Post by fulafel »

PaulDavisThe1st wrote: post #85
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,…

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…

I'm sure you know but this is the opposite of what real-time conventionally means (you have hard deadlines -> worst case is the chief concern).

Re: The Fastest Mutexes

#248

Post by [deleted] »

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…

[deleted]

Re: The Fastest Mutexes

#249

Post by jart »

int_19h wrote: post #216
jart wrote: post #205

Earlier quoted context omitted.

Yes that's exactly what we need. And we'll be laughing to the bank when we bundle a browser toolbar with adware into its installer ten years down the road. Oh wait Java already did this. OTOH Cosmopolitan gives you complete autonomy. You don't need a JVM to run a simple native command line program on multiple OSes and I proved that.

JVM bytecode is obviously not what I was talking about - it is neither low-level (if you can't efficiently compile the entirety of C into it, it's not good enough for this purpose), nor did it ever have universal first-class OS support. And stuff like https://github.com/jart/cosmopolitan/issues/1263 shows that just because it works today, it doesn't mean that it'll work tomorrow. What's the guarantee that the same wo…

I agree. As a user you should have those guarantees. Here's how I'm helping you get them.

- With Windows, APE is just PE and WIN32 so those are already guaranteed by Microsoft.

- With Linux, I've been working with kernel maintainers to build consensus around around a patch https://justine.lol/ape.patch that will let your APE binaries be loaded by binfmt_elf. This will provide you with a guarantee that they'll still work, even if someone has for instance registered a binfmt_misc entry like WINE that's intercepting MZ executables.

- With FreeBSD, I'm also working to build consensus here around another patch, that will help the kernel load APE natively as a normal ELF executable. That means you won't need to rely on the system shell to load your program into memory.

- I've been writing a specification for APE that documents this file format, its ABI, and its historical encodings. https://github.com/jart/cosmopolitan/blob/master/ape/specifi...

One day in the future, when we have the support of major OSes for the native loading of portable binaries, we'll look back at the APE shell script bootstrapping process similar to how we look back at self-extracting zip archives. When Phil Katz first invented PKZIP, it was useful to prepend the software to each archive. But nowadays it isn't necessary, since all OSes come with support for PKZIP built in.

Re: The Fastest Mutexes

#250

Post by adgjlsfhk1 »

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…

> Message passing is just outsourcing the lock, right?

Kind of. If you can architect such that each channel has exactly 1 reader and 1 writer, you can send messages in a single direction with no locks. The basic idea is that you have a circular buffer with a start index and an end index. The writer can write an element and increment the end index (as long as end index+1<start index which doesn't have to be done atomically), while the reader can just read an element and increment the start index (as long as start index +1 < end index). This strategy needs to use atomic operations (which are basically free when uncontested, which they will be as long as the queue has a few elements in it)

Post reply on HN