Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Spinning around: Please don’t – Common problems with spin locks

siliceum.com

Post reply on HN
Print view View original

51–60 of 66 posts

Re: Spinning around: Please don’t – Common problems with spin locks

#51

Post by Phelinofist »

Lectem wrote: post #37
pizlonator wrote: post #27

TFA lists WebKit as a project that "does it wrong". The author should read https://webkit.org/blog/6161/locking-in-webkit/ so that they understand what they are talking about. WebKit does it right in the sense that: - It as an optimal amount of spinning - Threads wait (instead of spinning) if the lock is not available immediately-ish And we know that the algorithms are optimal based on rigorous experiments.

The author (me) actually read this long ago > - It as an optimal amount of spinning No it isn't, it has a fixed number of yields, which has a very different duration on various CPUs > Threads wait (instead of spinning) if the lock is not available immediately-ish They use parking lots, which is one way to do futew (in fact, WaitOnAddress is implemented similarly). And no if you read the code, they do spin. Worse, the…

I guess you mean this regarding spin locks? https://web.archive.org/web/20250219201712/https://www.intel...

The direct link to Intel 404s.

Re: Spinning around: Please don’t – Common problems with spin locks

#52

Post by electroglyph »

Animats wrote: post #33

I struggled with this in Wine. "malloc" type memory allocation involves at least two levels of spinlocks. When you do a "realloc", the spinlocks are held during the copying operation. If you use Vec .push in Rust, you do a lot of reallocs. In a heavily multithreaded program, this can knock performance down by more than two orders of magnitude. It's hard to reproduce this with a simple program; it takes a lot of concu…

Microsoft's rwlock implementation was borked up until sometime last year iirc. this stuff is difficult to do correctly

Re: Spinning around: Please don’t – Common problems with spin locks

#53

Post by jacobp100 »

Lectem wrote: post #37
pizlonator wrote: post #27

TFA lists WebKit as a project that "does it wrong". The author should read https://webkit.org/blog/6161/locking-in-webkit/ so that they understand what they are talking about. WebKit does it right in the sense that: - It as an optimal amount of spinning - Threads wait (instead of spinning) if the lock is not available immediately-ish And we know that the algorithms are optimal based on rigorous experiments.

The author (me) actually read this long ago > - It as an optimal amount of spinning No it isn't, it has a fixed number of yields, which has a very different duration on various CPUs > Threads wait (instead of spinning) if the lock is not available immediately-ish They use parking lots, which is one way to do futew (in fact, WaitOnAddress is implemented similarly). And no if you read the code, they do spin. Worse, the…

The guy you relied to wrote the locking code. If you’re so certain they’re doing it wrong, would it not be easier to just prove it? It’s only one file, and they already have benchmarking set up

Re: Spinning around: Please don’t – Common problems with spin locks

#54

Post by imtringued »

squirrellous wrote: post #30
jcranmer wrote: post #5

The basic rule of writing your own cross-thread datastructures like mutexes or condition variables is... don't, unless you have very good reason not to. If you're in that rare circumstance where you know the library you're using isn't viable for some reason, then the next best rule is to use your OS's version of a futex as the atomic primitive, since it's going to solve most of the pitfalls for you automatically. The…

Another somewhat known case of a spinlock is in trading, where for latency purposes the OS scheduler is essentially bypassed by core isolation and thread pinning, so there’s nothing better for the CPU to do than spinning.

This is the primary use case for spinlocks, which is why the vast majority of developers shouldn't use them. When you use a spinlock, you're dedicating an entire CPU core to the thread or else it doesn't work in terms of correctness or performance.

If you want scheduling, then the scheduler needs to be aware of task dependencies and you must accept that your task will be interrupted.

When a lock is acquired on resource A by the first thread, the second thread that tries to acquire A will have a dependency on the release of A, meaning that it can only be scheduled after the first thread has left the critical section. With a spinlock, the scheduler is not informed of the dependency and thinks that the spinlock is performing real work, which is why it will reschedule waiting threads even if resource A has not been released yet.

If you do thread pinning and ensure there are less threads than CPU cores, but still have other threads be scheduled on those cores, it might still work, but the latency benefits are most likely gone.

Re: Spinning around: Please don’t – Common problems with spin locks

#55

Post by imtringued »

horizion2025 wrote: post #31

