5 ms·
Optimizing a Spin-Lock
- dalvrosa 2mo agoThanks for sharing! Happy to get feedback :) Note that I don't recommend spinlock for most cases, only when there is a 1:1 mapping between threads and phsycal CPU cores, and only after measuring
- loeg 2mo agoSpinlocks are unsuitable for situations where you can be involuntarily context switched (the vast majority of userspace programs). Probably worth mentioning that.
- josefx 2mo agoUnsuitable? Probably depends on your use case. Even a normal end user system shouldn't constantly kick your threads out unless it has enough other things to do to to keep every core busy.
- loeg 2mo ago> unless it has enough other things to do to to keep every core busy. And in this all-cores-busy case, do you want your waiters burning one of those precious cores while lock holders are preempted? If you care enough about your system design to even affirmatively select spinlocks in the first place, you should probably also care enough to not use them in preemptible userspace. Or at least, I am not aware of any reasonable usecase. Hybrid sleeplocks are fine, of course.
- tombert 2mo agoI genuinely had not heard of anyone actually using a spinlock in production code until I started using LMAX Disruptor a few years ago. I was always told that they were an anti-pattern, and I think that generally that is a pretty good rule of thumb, but I guess like most stuff in CS: there are always exceptions to "good rules of thumb". I still haven't actually explicitly written a spinlock for anything in production, but Disruptor has shown me that there are cases for it.
- sedatk 2mo agoIt’s one of the secret ingredients to avoid a Big Kernel Lock™.
- BoingBoomTschak 2mo agoI think Linus says it well: https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723 https://www.realworldtech.com/forum/?threadid=189711&curpost...
- markus_zhang 2mo agoThanks for sharing. Can someone tell me what does this paragraph mean? > Use a lock where you tell the system that you're waiting for the lock, and where the unlocking thread will let you know when it's done, so that the scheduler can actually work with you, instead of (randomly) working against you. I have “implemented” a sleep lock in xv6. Is it what he meant? What does the Linux scheduler “know” about it and will do differently? (Trying to figure out what does “work with you” mean) Thanks in advance.
- moregrist 2mo agoIn simplest terms: if you don’t tell the kernel that you’re waiting, the scheduler assumes you aren’t and will wake you up and let you spin, to the detriment of other threads that aren’t waiting. If the OS knows that a thread is waiting for a lock, the scheduler will not bother to schedule it until the lock is available. In general, it’s tempting when you’re bound by lock latency to skip the syscall overhead of sleeping. But a lot of the time that’s a code smell that there are other inefficiencies in the system and you should rethink how you’re scheduling work.
- rcxdude 2mo agoThe basic idea is that a lock should be something the OS is aware of, so that while a thread is blocked on a lock, the scheduler never tries to wake it at all, and when it is unlocked, the scheduler can wake up the thread that's waiting on it immediately. If the scheduler isn't aware of the lock, it'll just try to wake up the thread periodically, often just wasting CPU when it's still blocked or kept asleep when it could be running.
- jeffbee 2mo agoThis would have different answers depending on if it ran on a machine with a more closely-shared cache, right? For example on an Intel efficiency core cluster where 4 cores share an L2.
- cnrcode 2mo ago[flagged]
- gavinlilly 2mo agoIf contention is expected, would it be better to first perform a relaxed read before the exchange? For example: auto lock() noexcept -> void { auto backoff = 1; do { while (locked_.load(std::memory_order_relaxed)) { for (auto i = 0; i < backoff; ++i) _mm_pause(); backoff = backoff < 64 ? backoff << 1 : 64; } } while (locked_.exchange(true, std::memory_order_acquire); }
- nly 2mo agoIf you're expecting heavy contention, and there's no risk of any of the threads being descheduled, then FIFO spinlocks are probably best. In a FIFO threads register themselves into a linked list, and the thread calling unlock() directly wakes the next. It's possible to have e.g. 20 threads in this case all spinning on their own cache lines (their private node), rather than a shared one (the lock head). This can be coherence protocol optimal. A dumb test and set spinlock, or variant thereof, is going to degrade quickly as all the cores are spinning on the same cacheline causing a lot of coherence traffic between cores (transitions between shared, exclusive and modified states)
- pizlonator 2mo agoSuper dangerous to benchmark lock performance using microbenchmarks. If you have a tiny benchmark, then you're putting the CPU and memory into a very specific and unusual state (everything is quiet other than the lock itself). The real world story for locks is usually that you're not rage-contending 100% of the time, but that you have some contention combined with CPUs doing some real work and some real memory accesses. What I've found is that in those more real scenarios, the locks that perform best in microbenchmarks fall apart compared to completely different and unexpected algorithms.
- neeeeees 2mo agoTo repurpose a famous quote - all benchmarks are wrong, but some are useful
- dalvrosa 2mo agoFair enough yeah. IMO microbenchmarks are useful for trying to gain intuition and propose the next incremental improvement. In real world measuring is mandatory, if you don't want to risk pessimizing the code
- pizlonator 2mo agoThe wild thing about locks in particular is that microbenchmarks will cause you to make „optimizations” that are the opposite of what benefits real world workloads.
- dfphil 2mo ago[dead]
- RossBencina 2mo agoTFA mentions power usage from a dollar cost perspective, but there is also the thermal aspect. You do not want to trigger thermal throttling (or lose boost) while doing almost nothing.
- dalvrosa 2mo agoVery good point, should add this
- vova_hn2 2mo agoI want to share an excellent related article, "A Concurrency Cost Hierarchy" [0] by Travis Downs [1]. It was posted to HN many times [2], the largest discussion has 26 comments [3]. My own programming experience is mostly Python, so throughout the most of my career I treated locks as pure magic and didn't think much about what happens under the hood. At some point in my life I became interested in Rust and lower-level programming and this article in particular really helped me to set my head straight on this topic. It doesn't only explain how concurrency primitives actually work, but it also explains why they work this way, what choices and trade-offs are involved. This article uses C++ for all examples, but there are really nothing language specific, all principles will work in Rust, C, Zig etc [0] https://travisdowns.github.io/blog/2020/07/06/concurrency-costs.html https://travisdowns.github.io/blog/2020/07/06/concurrency-co... [1] https://travisdowns.github.io/ https://travisdowns.github.io/ [2] https://hn.algolia.com/?q=https%3A%2F%2Ftravisdowns.github.io%2Fblog%2F2020%2F07%2F06%2Fconcurrency-costs.html https://hn.algolia.com/?q=https%3A%2F%2Ftravisdowns.github.i... [3] https://news.ycombinator.com/item?id=24489829 https://news.ycombinator.com/item?id=24489829
- ennepoai 2mo ago[flagged]
- DmitryOlshansky 2mo agoI think one area where spinlock could be useful is fibers. There you have an option to schedule another fiber instead of spinning CPU until timeslice runs out.
- hn3ufz62f7 2mo ago[dead]