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

21–30 of 150 posts

Re: Mutexes are faster than Spinlocks

#21

Post by ww520 »

Modern day user-mode pthread mutex uses the futex kernel syscall [1] to implement the lock, which avoids the syscall in the non-contended case, so it can be very fast, acquiring the lock in the user-mode code entirely. I'm not sure whether the Rust's mutex API is a wrapper on the pthread mutex or calling the old kernel's mutex syscall directly.

Basically the user mode mutex lock is implemented as:

    // In user-mode, if the lock flag is free as 0, lock it to 1 and exit
    while !atomic_compare_and_swap(&lock, 0, 1)
        // Lock not free, sleeps until the flag is changed back to 0
        futex_wait(&lock, 0)  // syscall to kernel
When futex_wait() returns, it means the flag has been set back to 0 by the other thread's unlock, and the kernel wakes my thread up so I can check it again. However, another thread can come in and grab the lock in the meantime, so I need to loop back to check again. The atomic CAS operation is the one acquiring the lock.

[1] https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...

Edit: the atomic_compare_and_swap can be just a macro to the assembly CMPXCHG, so it's very fast to acquire a lock if no one else holding the lock.

Re: Mutexes are faster than Spinlocks

#22

Post by Diggsey »

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.

Re: Mutexes are faster than Spinlocks

#23

Post by bluejekyll »

ww520 wrote: post #21

Modern day user-mode pthread mutex uses the futex kernel syscall [1] to implement the lock, which avoids the syscall in the non-contended case, so it can be very fast, acquiring the lock in the user-mode code entirely. I'm not sure whether the Rust's mutex API is a wrapper on the pthread mutex or calling the old kernel's mutex syscall directly. Basically the user mode mutex lock is implemented as: // In user-mode, if…

https://github.com/rust-lang/rust/blob/master/src/libstd/sys...

Looks like it’s relying glibc for lock elision.

Mind you the parking_lot::Mutex in the article is not the stdlib implementation, documented here: https://docs.rs/parking_lot/0.10.0/parking_lot/type.Mutex.ht...

And that looks like it’s not using pthread, instead relying on primitives: https://github.com/Amanieu/parking_lot/blob/master/src/raw_m...

Re: Mutexes are faster than Spinlocks

#24

Post by ww520 »

bluejekyll wrote: post #23
ww520 wrote: post #21

Modern day user-mode pthread mutex uses the futex kernel syscall [1] to implement the lock, which avoids the syscall in the non-contended case, so it can be very fast, acquiring the lock in the user-mode code entirely. I'm not sure whether the Rust's mutex API is a wrapper on the pthread mutex or calling the old kernel's mutex syscall directly. Basically the user mode mutex lock is implemented as: // In user-mode, if…

https://github.com/rust-lang/rust/blob/master/src/libstd/sys... Looks like it’s relying glibc for lock elision. Mind you the parking_lot::Mutex in the article is not the stdlib implementation, documented here: https://docs.rs/parking_lot/0.10.0/parking_lot/type.Mutex.ht... And that looks like it’s not using pthread, instead relying on primitives: https://github.com/Amanieu/parking_lot/blob/master/src/raw_m...

Then it's using the futex implementation. It's very efficient.

Re: Mutexes are faster than Spinlocks

#25

Post by atq2119 »

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

Re: Mutexes are faster than Spinlocks

#27

Post by twic »

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 really work, you need to implement both tasks as threads pinned to dedicated cores, so they won't be preeempted. You will burn a huge amount of CPU doing this, and so it won't be "faster" from a throughput point of view. But the latency will be as low as it's possible to go.

Re: Mutexes are faster than Spinlocks

#28

Post by dcolkitt »

> 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 still runs under 20 microseconds. (With the vast majority of that time unrelated to mutex acquisition.)

The benchmark used in the blog post must be spending the vast majority of its time in some section of code that has nothing to do with lock/unlock.

Re: Mutexes are faster than Spinlocks

#29

Post by atq2119 »

the8472 wrote: post #18
rwem wrote: post #4

Earlier quoted context omitted.

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

That's true, though MWAIT can only be used from kernel mode. At least the docs say that you get a #UD exception if you attempt to use it from user mode.

Re: Mutexes are faster than Spinlocks

#30

Post by bluejekyll »

ww520 wrote: post #24
bluejekyll wrote: post #23

Earlier quoted context omitted.

https://github.com/rust-lang/rust/blob/master/src/libstd/sys... Looks like it’s relying glibc for lock elision. Mind you the parking_lot::Mutex in the article is not the stdlib implementation, documented here: https://docs.rs/parking_lot/0.10.0/parking_lot/type.Mutex.ht... And that looks like it’s not using pthread, instead relying on primitives: https://github.com/Amanieu/parking_lot/blob/master/src/raw_m...

Then it's using the futex implementation. It's very efficient.

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.
Post reply on HN