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

41–50 of 150 posts

Re: Mutexes are faster than Spinlocks

#41

Post by rwem »

gpm wrote: post #33
dcolkitt wrote: post #28

> Second, the uncontended case looks like > Parking_lot::Mutex avg 6ms min 4ms max 9ms This estimate is way too high for the uncontested mutex case. On a modern Linux/Xeon system using GCC, an uncontested mutex lock/unlock is well under 1 microsecond . I have a lot of experience here from writing low-latency financial systems. The hot path we use is littered with uncontested mutex lock/unlock, and the whole path stil…

You're misreading the benchmark, that's 6ms for 10,000 lock/unlocks per thread, 320,000 lock/unlocks total. In other words 0.6 microseconds per thread per lock.

That's still unreasonably high, isn't it? Even a Go sync.Mutex, not exactly a hot-rod implementation, can be acquired and released in < 50ns on the garbage hardware I have before me.

Re: Mutexes are faster than Spinlocks

#42

Post by jakswa »

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

Because you should never ever think that you're clever enough to write your own locking routines.. Because the likelihood is that you aren't (and by that "you" I very much include myself - we've tweaked all the in-kernel locking over decades, and gone through the simple test-and-set to ticket locks to cacheline-efficient queuing locks, and even people who know what they are doing tend to get it wrong several times).

There's a reason why you can find decades of academic papers on locking. Really. It's hard."

Re: Mutexes are faster than Spinlocks

#43

Post by bluejekyll »

ww520 wrote: post #37
bluejekyll wrote: post #30

Earlier quoted context omitted.

I updated my comment. The fastest impl, parking_lot, appears to be a ground up atomic based mutex that doesn’t rely on pthread at all.

It seems to be doing similar logic. 1. Does a CAS with compare_exchange_weak() at line 69. 2. Then call lock_slow() at line 72 to do spinlocking (Guh!). 3. The call to parking_lot_core::park() at line 256 seems to sleep wait.

Yes. I just meant to say that it’s not a pthread based implementation, potentially making it more portable.

Re: Mutexes are faster than Spinlocks

#44

Post by jnordwick »

atq2119 wrote: post #25
jnordwick wrote: post #20

This comes around every so often, and it isn't very interesting in that the best mutexes basically spins 1 or a couple times then falls back to a lock. It isn't a true pure spinlock vs pure lock (mutex/futex) fight. I think the linux futex can be implemented through the VDSO (can somebody correct me on this), so that eliminates the worse of the sycall costs. His benchmark is weird, but maybe I'm reading it wrong: * I…

The locks should be on separate cachelines, that's what the CachePadded::new is for. futex cannot be implemented in the VDSO since it needs to call into the scheduler. Another way to think about this: VDSO is used for syscalls that are (mostly) read-only and can avoid the kernel mode switch on a common fast path. The futex syscall is already the raw interface that is designed on the assumption that the caller only us…

> The locks should be on separate cachelines, that's what the CachePadded::new is for

I see that now. I looking for it in the AmdSpinlock struct, but that kind of makes sense.

> The futex syscall is already the raw interface that is designed on the assumption that the caller only uses it in the slow path of whatever higher-level synchronization primitive they're implementing, so trying to use VDSO tricks to implement futex would be redundant.

Ah. Thanks. I didn't know how far you could get with MWAIT, but I guess you still need to deschedule. I also didn't realize futex was a direct syscall and there was no user level api going on around it.

Is he running 32 threads even in the low contention case? And not pinning? There's something about his numbers that just seem a little too high for what I would expect. I've seen this around a lot, and the reason the mutex usually wins is that is basically does a spin of 1 or more then goes into a mutex (the pthread code appers to spin 100 times before falling back to a futex).

At work I use a spin lock on a shared memory region because it does test out to be lower latency than std::mutex and we're not under much contention. I've though about replacing it with a light futex-based library, but doesn't seem to be quicker.

He still seems to be getting some contention, and I'm trying figure out how.

Re: Mutexes are faster than Spinlocks

#46

Post by 0x0aff374668 »

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…

This is a great example of how so many programmers think they are the first to discover something that is "ancient". In reality this is a problem older than Linux (linux just had the advantage of a huge and diverse open-source userbase from which to draw data). On the flipside, lots of good information takes years to go from discussion groups to books, so it can be hard to find relevant research. Applied compsci is literally the cutting edge of reality.

Re: Mutexes are faster than Spinlocks

#47

Post by sanxiyn »

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.

Note that fair locking is still expensive. parking_lot achieves both speed and fairness by starting with unfair locking and falling back to fair locking.

Re: Mutexes are faster than Spinlocks

#48

Post by jakemal »

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?

Re: Mutexes are faster than Spinlocks

#49

Post by rrss »

any1 wrote: post #35
jnordwick wrote: post #20

This comes around every so often, and it isn't very interesting in that the best mutexes basically spins 1 or a couple times then falls back to a lock. It isn't a true pure spinlock vs pure lock (mutex/futex) fight. I think the linux futex can be implemented through the VDSO (can somebody correct me on this), so that eliminates the worse of the sycall costs. His benchmark is weird, but maybe I'm reading it wrong: * I…

According to "man vdso", futex is not in vDSO on any architecture. What eliminates the syscall cost is that it's rarely called due to elision. A mutex may try to spin more than a "couple of times" before it calls futex. Example: https://git.musl-libc.org/cgit/musl/tree/src/thread/pthread_...

> is that it's rarely called due to elision.

Calling this 'elision' is a bit confusing, since the glibc developers use the term 'lock elision' to refer to hardware lock elision via Intel TSX extensions.

What eliminates the syscall cost is optimistic spinning in userspace, so that locking only does futex_wait in cases of contention when the lock isn't released 'soon' after the thread starts trying to acquire it.

Re: Mutexes are faster than Spinlocks

#50

Post by lonelappde »

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?

Finishing a high priority job sooner.
Post reply on HN