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

291–300 of 360 posts

Re: The Fastest Mutexes

#291

Post by ninkendo »

pizlonator wrote: post #135
lilyball wrote: post #125

Earlier quoted context omitted.

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

Also worked for Apple for 13 years: there is a lot (and I mean a LOT) of priority inversions and abuse of locks in the codebase. Breaking out the internal profiler and actually having a look at whether you were running at the priority you thought can be a very illuminating thing.

One particular app had a particularly nasty habit of losing priority because most of its work was done in a set of daemons and not in the UI process itself. The foreground app is allowed to use Performance cores and receive USER_INTERACTIVE priority for operations if it wants, but daemons cannot unless they have a mach IPC voucher stating that the UI is blocked on their work. But if you do the wrong thing with a semaphore or a spinlock, you get booted out of the thread group and now you’re running on Efficiency cores at USER_INITIATED priority and suddenly your latency numbers spike 10x on systems with asymmetric cores. I remember solving a particularly bad one which was basically doubling our request latency on phones with E cores.

The company had a pretty widely spread internal article trying to whack people over the head to stop abusing lock primitives in this way, but we just kept shipping code with this issue.

(Most of the inversion issues came from the use of semaphores though. The problem got 1000x worse in swift concurrency because using semaphores blocks an entire SC OS thread and you only get as many of those as you have cores. Most Apple Watches and HomePod only have 2 of them so you can easily deadlock. Which most people fixed by just… adding a timeout to their locks. It was horrifying.)

Re: The Fastest Mutexes

#292

Post by gpderetta »

gpderetta wrote: post #241
ot wrote: post #168

Earlier quoted context omitted.

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

As a more practical argument, let's suppose x86 had a an atomic CAS that guarantees that the store is released but the load is relaxed (unlike other x86 normal loads, but like non-temporal loads, it has no implied LoadLoad or LoadStore like other x86 loads).

This relaxed-load-CAS, coupled with some form of control or data dependency would be sufficient to implement your mutex. But would such a CAS be significantly cheaper than the existing CAS? If it was, you would be able to approximate the strong CAS semantics by adding lfence+sfence after the relaxed CAS. These fences are cheap, so if strong CAS was possible to be implemented this way with significant improvements, intel would have already done it.

Finally, it is practically possible to implement the sequence store(A);#StoreLoad;load (B) without an explicit fence by using the colocation trick: have A and B be adjacent in memory (on the same cacheline), store to A, then do a wider load on both A and B. Intel does not give multithread guarantees on this, but my understanding is that it works: the wider load fails to be store-forwarded and stalls the pipeline waiting for the previous store to be flushed. In practice this costs about as much as a fence, so in addition to being undefined, is not cheaper.

Re: The Fastest Mutexes

#294

Post by matheusmoreira »

int_19h wrote: post #197
0x1ceb00da wrote: post #89

Earlier quoted context omitted.

Wasn't elf format modified by upstream to accomodate for cosmo? That makes it kinda official. Still hard to see a use case for it. If you want everyone to be able to run your program, just write a web app, a win32 program, or a java applet. 20 years old java applets still run on modern JVMs.

A web app is, well, a web app. Many things don't fit this format, e.g. command line tools. A Win32 program will not run out of the box on either Linux or macOS. Neither will a Java app. The nice thing about Cosmopolitan is that it "just works" as far as end user is concerned. But without firm support from the OSes involved, it is inevitably a hack with questionable long-term stability prospects. What we really need i…

> But without firm support from the OSes involved, it is inevitably a hack with questionable long-term stability prospects.

Case in point:

https://github.com/jart/cosmopolitan/blob/master/libc/sysv/s...

The system call numbers of all the unixlikes are bitwise packed into a single number. There is exactly one of those columns which is stable: the Linux one. Everything else is not part of the binary interface of their respective operating systems.

I've written about how Linux is special in this regard:

https://www.matheusmoreira.com/articles/linux-system-calls

It's a neat hack but I'm afraid it's in grave danger of falling victim to the Darth Vader of OS ABI stability.

