3 ms·

> The spin until success strategy seen above is employed in many lock-free algorithms and is called spinlock: a simple loop where the thread repeatedly tries to

by comex 7y ago

> The spin until success strategy seen above is employed in many lock-free algorithms and is called spinlock: a simple loop where the thread repeatedly tries to perform something until successful. It's a form of gentle lock where the thread is up and running — no sleep forced by the operating system, although no progress is made until the loop is over. Regular locks employed in mutexes or semaphores are way more expensive, as the suspend/wakeup cycle requires a lot of work under the hood. A compare-and-swap loop is not a spinlock. (It is the primitive used to implement a spinlock, but that's different.) Pure spinlocks are almost always a bad idea, at least in userland, because threads spinning trying to acquire the lock look "busy" to the scheduler, so the scheduler may run them instead of the thread that owns the lock. It does make sense to spin a limited number of times before going through the slow path to acquire a mutex, but most OS mutex implementations have that functionality built in, so there's usually no need to do that manually.

fulafel 7y ago
Nitpick: cas is the spinlock primitive on some hw platforms, others use eg ll/sc.
archy_ 7y ago
Why would it make more sense to "spin a limited number of times before going through the slow path to acquire a mutex"? Does a mutex have more overhead in the short term than a spinlock but after a few cycles become more efficient? Off topic, but I remember reading that the Linux kernel prefers spinlocks to mutexes. Is there a good technical reason for that?
- dragontamer 7y ago
  > Does a mutex have more overhead in the short term than a spinlock but after a few cycles become more efficient? Think about what a true mutex does. The true mutex switches into kernel mode (aka: your program is no longer running, Linux is running). That means a spectre-guard / meltdown guard is executed (your TLB buffer may be flushed, as well as various other memory-guards to prevent Spectre from leaking data). Once the guards are executed, kernel-mode has to find more work to do. Traversing the kernel-data structures can take 1 to 10 microseconds, depending on how cold the cache is. Finally, since another thread may be running (before your thread comes back), you probably lost all your data from L1 cache (and at minimum: your branch-predictor state because of Spectre). A spinlock without any contention takes less than 10-nanoseconds to run, to maybe 50-nanoseconds with a bit of contention (!!). You're basically reading/writing data to L1 cache, maybe L3 cache under contention. However, a scheduler invocation will be on the order of 5000 nanoseconds (~5 microeconds) or so, due to all of the work that the scheduler has to do. -------- Window's default spincount is something on the order of 4000 cycles. Spinning for 4000-cycles (or less) is an advantage towards a spinlock-like methodology. (4000 cycles x 4GHz == 1-microsecond). Just to give you an idea of the speed-magnitudes that are being discussed here.
  - lallysingh 7y ago
    That's 4000 cycles @ 4 GHz == 1us right?
    - dragontamer 7y ago
      Yes, sorry. I'll go edit that correctly really quick...
- charleslmunger 7y ago
  Depends on the mutex implementation. Many mutexes will do their own spinning internally - for short critical sections, you can avoid sleeping and waking your thread, a (relatively) expensive operation. Obviously spinning for an unlimited amount of time is less efficient - in the case of a priority inversion, you'll effectively deadlock. [1] There's also tools like [2], where you can tell a mutex to spin if the current lock holder is actively running (as opposed to blocked or preempted), to get the best of both worlds. [1] https://blog.postmates.com/why-spinlocks-are-bad-on-ios-b69fc5221058 https://blog.postmates.com/why-spinlocks-are-bad-on-ios-b69f... [2] https://lwn.net/Articles/724384/ https://lwn.net/Articles/724384/
- scott_s 7y ago
  > Why would it make more sense to "spin a limited number of times before going through the slow path to acquire a mutex"? Have you ever waited at a door for someone, and after a long enough time, sat down on the floor? It's basically the same logic. First, the "slow path" for acquiring a true mutex involves calling into the kernel. This is relatively expensive. At first, you hope that your waiting time will be very small. So you optimistically just spin in user-space waiting for the lock to be released. But this spinning is expensive: you're consuming the CPU doing nothing productive. Eventually, there's a basic principle to consider: the longer you wait, the more likely you are to wait longer. After along enough wait, you assume you're going to wait even longer, so it's worth it to pay the cost of calling into the kernel so that someone else who has productive work to do can do that while you're waiting. Kernels will use spinlocks in various places because the kernel implementors know that the critical sections will be short, or they know that scheduling another task over the current one would be problematic.
gpderetta 7y ago
> Pure spinlocks are almost always a bad idea True, but they might still appropriate for very tiny critical sections (a handful of instructions) of finely distributed locks where the probability of both contention and preemption is very low. Also some applications have the luxury to exclusively dedicate on thread per core.
- vardump 7y ago
  > Also some applications have the luxury to exclusively dedicate on thread per core. To save power and thermals to enable higher frequencies for other cores doing useful work, if the latency requirements and CPU architecture allows, be nice and put the spinning CPU in a lower power state. Like x86 PAUSE or MONITOR/MWAIT instructions.
  - deleted 7y ago
    [deleted]
  - vardump 7y ago
    Someone wrote a comment and then quickly deleted it. Since I already typed a reply, I'll include it here anyways: --- > Does this mean all spinlock operations are pinned to the low-power core? That wouldn't make sense. Perhaps for example in a case a core is allocated to immediately operate on some data once the spinlock is released. > If yes, how is this usually supported by OS/language runtimes? That really depends as MONITOR and MWAIT require ring 0. That means executing those instructions in userland always causes an exception. Yeah, I develop kernel drivers... :-) PAUSE [0] works at any ring level, so it works fine in usermode code. It's encoded just as "REP NOP". > And as soon as the spinlock operations succeed, the work will be moved out of the low-power core, which would involve the usual context switch costs. So I'm assuming this strategy would need a lot of workload-specific benchmarking before you decide to use it. If you're doing this, you're actively avoiding context switches. That's the whole point in this kind of spinning. Kernel is not involved for usermode code. [0]: https://c9x.me/x86/html/file_module_x86_id_232.html https://c9x.me/x86/html/file_module_x86_id_232.html

