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

131–140 of 150 posts

Re: Mutexes are faster than Spinlocks

#131

Post by ncmncm »

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.

This definitely wasn't one. It didn't bite in any obvious way because Intel, and because the system already had so many other bugs. (Free advice: don't take on a C++ program written by a Java coder.)

Re: Mutexes are faster than Spinlocks

#132

Post by AstralStorm »

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!

Software industrial process control, such as motors and let robotics. The longer latencies make the control loop less responsive or unstable. Microseconds granularity is very useful there.

Re: Mutexes are faster than Spinlocks

#133

Post by AstralStorm »

acqq wrote: post #58
ww520 wrote: post #37

Earlier quoted context omitted.

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.

So this it acquires fully in userspace if there's no contention, it even spins if there is contention, and then if that wasn't enough it lets the thread sleep with the timeout. Which matches the description of that library: https://github.com/Amanieu/parking_lot "This library provides implementations of Mutex, RwLock, Condvar and Once that are smaller, faster and more flexible than those in the Rust standard library"…

How does it know that said critical section is short? Guessing?

Likely a hard linear-quadratic expanding threshold. They tend to waste a lot of CPU power in specific algorithms.

There are better, more intrusive ways of solving this problem on language level.

Re: Mutexes are faster than Spinlocks

#134

Post by AstralStorm »

AnanasAttack wrote: post #122

Thread scheduling (or waking up cores) is slow. Because of this, mutexes will look better on dumb benchmarks, as the contending threads keep going to sleep, while the single succesful owner has practically uncontended access

There are various degrees of slow, in addition to kernel being smarter about multiple cores and SMT siblings than your application.

Kernel can run your code on a cooled core, giving it higher clock, for example. Ultimately making it run faster.

Of course this won't show in a benchmark where all the threads do mostly calculation rather than contention, but that's not the typical case. That mostly shows up in compute such as multithreaded video where latency does not matter one bit.

Typically you have more of a producer/consumer pattern where consumer sleeps, and it's beneficial to run it on a cold CPU, assuming the kernel woke it up beforehand.

Source: hit some latency issues with an ancient kernel on a nastily hacked big little architecture ARM machine. It liked to overheat cores and put heavy tasks on the overheated ones for alleged power saving. (Whereas running a task quicker saves power.)

Re: Mutexes are faster than Spinlocks

#135

Post by chrismonsanto »

gpderetta wrote: post #119
dfox wrote: post #116

Earlier quoted context omitted.

That is exactly my point. Any x86 SMP platform since Pentium is built on the assumption that truly exclusive access is possible. For the shared FSB platforms that is trivially implemented by global LOCK# and K8/QPI simply has to somehow simulate same behavior on top of some switched NUMA fabric (and this is one of the reasons why x86 NUMA coherency protocols are somewhat wasteful, think global broadcasts, and incredi…

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.

Re: Mutexes are faster than Spinlocks

#136

Post by shaklee3 »

sillysaurusx wrote: post #107
dfox wrote: post #103

Earlier quoted context omitted.

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…

This is also the reason DPDK uses a highly-efficient ring buffer. I believe (old benchmarks) it's faster than LMAX.

Re: Mutexes are faster than Spinlocks

#137

Post by shaklee3 »

rumanator wrote: post #51
gpderetta wrote: post #38

Earlier quoted context omitted.

Also if both threads are pinned to separate cores and nothing else is supposed to run on those cores, it is pointless to use anything but spinlocks as there is no other thread that could better use the core (and probably you do not want the core to go to a low power syate waiting for an interrupt).

> and nothing else is supposed to run on those cores That's quite the corner case.

This is the normal use case for any DPDK software. I think anyone involved in HPC or high-speed networking knows that this is pretty common.

Re: Mutexes are faster than Spinlocks

#138

Post by thatsenough »

vba wrote: post #62
simias wrote: post #56

Earlier quoted context omitted.

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

TFA? Tried to google but unsuccessful

The Fabulous Article.

Re: Mutexes are faster than Spinlocks

#139

Post by lowbloodsugar »

TFA makes the point that modern "mutex" implementations actually use spinlocks first and only fall back to heavy, kernel Mutexes if there is contention. So the title is click-baity. Mutexes are slower than spinlocks. The "faster than spinlocks" mutexes in this article are actually spinlocks that fallback to mutexes.

Then the benchmark uses spinlocks in situations that spinlocks aren't great for. And, surprise, spinlocks are slower, than spinlocks-with-mutexes.

Spinlocks are great in situations such as:

  * There are far more resources than threads,
  * The probability of actually having to spin is small,
    ideally if the time spent in the lock is a few instructions
  * When you can't use optimistic concurrency*
* because perhaps the number of memory locations to track is too complicated for my poor brain and I can't be arsed to remember how TLA+ works

There's plenty of linked list implementations, for example, that use optimistic concurrency. At that point you've got yourself a thread-safe message queue and that might be better than mutexes, too.

Re: Mutexes are faster than Spinlocks

#140

Post by bdash »

AstralStorm wrote: post #133
acqq wrote: post #58

Earlier quoted context omitted.

So this it acquires fully in userspace if there's no contention, it even spins if there is contention, and then if that wasn't enough it lets the thread sleep with the timeout. Which matches the description of that library: https://github.com/Amanieu/parking_lot "This library provides implementations of Mutex, RwLock, Condvar and Once that are smaller, faster and more flexible than those in the Rust standard library"…

How does it know that said critical section is short? Guessing? Likely a hard linear-quadratic expanding threshold. They tend to waste a lot of CPU power in specific algorithms. There are better, more intrusive ways of solving this problem on language level.

It doesn't attempt to determine the size of the critical section, AFAIK. I think it's saying that sleeping immediately when failing to acquire the lock would significantly hurt small critical sections, and so instead they spin a few times to avoid punishing those scenarios.
Post reply on HN