3 ms·

We use spinlocks where appropriate. In the 90s I recall that the general rule of thumb was if the lock is held for <10x the context switch time, spinlocks are g

We use spinlocks where appropriate. In the 90s I recall that the general rule of thumb was if the lock is held for <10x the context switch time, spinlocks are generally a better choice. Not sure if that's still true of contemporary architectures. The more common pattern in rt/audio code is "try to take the lock, but have an alternate code path if that fails". It's not that is never going to be contention, but it will be extremely rare, and when it occurs, it probably matters. RWLocks are also a common pattern, with the RT thread(s) being read-only (and still being required to fall back on an alternate code path if the read lock cannot be taken).

pizlonator 2y ago
These days, fast lock implementations use the following rough idiom, or some idiom that is demonstrably not any slower even for short critical sections. if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return; for (unsigned i = 0; i < 40; ++i) { /* spin for a bounded a mount of time */ if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return; sched_yield(); } ... /* actual full lock algo goes here */ So, the reason to use spinlocks isn't that they are faster for short critical sections, but that they don't have to CAS on unlock - and so they are faster especially in the uncontended case (and in all other cases too). In other words, the modern rule of thumb is something like: if you're going to grab the lock so frequently that the uncontended lock/unlock time shows up as a significant percentage of your execution time, then use a spinlock. That probably implies that you are probably holding the lock for <100x or even <1000x context switch time, or something around there.
- adastra22 2y ago
  Huh, interesting. TIL. Thanks for that!
  - xxs 2y ago
    Lots of code is 'lock free' and uses the same pattern (more or less). Attempt the change optimistically, if it fails spin it, if it keeps failing (Massive Contention), back off.
    - adastra22 2y ago
      A properly lock-free architecture wouldn’t have spin-locks, no?
      - xxs 2y ago
        of course, no lock. I have written quite the fair share of lock free code (back then when it was new), and generally enjoy writing it (to this day). Yet, for most folks it's just too hard to reason/understand/maintain it. Just a note, lock free is a lesser requirement than wait-free.
      - pjdesno 2y ago
        A properly lock-free architecture is a spin-lock :-)
        xxs 2y ago
        spin locks prevent forward grantees, e.g. when the thread is scheduled out (or serves an interrupt), no other thread can make progress. Lock free allows progress - there is no exclusivity. Of course if working on the kernel and controlling the scheduler, etc. the restriction does not apply immediately. Realistically though, lots of lock free employs copy-on-write or rcu.
- deleted 2y ago
  [deleted]
- loeg 2y ago
  > if you're going to grab the lock so frequently that the uncontended lock/unlock time shows up as a significant percentage of your execution time, then use a spinlock. Yeah, and maybe also consider changing your design because usually this isn't needed.
  - pizlonator 2y ago
    This is (in my experience) a byproduct of good design, so changing the design wouldn't be a great idea. Every time I've seen this happen it's in code that scales really well to lots of CPUs while having a lot of shared state, and the way it gets there is that it's using very fine-grained locks combined with smart load balancing. The idea is that the load balancer makes it improbable-but-not-impossible that two processors would ever want to touch the same state. And to achieve that, locks are scattered throughout, usually protecting tiny critical sections and tiny amounts of state. Whenever I've gotten into that situation or found code that was in that situation, the code performed better than if it had coarser locks and better than if it used lock-free algorithms (because those usually carry their own baggage and "tax"). They performed better than the serial version of the code that had no locks. So, the situation is: you've got code that performs great, but does in fact spend maybe ~2% of its time in the CAS to lock and unlock locks. So... you can get a tiny bit faster if you use a spinlock, because then unlocking isn't a CAS, and you run 1% faster.
spacechild1 2y ago
Keep in mind that while try_lock() is realtime-safe, the following unlock() may not, as it may need to wake threads that have been blocked in the meantime! So I would only use this pattern for situations where the very fact that a NRT thread tries to acquire the lock already means that RT safety is not a concern anymore (e.g. a device has been disconnected)
- PaulDavisThe1st 2y ago
  Excellent reminder. Yes, this is both a design defect of try/unlock that can't really be solved, and an implementation defect on several platforms that makes it worse than it actually needs to be (Windows, I'm looking at you)
  - spacechild1 2y ago
    One thing I've been using is a spinlock where the RT thread only uses try_lock() + fallback path and the NRT thread(s) call try_lock() in a loop with pause instructions and occasional thread yielding (or even sleeping). This might waste lots of CPU cycles when a NRT thread tries to acquire a lock that is already held by the RT thread, but assuming this only happens occasionally/rarely, it's a reasonable trade-off.