https://lwn.net/Articles/806870/

  Program to the API rather than the ABI.
  When we see benefits, we change the ABI
  more often than the API.

  I have altered the ABI.
  Pray I do not alter it further.
  
  -- Theo de Raadt

Re: The Fastest Mutexes

#295

Post by bluGill »

0cf8612b2e1e wrote: post #170
bluGill wrote: post #129

Earlier quoted context omitted.

Unless the customer is one who has issues with large downloads. Not everyone has fiber to the home with massive storage on modern computers. Some people have the entry level systems, settle for slow internet. Often they are in poor or "third world" places which means maybe you don't care about them, but they exist.

Given how fat modern websites are, compassion for the bandwidth deprived seems rare.

Very much. Which is really a problem for those who do have bandwidth limitations. Or even low end phones / old computers. Or even new computers that are not very powerful.

Re: The Fastest Mutexes

#296

Post by pizlonator »

epcoa wrote: post #267
secondcoming wrote: post #187

Earlier quoted context omitted.

`rep; nop;` is actually the `pause` instruction. On older CPUs it’s a standard nop, but on newer CPUs it’s a more efficient nop. Spinning on the CMPXCHG is also a bad idea. You should spin on the read and only then attempt the CMPXCHG.

Just to clarify: the spinning on CMPXCHG is not also a bad idea, the YieldProcessor is correct (a pause), but inside the CMPXCHG loop it should be spinning on a pure unlocked load. Is that correct?

Spinning with pause is slower than spinning with sched_yield according to every test I’ve ever done

Re: The Fastest Mutexes

#297

Post by xmodem »

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…

What type of scenarios come up in RT/audio code where an alternative path is available if you can't get a lock? In most of the concurrent code I've written the options available if I can't get a lock is some subset of try again, try again with backoff, or fail.

Re: The Fastest Mutexes

#298

Post by TinkersW »

yshui wrote: post #78

I had the pleasure of reverse-engineering win32 SRWLOCKs, and based on the author description of nsync it is very close to how SRWLOCK works internally. Kind of surprised how much faster nsync is compared to SRWLOCK.

The post doesn't include any benchmarks for the uncontended case, where I've found SRWLock is also very fast, I'm curious why this wasn't included.

At least for what I use locks for, the uncontended case is like 10000x more common, I actually don't think I have any super heavy contention such as the case shown in the post, as this is simply something to be avoided--as no no matter how good the mutex this won't play well with the memory system.

Re: The Fastest Mutexes

#299

Post by Archit3ch »

xmodem wrote: post #297
PaulDavisThe1st wrote: post #114

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…

What type of scenarios come up in RT/audio code where an alternative path is available if you can't get a lock? In most of the concurrent code I've written the options available if I can't get a lock is some subset of try again, try again with backoff, or fail.

Let's say you are doing audio processing in the real-time thread. You try to lock to read new parameters, and if you fail to get the lock you do the processing with the old parameters.

Re: The Fastest Mutexes

#300

Post by davidtgoldblatt »

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…

There's two I've tried to do this:

- On the wait side, do the CAS to set the "waiter present" bit. Down unlock, do a (relaxed) read of the lock word, and if "waiter present" isn't set, just do a release store to unlock (and go down some slow CAS-y wake path if a waiter is present). On the wait side, never do an un-timed futex wait; just do a series of timed waits, with increasing wait times (so that you still eventually fix things if you hit the unlucky race between the previous holder's check+store sequence). (You can also do some tricks with counters to let waiters do an unconditional sleep once they get their wait acknowledged).

- Split out the "waiter present" bit into its own byte, do a store-load sequence (with just a compiler reordering fence) to check for waiters, and have waiters either do a membarrier() syscall or wait "long enough" that they're sure they've gotten the same effect. (This gets tricky w.r.t. mutex lifetime though; you either need out of band lifetime knowledge or to use RCU or whatever and indirect through pointers).

Practically, neither was ever "better enough" for anything but microbenchmarks to be worth the complexity.

Post reply on HN