Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Mutexes are faster than Spinlocks

matklad.github.io

Post reply on HN
Print view View original

111–120 of 150 posts

Re: Mutexes are faster than Spinlocks

#111

Post by matklad »

Diggsey wrote: post #22
gok wrote: post #15

Note that all of the locks tested here are unfair, which is why they all show very high waiting variance. Until recently many mutex implementations aimed for fairness, which made them much slower than spinlocks in microbenchmarks like this.

Actually, the parking_lot mutex is fair: https://docs.rs/parking_lot/0.10.0/parking_lot/type.Mutex.ht... The high waiting variance is because the benchmark randomly decides which locks to take, meaning that the amount of contention is variable.

Benchmark uses fixed seeds, there’s no inherent randomness.

Re: Mutexes are faster than Spinlocks

#112

Post by gpderetta »

dfox wrote: post #103
sillysaurusx wrote: post #98

Earlier quoted context omitted.

Compare-and-swap isn't quite the same as atomic increment. An atomic increment can't fail; it always increments. Whereas CAS will fail if a different thread has modified the value. The highest performance design is to use a ringbuffer. To write to the ringbuffer, you atomic-increment the "claim" counter, giving you an index. Now take index modulo ringbuffer size. That's the slot to write to. After you're done writing…

From the architecture PoV it is exactly same thing if you think of it as implemented by LL/SC pair. This is how this is presented in most of literature and university courses. Then there is the purely practical issue of x86 not exposing LL/SC and instead having somewhat strict memory model and various lock-prefixed high-level instructions with wildly varying performance characteristics.

I do not think x86 atomics are implemented as LL/SC internally. As a minimum they always guarantee forward progress: as soon the cacheline is acquired in exclusive mode (and the coherency protocol gurantees it happens in finite time), the load-op-write always happens and cannot be interrupted.

Also as far as I'm aware, at least on intel all atomic operations take pretty much exactly the same number of clock cyles (except for CAS and DCAS which are ~10% and 50% more expensive, IIRC)

Re: Mutexes are faster than Spinlocks

#113

Post by tingletech »

codezero wrote: post #82
simias wrote: post #75

Earlier quoted context omitted.

I personally go with "The Fine Article" in my mind when I write it, although obviously all these alternatives are possible. I first encountered this initialism on slashdot back when it was still relevant, although I don't know if it was coined there. And yeah, I believe that it derives from "RTFA" (read the fucking article) which would be what you told people who obviously commented without reading the article.

Not sure it’s the origin, but it used to be RTFM (read the fucking manual).

Also read "read the fine manual"

Re: Mutexes are faster than Spinlocks

#114

Post by gpderetta »

rumanator wrote: post #51
gpderetta wrote: post #38

Earlier quoted context omitted.

Also if both threads are pinned to separate cores and nothing else is supposed to run on those cores, it is pointless to use anything but spinlocks as there is no other thread that could better use the core (and probably you do not want the core to go to a low power syate waiting for an interrupt).

> and nothing else is supposed to run on those cores That's quite the corner case.

Yes, in practice you have to dedicate the whole machine for a specific application, but the one thread per isolated core is a proven one for high performance/low latency applications.

Re: Mutexes are faster than Spinlocks

#115

Post by jnordwick »

extropy wrote: post #96

How about a new opcode wait till memory address read equals? That would allow implementing a power efficient spinlock. Oh there is one already. Meet PAUSE: https://www.felixcloutier.com/x86/pause Edit: related post from 2018 https://news.ycombinator.com/item?id=17336853

MONITOR/MWAIT will get you the part where a thread will pause and the cpu can rest until a write on a store on an address range, then the waiting thread is allowed to continue. You can't wait on a specific value though.

Re: Mutexes are faster than Spinlocks

#116

Post by dfox »

gpderetta wrote: post #112
dfox wrote: post #103

Earlier quoted context omitted.

From the architecture PoV it is exactly same thing if you think of it as implemented by LL/SC pair. This is how this is presented in most of literature and university courses. Then there is the purely practical issue of x86 not exposing LL/SC and instead having somewhat strict memory model and various lock-prefixed high-level instructions with wildly varying performance characteristics.

I do not think x86 atomics are implemented as LL/SC internally. As a minimum they always guarantee forward progress: as soon the cacheline is acquired in exclusive mode (and the coherency protocol gurantees it happens in finite time), the load-op-write always happens and cannot be interrupted. Also as far as I'm aware, at least on intel all atomic operations take pretty much exactly the same number of clock cyles (ex…

That is exactly my point. Any x86 SMP platform since Pentium is built on the assumption that truly exclusive access is possible. For the shared FSB platforms that is trivially implemented by global LOCK# and K8/QPI simply has to somehow simulate same behavior on top of some switched NUMA fabric (and this is one of the reasons why x86 NUMA coherency protocols are somewhat wasteful, think global broadcasts, and incredibly complex).

For context: before Pentium with its glueless 2x2 SMP/redundancy support there were various approaches to shared memory x86 multiprocessors with wildly different memory coherence models. (And some of the “lets design a board with eight 80386” are the reason why Intel had designed i586 to be glueless and such systems are probably still used to this day, althought unsupported)

Re: Mutexes are faster than Spinlocks

#117

Post by boltzmann_brain »

I don't understand, I thought spinlock is just a busy spin on a CAS (hence the name?). Why would it ever be slower than mutex.

EDIT: ah, I read his previous post, it's all about priority inversion. However, in a typical scenarios most threads are the same priority, aren't they?

Re: Mutexes are faster than Spinlocks

#119

Post by gpderetta »

dfox wrote: post #116
gpderetta wrote: post #112

Earlier quoted context omitted.

I do not think x86 atomics are implemented as LL/SC internally. As a minimum they always guarantee forward progress: as soon the cacheline is acquired in exclusive mode (and the coherency protocol gurantees it happens in finite time), the load-op-write always happens and cannot be interrupted. Also as far as I'm aware, at least on intel all atomic operations take pretty much exactly the same number of clock cyles (ex…

That is exactly my point. Any x86 SMP platform since Pentium is built on the assumption that truly exclusive access is possible. For the shared FSB platforms that is trivially implemented by global LOCK# and K8/QPI simply has to somehow simulate same behavior on top of some switched NUMA fabric (and this is one of the reasons why x86 NUMA coherency protocols are somewhat wasteful, think global broadcasts, and incredi…

No, to implement x86 atomic semantics is the guarantee that a single cache line can be held in exlusive mode for a minimum lenght of time.

As forward progress is a pretty basic requirements, in practice even LL/SC platforms in practice do that, but is instead of having a single instruction with guaranteed forward progress you have to use a few special (but sometimes underspecified) sequences of instructions between the ll/sc pairs.

Post reply on HN