by comex 7y ago

fulafel 7y ago

Nitpick: cas is the spinlock primitive on some hw platforms, others use eg ll/sc.

archy_ 7y ago

Why would it make more sense to "spin a limited number of times before going through the slow path to acquire a mutex"? Does a mutex have more overhead in the short term than a spinlock but after a few cycles become more efficient? Off topic, but I remember reading that the Linux kernel prefers spinlocks to mutexes. Is there a good technical reason for that?

dragontamer 7y ago
> Does a mutex have more overhead in the short term than a spinlock but after a few cycles become more efficient? Think about what a true mutex does. The true mutex switches into kernel mode (aka: your program is no longer running, Linux is running). That means a spectre-guard / meltdown guard is executed (your TLB buffer may be flushed, as well as various other memory-guards to prevent Spectre from leaking data). Once the guards are executed, kernel-mode has to find more work to do. Traversing the kernel-data structures can take 1 to 10 microseconds, depending on how cold the cache is. Finally, since another thread may be running (before your thread comes back), you probably lost all your data from L1 cache (and at minimum: your branch-predictor state because of Spectre). A spinlock without any contention takes less than 10-nanoseconds to run, to maybe 50-nanoseconds with a bit of contention (!!). You're basically reading/writing data to L1 cache, maybe L3 cache under contention. However, a scheduler invocation will be on the order of 5000 nanoseconds (~5 microeconds) or so, due to all of the work that the scheduler has to do. -------- Window's default spincount is something on the order of 4000 cycles. Spinning for 4000-cycles (or less) is an advantage towards a spinlock-like methodology. (4000 cycles x 4GHz == 1-microsecond). Just to give you an idea of the speed-magnitudes that are being discussed here.
- lallysingh 7y ago
  That's 4000 cycles @ 4 GHz == 1us right?
  - dragontamer 7y ago
    Yes, sorry. I'll go edit that correctly really quick...
charleslmunger 7y ago
Depends on the mutex implementation. Many mutexes will do their own spinning internally - for short critical sections, you can avoid sleeping and waking your thread, a (relatively) expensive operation. Obviously spinning for an unlimited amount of time is less efficient - in the case of a priority inversion, you'll effectively deadlock. [1] There's also tools like [2], where you can tell a mutex to spin if the current lock holder is actively running (as opposed to blocked or preempted), to get the best of both worlds. [1] https://blog.postmates.com/why-spinlocks-are-bad-on-ios-b69fc5221058 https://blog.postmates.com/why-spinlocks-are-bad-on-ios-b69f... [2] https://lwn.net/Articles/724384/ https://lwn.net/Articles/724384/
scott_s 7y ago
> Why would it make more sense to "spin a limited number of times before going through the slow path to acquire a mutex"? Have you ever waited at a door for someone, and after a long enough time, sat down on the floor? It's basically the same logic. First, the "slow path" for acquiring a true mutex involves calling into the kernel. This is relatively expensive. At first, you hope that your waiting time will be very small. So you optimistically just spin in user-space waiting for the lock to be released. But this spinning is expensive: you're consuming the CPU doing nothing productive. Eventually, there's a basic principle to consider: the longer you wait, the more likely you are to wait longer. After along enough wait, you assume you're going to wait even longer, so it's worth it to pay the cost of calling into the kernel so that someone else who has productive work to do can do that while you're waiting. Kernels will use spinlocks in various places because the kernel implementors know that the critical sections will be short, or they know that scheduling another task over the current one would be problematic.

gpderetta 7y ago

> Pure spinlocks are almost always a bad idea True, but they might still appropriate for very tiny critical sections (a handful of instructions) of finely distributed locks where the probability of both contention and preemption is very low. Also some applications have the luxury to exclusively dedicate on thread per core.

vardump 7y ago
> Also some applications have the luxury to exclusively dedicate on thread per core. To save power and thermals to enable higher frequencies for other cores doing useful work, if the latency requirements and CPU architecture allows, be nice and put the spinning CPU in a lower power state. Like x86 PAUSE or MONITOR/MWAIT instructions.
- deleted 7y ago
  [deleted]
- vardump 7y ago
  Someone wrote a comment and then quickly deleted it. Since I already typed a reply, I'll include it here anyways: --- > Does this mean all spinlock operations are pinned to the low-power core? That wouldn't make sense. Perhaps for example in a case a core is allocated to immediately operate on some data once the spinlock is released. > If yes, how is this usually supported by OS/language runtimes? That really depends as MONITOR and MWAIT require ring 0. That means executing those instructions in userland always causes an exception. Yeah, I develop kernel drivers... :-) PAUSE [0] works at any ring level, so it works fine in usermode code. It's encoded just as "REP NOP". > And as soon as the spinlock operations succeed, the work will be moved out of the low-power core, which would involve the usual context switch costs. So I'm assuming this strategy would need a lot of workload-specific benchmarking before you decide to use it. If you're doing this, you're actively avoiding context switches. That's the whole point in this kind of spinning. Kernel is not involved for usermode code. [0]: https://c9x.me/x86/html/file_module_x86_id_232.html https://c9x.me/x86/html/file_module_x86_id_232.html