xmodem 2y ago
What type of scenarios come up in RT/audio code where an alternative path is available if you can't get a lock? In most of the concurrent code I've written the options available if I can't get a lock is some subset of try again, try again with backoff, or fail.
- Archit3ch 2y ago
  Let's say you are doing audio processing in the real-time thread. You try to lock to read new parameters, and if you fail to get the lock you do the processing with the old parameters.

pizlonator 2y ago

These days, fast lock implementations use the following rough idiom, or some idiom that is demonstrably not any slower even for short critical sections. if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return; for (unsigned i = 0; i < 40; ++i) { /* spin for a bounded a mount of time */ if (LIKELY(CAS(&lock, UNLOCKED, LOCKED))) return; sched_yield(); } ... /* actual full lock algo goes here */ So, the reason to use spinlocks isn't that they are faster for short critical sections, but that they don't have to CAS on unlock - and so they are faster especially in the uncontended case (and in all other cases too). In other words, the modern rule of thumb is something like: if you're going to grab the lock so frequently that the uncontended lock/unlock time shows up as a significant percentage of your execution time, then use a spinlock. That probably implies that you are probably holding the lock for <100x or even <1000x context switch time, or something around there.

adastra22 2y ago
Huh, interesting. TIL. Thanks for that!
- xxs 2y ago
  Lots of code is 'lock free' and uses the same pattern (more or less). Attempt the change optimistically, if it fails spin it, if it keeps failing (Massive Contention), back off.
  - adastra22 2y ago
    A properly lock-free architecture wouldn’t have spin-locks, no?
    - xxs 2y ago
      of course, no lock. I have written quite the fair share of lock free code (back then when it was new), and generally enjoy writing it (to this day). Yet, for most folks it's just too hard to reason/understand/maintain it. Just a note, lock free is a lesser requirement than wait-free.
    - pjdesno 2y ago
      A properly lock-free architecture is a spin-lock :-)
      - xxs 2y ago
        spin locks prevent forward grantees, e.g. when the thread is scheduled out (or serves an interrupt), no other thread can make progress. Lock free allows progress - there is no exclusivity. Of course if working on the kernel and controlling the scheduler, etc. the restriction does not apply immediately. Realistically though, lots of lock free employs copy-on-write or rcu.
deleted 2y ago
[deleted]
loeg 2y ago
> if you're going to grab the lock so frequently that the uncontended lock/unlock time shows up as a significant percentage of your execution time, then use a spinlock. Yeah, and maybe also consider changing your design because usually this isn't needed.
- pizlonator 2y ago
  This is (in my experience) a byproduct of good design, so changing the design wouldn't be a great idea. Every time I've seen this happen it's in code that scales really well to lots of CPUs while having a lot of shared state, and the way it gets there is that it's using very fine-grained locks combined with smart load balancing. The idea is that the load balancer makes it improbable-but-not-impossible that two processors would ever want to touch the same state. And to achieve that, locks are scattered throughout, usually protecting tiny critical sections and tiny amounts of state. Whenever I've gotten into that situation or found code that was in that situation, the code performed better than if it had coarser locks and better than if it used lock-free algorithms (because those usually carry their own baggage and "tax"). They performed better than the serial version of the code that had no locks. So, the situation is: you've got code that performs great, but does in fact spend maybe ~2% of its time in the CAS to lock and unlock locks. So... you can get a tiny bit faster if you use a spinlock, because then unlocking isn't a CAS, and you run 1% faster.

spacechild1 2y ago

Keep in mind that while try_lock() is realtime-safe, the following unlock() may not, as it may need to wake threads that have been blocked in the meantime! So I would only use this pattern for situations where the very fact that a NRT thread tries to acquire the lock already means that RT safety is not a concern anymore (e.g. a device has been disconnected)

PaulDavisThe1st 2y ago
Excellent reminder. Yes, this is both a design defect of try/unlock that can't really be solved, and an implementation defect on several platforms that makes it worse than it actually needs to be (Windows, I'm looking at you)
- spacechild1 2y ago
  One thing I've been using is a spinlock where the RT thread only uses try_lock() + fallback path and the NRT thread(s) call try_lock() in a loop with pause instructions and occasional thread yielding (or even sleeping). This might waste lots of CPU cycles when a NRT thread tries to acquire a lock that is already held by the RT thread, but assuming this only happens occasionally/rarely, it's a reasonable trade-off.

xmodem 2y ago

What type of scenarios come up in RT/audio code where an alternative path is available if you can't get a lock? In most of the concurrent code I've written the options available if I can't get a lock is some subset of try again, try again with backoff, or fail.

Archit3ch 2y ago
Let's say you are doing audio processing in the real-time thread. You try to lock to read new parameters, and if you fail to get the lock you do the processing with the old parameters.