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

141–150 of 150 posts

Re: Mutexes are faster than Spinlocks

#141

Post by Ericson2314 »

As the person that added a bunch of functionality to spin-rs making it roughly match the std API, yes you should not use spinlocks in scheduled code.

That said, I see why Rust makes things so annoying. I want lots of code to work in no-std so have a robust embedded and kernel ecosystem. It would be really nice to abstract over the locking implementation with type parameters, but that required "higher kinded types" which Rust doesn't have. The alternative is relying on carefully coordinated Cargo features, which is much more flaky and hard to audit (e.g. with the type system). Given that, I am not sure people over-use spin locks.

Re: Mutexes are faster than Spinlocks

#142

Post by legulere »

asveikau wrote: post #129
ncmncm wrote: post #125

Earlier quoted context omitted.

Back around 2012 I worked with a guy, a FreeBSD kernel committer, who insisted volatile was sufficient as a thread synchronization primitive. He convinced our boss.

Wouldn't that depend on the case? There is a nonzero amount of things in the universe for which volatile with no locking will do. Although, any particular thing happening to be one of those is a pretty rare event, so odds are good that this wasn't one.

Volatile doesn’t even guarantee that data is written atomically in one step and not e.g. byte-wise. Also it allows both the compiler as well as the CPU to reorder it with any read or write. I can’t think of anything that would it could be used for in a multithreaded environment.

Re: Mutexes are faster than Spinlocks

#143

Post by ncmncm »

legulere wrote: post #142
asveikau wrote: post #129

Earlier quoted context omitted.

Wouldn't that depend on the case? There is a nonzero amount of things in the universe for which volatile with no locking will do. Although, any particular thing happening to be one of those is a pretty rare event, so odds are good that this wasn't one.

Volatile doesn’t even guarantee that data is written atomically in one step and not e.g. byte-wise. Also it allows both the compiler as well as the CPU to reorder it with any read or write. I can’t think of anything that would it could be used for in a multithreaded environment.

Right.

There is really only a single place volatile actually works, and that is for memory-mapped hardware registers. Anybody who says it is useful for anything else is badly mistaken.

Except in MSVC, where it kinda/sorta means atomic.

Re: Mutexes are faster than Spinlocks

#144

Post by rcxdude »

simias wrote: post #56
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…

>The main use of spinlocks that i'm aware of is minimising latency in inter-processor communication. The main use of spinlocks that I'm aware of is dealing with interrupt handlers in driver code. In this situation you generally can't go to sleep (sleeping with interrupts disabled is generally a good way of never waking up) so calling "mutex_lock" is simply out of the question. That's probably a niche use but that's l…

And this only makes sense in a multi-core system (where the spinlock is held on another core). In a single core system if you are trying to take a contended lock in an interrupt you are stuck and can only fail to take it and hope to handle that gracefully.

Re: Mutexes are faster than Spinlocks

#145

Post by rcxdude »

sillysaurusx wrote: post #70
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…

Ya’ll should consider using atomic increment on separate cache lines instead of spinlocks. If you want to minimize latency to the bare minimum, atomic increment gives you two orders of magnitude measurable improvements over locks. https://lmax-exchange.github.io/disruptor/files/Disruptor-1....

