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

101–110 of 150 posts

Re: Mutexes are faster than Spinlocks

#101

Post by gpderetta »

temac wrote: post #95
gpderetta wrote: post #90

Earlier quoted context omitted.

> you could possibly do away atomics, since (I believe) int updates are atomic by default. The release can be a compiler only barrier followed by a simple store, but you do need an atomic RMW in the acquire path. It is technically possible to implement a lock with just loads and stores (see Peterson lock[1]) even in the acquire path but it does require a #StoreLoad memory barrier even on Intel, which is as expensive…

> #StoreRelease memory barrier even on Intel What is that? x86 is TSO... Do you have an example of the full acquire and release sections in x86 assembly?

I'm sorry, I meant #StoreLoad.

Edit: here is a good (but long) article with a x86 Peterson Lock example (with an analysis of the critical race without the barrier):

https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fe...

Re: Mutexes are faster than Spinlocks

#102

Post by hinkley »

nathanielherman wrote: post #40

This experiment is a bit weird. If you look at https://github.com/matklad/lock-bench , this was run on a machine with 8 logical CPUs, but the test is using 32 threads. It's not that surprising that running 4x as many threads as there are CPUs doesn't make sense for spin locks. I did a quick test on my Mac using 4 threads instead. At "heavy contention" the spin lock is actually 22% faster than parking_lot::Mutex. At "…

The top comment opens up the concept of latency versus throughput. My interpretation is that this experiment is demonstrating that optimizing only for latency has consequences elsewhere in the system. Which is not surprising at all, but then again I spend a lot of time explaining unsurprising things.

I remember a sort of sea change in my thinking on technical books during a period where I tended to keep them at work instead of at home. I noticed a curious pattern in which ones were getting borrowed and by whom. Reading material isn't only useful if it has something new to me in it. It's also useful if it presents information I already know and agree with, in a convenient format. Possibly more useful, in fact.

Re: Mutexes are faster than Spinlocks

#103

Post by dfox »

sillysaurusx wrote: post #98
extropy wrote: post #94

Earlier quoted context omitted.

As far as I'm aware that's exactly how you would implement a spinlock. Random Google search seems to validate that. https://stackoverflow.com/questions/1383363/is-my-spin-lock-...

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.

Re: Mutexes are faster than Spinlocks

#104

Post by kortilla »

twic wrote: post #54
anonymoushn wrote: post #53

Earlier quoted context omitted.

Hello, I wrote some software at an automated trading firm that would do the subset of "parsing ticks and maintaining order books" sufficient to map ticks to symbols, and no more work than that. My code was pinned to one core and spun waiting for an expensive network card to DMA some ticks into memory, then when ticks we cared about were found it would load them onto one or more queues. Each queue corresponded to a di…

Comment-OP here - this is also more or less my use case. Whether there is a use case for spinlocks outside low-latency trading, i have no idea!

High performance networking in general (NFV) frequently relies on cores dedicated to dpdk for the this.

Re: Mutexes are faster than Spinlocks

#105

Post by johncolanduoni »

rumanator wrote: post #93
titzer wrote: post #91

Earlier quoted context omitted.

This is exactly the situation for a well-balanced parallel work queue. You want to start as many threads as there are cores and run them full tilt pulling work off the queue until it is empty. If you're running a large scale cluster that is dedicated to a particular task (e.g. like servicing a special kind of query, or encoding videos, rendering, etc), this is very common, or even a parallel Photoshop filter.

> This is exactly the situation for a well-balanced parallel work queue. What if your work queues are running on a multitasking operating system that runs services? And what about a hypervisor?

For this technique you generally dedicate some core(s) to those miscellaneous threads and flag the rest as unscheduable unless a thread is specifically assigned to them.

If you’re not sharing cores between VMs it’s typical to do the same at the hypervisor layer.

Re: Mutexes are faster than Spinlocks

#106

Post by dfox »

temac wrote: post #78
corysama wrote: post #74

Earlier quoted context omitted.

Intel has a low-power PAUSE instruction that is literally a ‘rep nop’. I assume Arm has one too.

That's not extremely low power compared to real low power states. The main advantage of PAUSE is the scheduling of the other hyperthread (if it exists) and maybe not generating a gratuitous L1 / MESI workload at a crazy rate (well if programmed correctly that should be quite cheap in lots of cases, but still...). To my knowledge this does not cut any clock, so the power economy is going to be minimal.

IIRC the mov imm, %ecx; rep nop sequences are somewhat special cased by modern architectures (and this fact is the only reason why you even would want to execute such code). On the other hand the energy savings are mostly negligible and it is simply an SMT-level equivalent of sched_yield()

