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

11–20 of 150 posts

Re: Mutexes are faster than Spinlocks

#11

Post by xtacy »

elteto wrote: post #9
hackworks wrote: post #2

Not an expert here. In a spin lock, the lock state is checked in a tight loop by all waiters. This will be using some sort of memory fence. FWIK, memory fence or barriers flush the CPU cache and would initiate reading the variable (spin lock state) for evaluation. I would expect spin locking overheads to increase with number of cores. On NUMA, I think flushing is more expensive. Hence, spin locks have an additional o…

> checked in a tight loop by all waiters This actually does not have to be this way. You could have a linked list of spinlocks, one for each waiter. Each waiter spins on its own, unique spinlock. When the previous waiter is done it unlocks the next spinlock, and so on. The implementation gets a bit complicated on non-GC languages, since there are races between insertion/removal on the linked list. If the number of th…

Yep, that's the underlying principle behind Mellor-Crummey Spinlock: https://lwn.net/Articles/590243/.

Re: Mutexes are faster than Spinlocks

#12

Post by hackworks »

elteto wrote: post #9
hackworks wrote: post #2

Not an expert here. In a spin lock, the lock state is checked in a tight loop by all waiters. This will be using some sort of memory fence. FWIK, memory fence or barriers flush the CPU cache and would initiate reading the variable (spin lock state) for evaluation. I would expect spin locking overheads to increase with number of cores. On NUMA, I think flushing is more expensive. Hence, spin locks have an additional o…

> checked in a tight loop by all waiters This actually does not have to be this way. You could have a linked list of spinlocks, one for each waiter. Each waiter spins on its own, unique spinlock. When the previous waiter is done it unlocks the next spinlock, and so on. The implementation gets a bit complicated on non-GC languages, since there are races between insertion/removal on the linked list. If the number of th…

NetApp has a very interesting implementation RW spin lock inside the kernel. I tried optimizing to make it more fair for writers by introducing a single variable that would be check in each iteration.

The additional delay it added for checking the state resulted in deadlock timer triggering a dump! Hence, checking a variable is very expensive.

Re: Mutexes are faster than Spinlocks

#14

Post by kcolford »

This absolutely makes sense in userspace. The most important part of a spinlock in an OS is that you can yield to the scheduler instead of taking up CPU time on the core. But that defeats the purpose of using a spinlock when in userspace because you still have to syscall

Re: Mutexes are faster than Spinlocks

#15

Post by gok »

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.

Re: Mutexes are faster than Spinlocks

#16

Post by elteto »

xtacy wrote: post #11
elteto wrote: post #9

Earlier quoted context omitted.

> checked in a tight loop by all waiters This actually does not have to be this way. You could have a linked list of spinlocks, one for each waiter. Each waiter spins on its own, unique spinlock. When the previous waiter is done it unlocks the next spinlock, and so on. The implementation gets a bit complicated on non-GC languages, since there are races between insertion/removal on the linked list. If the number of th…

Yep, that's the underlying principle behind Mellor-Crummey Spinlock: https://lwn.net/Articles/590243/ .

Yes! The MCS spinlock, the name eluded me. The paper is actually a pretty good read (it is linked in the lwn article).

Re: Mutexes are faster than Spinlocks

#18

Post by the8472 »

rwem wrote: post #4
hackworks wrote: post #2

Not an expert here. In a spin lock, the lock state is checked in a tight loop by all waiters. This will be using some sort of memory fence. FWIK, memory fence or barriers flush the CPU cache and would initiate reading the variable (spin lock state) for evaluation. I would expect spin locking overheads to increase with number of cores. On NUMA, I think flushing is more expensive. Hence, spin locks have an additional o…

It doesn’t flush the entire cache (that would be a disaster) but it does shoot down the cache line containing the lock in all cores other than the one that acquired the lock. The real issue with spin locks is fairness. There’s no assurance that any given thread will ever make progress. A thread could starve forever. Production-ready mutexes like absl::Mutex make efforts toward fairness, even if they don’t have hard g…

> but it does shoot down the cache line containing the lock in all cores other than the one that acquired the lock.

Well, as long as you do the test-CAS instead of the pure-CAS approach not every loop iteration results in cache line bouncing.

Plus intel has introduced the MWAIT[0] instruction to implement something similar to futex in hardware, i.e. the hyperthread can sleep until another core updates the cacheline in question.

[0] https://www.felixcloutier.com/x86/mwait

Re: Mutexes are faster than Spinlocks

#19

Post by mareko »

hackworks wrote: post #12
elteto wrote: post #9

Earlier quoted context omitted.

> checked in a tight loop by all waiters This actually does not have to be this way. You could have a linked list of spinlocks, one for each waiter. Each waiter spins on its own, unique spinlock. When the previous waiter is done it unlocks the next spinlock, and so on. The implementation gets a bit complicated on non-GC languages, since there are races between insertion/removal on the linked list. If the number of th…

NetApp has a very interesting implementation RW spin lock inside the kernel. I tried optimizing to make it more fair for writers by introducing a single variable that would be check in each iteration. The additional delay it added for checking the state resulted in deadlock timer triggering a dump! Hence, checking a variable is very expensive.

If you're interested in very efficient MCS style reader writer locks, check out this paper:

https://people.csail.mit.edu/mareko/spaa09-scalablerwlocks.p...

Re: Mutexes are faster than Spinlocks

#20

Post by jnordwick »

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:

* Instead of reducing thread count to reduce contention he appears to increase the number of locks available. This is still a bad scenario for spinlocks since they will still have bad interactions with scheduler (they will use a large amount of cpu time when and get evicted from the run queue and need to be rescheduled).

* Also, I didn't see him pin any of the threads, so all those threads will start sharing some cpus since the OS does need to be doing some work on a them too.

* And Rust can be a little hard to read, but it seem he packed his locks on the same cache line? I don't see any padding in his AmdSpinlock struct. That would be a huge blow for the spinlock because of the false sharing issues. He's getting all the cache coherence traffic still because of it.

The worst cases for the spinlock are not understanding scheduling costs and the cache thrashing that can occur.

What they call the AMD spinlock (basically just a regular sane spinlock that tries to prevent cache thrashing) has its best performace with a low number of threads, assigned to different cores under the same L3 segment.

(Does anybody know if AMD's new microarchitecture went away from the MOESI/directory based cache towards Intel's MESIF/snoop model?)

The MOESI model might have performed better in this regard under worse case scenario since it doesn't need to write the cache line back and can just forward around the dirty line as it keeps track of who owns it.

And if you run under an MESIF-based cache and you can keep your traffic local to your L3 segment, you are backstopped there and never need to go anywhere else.

A spinlock is a performance optimization and should be treated as one. You need to have intimate knowledge of the architecture you are running under and the resources being used.

(edit: answered my own question, apparently the vdso is still pretty limited in what it exports, so no. it isn't happening at this time from what i can tell.)

Post reply on HN