They solve different problems. A lock-free datastructure can be much fast than one with locks, but they depend on exactly what operations you can do fast and atomically (for example, the LMAX queue length is limited to a power of 2 because there's no way to atomically increment an integer which will wrap at arbitrary values, and the modulo operator is too expensive for non-power of two values). A lock is a primitive which allows you to make arbitrary operations 'atomic' (though in these benchmarks generally a simple increment is used). A lock-free queue may be a good replacement for a queue using locks, but this is only in one application of locks.

Also, the disruptor design is based on a system where there is a 1:1 correspondance between threads and cores. If this is not the case it will likely still interact somewhat poorly with the OS's scheduler without any blocking at all, for the same reason as spinlocks (in fact, if you use the library you can customize this behaviour).

Re: Mutexes are faster than Spinlocks

#146

Post by rcxdude »

legulere wrote: post #142
asveikau wrote: post #129

Earlier quoted context omitted.

Wouldn't that depend on the case? There is a nonzero amount of things in the universe for which volatile with no locking will do. Although, any particular thing happening to be one of those is a pretty rare event, so odds are good that this wasn't one.

Volatile doesn’t even guarantee that data is written atomically in one step and not e.g. byte-wise. Also it allows both the compiler as well as the CPU to reorder it with any read or write. I can’t think of anything that would it could be used for in a multithreaded environment.

It allows the compiler to reorder it with any non-volatile read or write. Of course it still doesn't indicate anything to the CPU. In single-core embedded systems where the CPU doesn't reorder anything and you know the compiler is going to emit a single instruction for a read or write it can be sufficient (for example, this is how FreeRTOS implements all of its threading primitives)

Re: Mutexes are faster than Spinlocks

#147

Post by bluejekyll »

asveikau wrote: post #130
bluejekyll wrote: post #43

Earlier quoted context omitted.

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

The P in pthread is the P from Posix which stands for portable . Now, the "zero syscalls for uncontended pthread mutices via futex" optimization is Linux specific and may not be replicated elsewhere. Or it may. It's not Posix, but I know for instance win32 critical sections look a lot like spinlocks when not contended but do syscalls to block, which sounds a lot like a futex. So that would put that technique as datin…

> The P in pthread is the P from Posix which stands for portable.

What’s your point here? Posix is portable across posix compliant systems, it is not portable beyond that.

There are many systems that are posix, but Rust targets more than that.

Re: Mutexes are faster than Spinlocks

#148

Post by asveikau »

bluejekyll wrote: post #147
asveikau wrote: post #130

Earlier quoted context omitted.

The P in pthread is the P from Posix which stands for portable . Now, the "zero syscalls for uncontended pthread mutices via futex" optimization is Linux specific and may not be replicated elsewhere. Or it may. It's not Posix, but I know for instance win32 critical sections look a lot like spinlocks when not contended but do syscalls to block, which sounds a lot like a futex. So that would put that technique as datin…

> The P in pthread is the P from Posix which stands for portable. What’s your point here? Posix is portable across posix compliant systems, it is not portable beyond that. There are many systems that are posix, but Rust targets more than that.

Avoiding pthreads because they aren't portable and replacing them with a spinlock sounds a little bit like madness, that was my point.

What is the non-posix target you have in mind? Windows? Seems like conditionally compiling against either pthreads or win32 critical section [or anything else] is a feasible thing and reasonable action. Maybe even the spinlock as a last resort.

Re: Mutexes are faster than Spinlocks

#149

Post by gpderetta »

chrismonsanto wrote: post #135
gpderetta wrote: post #119

Earlier quoted context omitted.

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

> in practice FWIW RISC-V guarantees forward progress for reasonable uses: > We mandate that LR/SC sequences of bounded length (16 consecutive static instructions) will eventually succeed, provided they contain only base ISA instructions other than loads, stores, and taken branches.

[sorry for the late reply]

what happens if those 16 instructions touch 16 different cache lines? I'm not an hardware expert (and even less on coherency protocols), but I think it would be extremely hard to make sure livelocking is avoided in all cases, short of having some extremely expensive and heavy handed global 'bus' lock fallback.

Re: Mutexes are faster than Spinlocks

#150

Post by chrismonsanto »

gpderetta wrote: post #149
chrismonsanto wrote: post #135

Earlier quoted context omitted.

> in practice FWIW RISC-V guarantees forward progress for reasonable uses: > We mandate that LR/SC sequences of bounded length (16 consecutive static instructions) will eventually succeed, provided they contain only base ISA instructions other than loads, stores, and taken branches.

[sorry for the late reply] what happens if those 16 instructions touch 16 different cache lines? I'm not an hardware expert (and even less on coherency protocols), but I think it would be extremely hard to make sure livelocking is avoided in all cases, short of having some extremely expensive and heavy handed global 'bus' lock fallback.

Reading and writing memory are excluded from the guarantee, aside from the LR/SC instructions that bookend a transaction. Inside the transaction you're basically limited to register-register ALU and aborting branches.
Post reply on HN