Re: Mutexes are faster than Spinlocks

#107

Post by sillysaurusx »

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.

Is it?

I'd be interested to see benchmarks showing that spinlocks with CAS have similar throughput to a ringbuffer with atomic increment.

Note that with the ringbuffer approach, each reader can process many slots at once, since you're taking the minimum of all published slot numbers. If you last processed slot 3, and the minimum publish count is 9, you can process slot 4 through 9 without doing any atomic operations at all. The design guarantees safety with no extra work.

It's not a minor trick; it's one of the main reasons throughput is orders of magnitude higher.

Benchmarks: https://github.com/LMAX-Exchange/disruptor/wiki/Performance-...

Beyond that, the ringbuffer approach also solves the problem you'll always run into: if you use a queue, you have to decide the max size of the queue. It's very hard to use all available resources without allocating too much and swapping to disk, which murders performance. Real systems with queues have memory usage patterns that tend to fluctuate by tens of GB, whereas a fixed-size ringbuffer avoids the problem.

Re: Mutexes are faster than Spinlocks

#108

Post by gpderetta »

temac wrote: post #78
corysama wrote: post #74

Earlier quoted context omitted.

Intel has a low-power PAUSE instruction that is literally a ‘rep nop’. I assume Arm has one too.

That's not extremely low power compared to real low power states. The main advantage of PAUSE is the scheduling of the other hyperthread (if it exists) and maybe not generating a gratuitous L1 / MESI workload at a crazy rate (well if programmed correctly that should be quite cheap in lots of cases, but still...). To my knowledge this does not cut any clock, so the power economy is going to be minimal.

Actually I heard that the last few generations of intel (from skylake) enter power state mode more aggressively with pause and the latency of getting out of a pause went up from tens of cycles to hundreds. No first hand testing though.

Re: Mutexes are faster than Spinlocks

#109

Post by dfox »

jakemal wrote: post #48
twic wrote: post #27

The author has an implicit definition of "faster" which it is important to be aware of. The main use of spinlocks that i'm aware of is minimising latency in inter-processor communication. That is, if you have a worker task which is waiting for a supervisor task to tell it to do something, then to minimise the time between the supervisor giving the order and the worker getting to work, use a spinlock. For this to real…

What is a use case for optimizing interprocessor latency?

Essentialy any true HPC workload. You can go pretty far by ignoring latency and doing some series of map and reduce stages on top of giant conceptual file with large-ish records. There are workloads where data for these partial parallel jobs are on the order of machine word or two and then you really care about communication latency between cores.

Re: Mutexes are faster than Spinlocks

#110

Post by hinkley »

jakswa wrote: post #42
sharken wrote: post #13

This is pretty much the conclusion in this game related post on spinlocks: https://probablydance.com/2019/12/30/measuring-mutexes-spinl...

Oh wow/yikes, Linus Torvalds commented on that recently: https://www.realworldtech.com/forum/?threadid=189711&curpost... "So you might want to look into not the standard library implementation, but specific locking implentations for your particular needs. Which is admittedly very very annoying indeed. But don't write your own. Find somebody else that wrote one, and spent the decades actually tuning it and making it w…

We've been arguing about concurrency primitives literally for decades and the 'worst' part is that for most of that time, all of the competing solutions were documented by the same individual - Tony Hoare - within a narrow period in the early 1970's. Soon that will be 50 years ago. Watching people argue is like the People's Liberation Front of Judea scene in Life of Brian. As far as I know, borrow checking may be the first real change in that arena in decades, and I bet even that is older than most of us know.

I was getting heckled recently about my allergy to trying to negotiate interprocess consensus through the filesystem. I've seen similar conversations about how hard it is to 'know' the state of files, especially in a cross platform or cross filesystem way (see also the decade old fsync bug in PostgreSQL we were talking about early last year). In our case several dozen machines all have to come to the same decision at the same time (because round robin) and I was having none of it. I eventually had to tell him, in the nicest way possible, to fuck off, I'm doing this through Consul.

The thing is that people who generally don't learn from their mistakes absolutely do not learn from their old mistakes. So for any bug they introduce (like a locking problem) that takes months or quarters to materialize, they will not internalize any lessons from that experience. Not only wasn't I gonna solve the problem the way he wanted, but if he tried to take over it, we'd have broken code at some arbitrary future date and he'd learn nothing. He could not understand why I in particular and people in general were willing to die on such a hill.

Anger is not the best tool for communication, but as someone once put it, it's the last signal you have available that your boundaries are being violated and this needs to stop. Especially if you're the one who will have to maintain a bad decision. As often as I critique Linus for the way he handles sticky problems, on some level he is not wrong.

Post reply on HN