4 ms·

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 s

by 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.

by archy_ 7y ago

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.