My concurrency knowledge is a bit rusty but aren't spinlocks only supposed to be used for very brief waits like in the hundreds of cycles (or situations where you can't block... like internal o/s scheduling structures in SMP setups)? If so how much does all this back off and starvation of higher priority threads even matter? If it is longer then you should use a locking primitive (except for in those low level os str…

How can you guarantee that the OS doesn't preempt your thread in the middle of the spinlock? Suddenly your 100 cycle spinlock turns into millions or billions of wasted cycles, because the other threads that are trying to acquire the same lock are spinning and didn't bother informing the OS scheduler that they need the thread that is holding the spinlock, which also didn't inform the OS, to finish its business ASAP.

Re: Spinning around: Please don’t – Common problems with spin locks

#56

Post by imtringued »

CamperBob2 wrote: post #3

Sheesh. Can something this complicated ever truly be said to work?

It works if there is no scheduler, or you tell the scheduler what you're doing.

Turns out the first scenario is rare outside of embedded or OS development. The second scenario defeats the purpose because you're doing the same thing a mutex would be doing. It's not like mutexes were made slow on purpose to bully people. They're actually pretty fast.

Re: Spinning around: Please don’t – Common problems with spin locks

#57

Post by Lectem »

jacobp100 wrote: post #53
Lectem wrote: post #37

Earlier quoted context omitted.

The author (me) actually read this long ago > - It as an optimal amount of spinning No it isn't, it has a fixed number of yields, which has a very different duration on various CPUs > Threads wait (instead of spinning) if the lock is not available immediately-ish They use parking lots, which is one way to do futew (in fact, WaitOnAddress is implemented similarly). And no if you read the code, they do spin. Worse, the…

The guy you relied to wrote the locking code. If you’re so certain they’re doing it wrong, would it not be easier to just prove it? It’s only one file, and they already have benchmarking set up

I mean my "No it isn't, it has a fixed number of yields, which has a very different duration on various CPUs" can be verified directly by having a look at the table in my article showing different timings for pause.

For the yield part, I already linked to the part that shows that. Yes it doesn't call yield if it sees others are parked, but on quick lock/unlock of threads it happens that it sees nobody parked and fails, yielding directly to the OS. This is not frequent, but frequent enough that it can introduce delay issues.

Re: Spinning around: Please don’t – Common problems with spin locks

#58

Post by foldr »

> The code is not thread-safe as, if multiple threads attempt to use this lock, we could read invalid values of isLocked (in theory, and on a CPU where tearing could happen on its word size).

The issue isn’t just tearing but also memory order. On some architectures you can read a valid but out of date value in Thread A after Thread B has updated that value. (Memory order is mentioned later in the article, to be fair.)

Re: Spinning around: Please don’t – Common problems with spin locks

#59

Post by arghwhat »

Lectem wrote: post #37
pizlonator wrote: post #27

TFA lists WebKit as a project that "does it wrong". The author should read https://webkit.org/blog/6161/locking-in-webkit/ so that they understand what they are talking about. WebKit does it right in the sense that: - It as an optimal amount of spinning - Threads wait (instead of spinning) if the lock is not available immediately-ish And we know that the algorithms are optimal based on rigorous experiments.

The author (me) actually read this long ago > - It as an optimal amount of spinning No it isn't, it has a fixed number of yields, which has a very different duration on various CPUs > Threads wait (instead of spinning) if the lock is not available immediately-ish They use parking lots, which is one way to do futew (in fact, WaitOnAddress is implemented similarly). And no if you read the code, they do spin. Worse, the…

For reference, golang's mutex also spins by up to 4 times before parking the goroutine on a semaphore. A lot less than the 40 times in the webkit blogpost, but I would definitely consider spinning an appropriate amount before sleeping to be common practice for a generic lock. Granted, as they have a userspace scheduler things do differ a bit there, but most concepts still apply.

https://github.com/golang/go/blob/2bd7f15dd7423b6817939b199c...

https://github.com/golang/go/blob/2bd7f15dd7423b6817939b199c...

Re: Spinning around: Please don’t – Common problems with spin locks

#60

Post by bluGill »

pjmlp wrote: post #50
bluGill wrote: post #13

Earlier quoted context omitted.

They can, but nobody runs a single process on such CPUs. They run some form of OS which implements spinlock, mutexes, and all these other complex things. I suppose someplace someone is running an embedded system without an OS on such a processor - but I'd expect they are still using extra cores and so have all of the above tricks someplace.

I never get the single threaded assertions regarding CPU performance, it is mostly useless in the day of premptive scheduling in modern OSes. Yes it matters on MS-DOS like OS design, like some embedded deployments and that is about it. It is even impossible to guarantee a process doesn't get rescheduled into another CPU with the performance impact it entails, unless the process explicitly sets its CPU affinity.

If you don't allow complev things like spinlocks then all that is left is single thread performance.
Post reply on HN