10 ms·

Measuring mutexes, spinlocks and how bad the Linux scheduler is

331 points by bazzargh 7y ago

pedrocr 7y ago
Why isn't the conclusion to just use the mutex at least on Linux? It seems to have both consistently low latency and great throughput. What else can you get from the spinlock?
- jiveturkey 7y ago
  > What these benchmarks have in common is that they measure code in which there is nothing else to do except fight over the lock. In that environment the only thing that makes sense is to use a spinlock. Because if you go to sleep, all that will happen is that some other thread will wake up that will fight over the same lock. That said, his conclusion is in fact just as you stated, if you read in between the lines. (This paper is really about the scheduler, so it's not exactly that conclusion.)
  - trasz 7y ago
    And that’s precisely what most operating systems other than Linux do: use adaptive mutexes as the default mechanism, not spinlocks.
    - gpderetta 7y ago
      Pthread_mutex on linux is also an adaptive mutex, although the spinning count might not be optimal.
  - banachtarski 7y ago
    You don't even need to read in between the lines. He literally states that in his conclusion...
- 7532yahoogmail 7y ago
  No that was the conclusion: use mutexes
- banachtarski 7y ago
  > Why isn't the conclusion to just ... Sigh. From the article itself: > I hope to have convinced you to avoid spinlocks, even for very short sections. Spinlocks are only a benefit if you really really care about the fast path and are certain that the lock will essentially always be free to take. On my computer the fast path on a spinlock is roughly 7ns and on a mutex it’s roughly 14ns, so both of those numbers are very fast. But when spinlocks go bad, the scheduler can be really confused, at least on Linux.
  - pedrocr 7y ago
    I did read it till the end but missed that bit about the fast path somehow. I struggle to see a case where you care enough about those 7ns but the Windows scheduler was a different story.
pixel_fcker 7y ago
I think the answer, as always, is to measure on your own workloads. I’ve seen real-world production code get significant speed ups by switching to spinlocks from mutexes. Very interesting post though. I’ve never considered the idle latency before.
pmoriarty 7y ago
Can someone knowledgable explain what a mutex is, what a spinlock is, and the difference between mutexes and spinlocks?
- ptr 7y ago
  A spinlock is a kind of mutex (“mutual exclusion”) where in a condition is checked as fast as possible in a loop. This is useful when the expected wait times are short as you don’t have to pay the context switch penalty. Typically done when you have real parallelism with multiple CPUs/cores. A mutex can also refer to a particular group of “mutual exclusion” methods where in the current process/thread is suspended until the condition is true. Hope this helps.
  - jonny383 7y ago
    Additional note that mutual exclusion is a concept that pops up a lot when dealing with concurrent processing (think threads, multi-process type architectures). Typically mutex / spinlock is implemented to reduce and prevent race conditions
    - edoceo 7y ago
      One can see this at a higher level in Golang, where a gofunc are reading/updating a map - and run with -race then it shows where you have to use a Mutex call to lock that Map for the access, R or RW. Higher level but pretty simple to see.
      - zozbot234 7y ago
        One can see this at an even higher level in Rust, where you don't even need a "race checker" to avoid data races in safe code - the compiler will force the use of patterns like Mutex<> or Rwlock<> (or others) for stuff that might be accessed concurrently in ways that would otherwise break mutual exclusion.
        jonny383 7y ago
PaulDavisThe1st 7y ago
(reposting my comment from the original) There’s some potentially misleading information here. Background: I’ve spent the last 20+ years writing low-latency realtime audio applications, technically cross-platform but focused on Linux. If you care about low latency on any general purpose OS, you need to use a realtime scheduling policy. The default scheduling on these OS’s is intended to maximise some combination of bandwidth and/or fairness. Low latency requires ditching both of those in favor of limiting the maximum scheduling delay of a thread that is otherwise ready to run. Measuring how long synchronization primitives take without SCHED_FIFO is illustrative, but only of why, if you care about scheduling latency, you need SCHED_FIFO. There are several alternative schedulers for Linux – none of them remove the need for SCHED_FIFO if latency is important. It is absolutely not the case that using SCHED_FIFO automatically starves non-SCHED_FIFO threads. Scheduling policy is set per-thread, and SCHED_FIFO will only cause issues if the threads that use it really do “burn the CPU” (e.g. by using spinlocks). If you combine SCHED_FIFO with spinlocks you need to be absolutely certain that the locks have low contention and/or are held for extremely short periods (preferably just a few instructions). If you use mutexes (which ultimately devolve to futexes at the kernel level), the kernel will take care of you a little better, unless your SCHED_FIFO thread doesn’t block – if it doesn’t do that, that’s entirely on you. Blocking means making some sort of system call that will cause the scheduler to put the thread to sleep – could be a wait on a futex, waiting for data, or an explicit sleep. In particular, this: “This was known for a while simply because audio can stutter on Linux when all cores are busy (which doesn’t happen on Windows)” is NOT true. Linux actually has better audio performance than Windows or macOS, but only if the app developer understands a few basic principles. One of them is using SCHED_FIFO appropriately. Pro-audio/music creation scheduling is MUCH more demanding than video, and a bit more demanding than games. Linux handles this stuff just fine – it just gives you enough rope to shoot yourself in the foot if you don’t fully understand what you’re doing.
- segfaultbuserr 7y ago
  For the same reason, by default, PulseAudio uses rtkit to escalate its privileges and set its scheduler policy to SCHED_FIFO (then drop the privilege). Many people don't understand it and see it as another example of how Lennart's software is taking over the world (especially when you use a distribution like Arch that didn't already have rtkil configured for you), but it's essential for good audio latency (but the audio player needs SCHED_FIFO as well, there's nothing to help if the player itself is locking up). > SCHEDULING > high-priority= Renice the daemon after startup to become a high-priority process. This a good idea if you experience drop-outs during playback. However, this is a certain security issue, since it works when called SUID root only, or RLIMIT_NICE is used. root is dropped immediately after gaining the nice level on startup, thus it is presumably safe. See pulseaudio(1) for more information. > Takes a boolean argument, defaults to yes. The --high-priority command line option takes precedence. > realtime-scheduling= Try to acquire SCHED_FIFO scheduling for the IO threads. The same security concerns as mentioned above apply. However, if PA enters an endless loop, realtime scheduling causes a system lockup. Thus, realtime scheduling should only be enabled on trusted machines for now. Please note that only the IO threads of PulseAudio are made real-time. The controlling thread is left a normally scheduled thread. Thus enabling the high-priority option is orthogonal. See pulseaudio(1) for more information. > Takes a boolean argument, defaults to yes. The --realtime command line option takes precedence.
devit 7y ago
The claim that "the Linux scheduler is bad" seems wrong. First of all, a program that calls sched_yield() for synchronization is simply broken, since doing so can cause 100% CPU usage (if the other thread is stopped at an unfortunate place), so the only correct method among the ones benchmarked is std::mutex. When using std::mutex (the only correct approach), Linux and Windows both seem to have similar average performance, but Windows has 10x latency, so Linux is better.
- newnewpdro 7y ago
  sched_yield() isn't being used for synchronization, it's to yield the calling thread before its timeslice is exhausted because it's potentially preventing the lock-holder thread from getting scheduled to run and releasing it. Spinlocks assume the critical section is fast and non-blocking, so when the spinning lasts longer than expected, throwing in a yield can help by handing some CPU time to something else. The lock-holder might be getting scheduled on the same CPU and waiting for this thread to yield, or there might just be excessive threads runnable right now and burning cycles pointlessly spinning isn't helping get the lock-holder to run and release the lock any sooner. In a situation where you have exactly as many threads as there are CPUs, and they've been assigned their own respective CPUs, and there's nothing else running on the system, I wouldn't expect the yield to help. But that ideal isn't how things generally look in practice.
  - gpderetta 7y ago
    If a spin lock ends up in a call to sched_yeld, it means that it is already outside its intended use case (uncontrnded or nearly uncontented), so it is a bit pointless to optimize this path or expect any sane scheduling behaviour. If contention is probable it is better to fall back on a futex after a few[1] busy spins. This is what pthread_mutex (and pretty much every decent OS provided mutex does) on glibc by default. [1] how much is 'few' of course is often application dependent.
  - devit 7y ago
    You must not use sched_yield() and also must not spin indefinitely. Instead, one should optionally spin for up to a constant number of iterations and then call sys_futex.
mehrdadn 7y ago
Windows has process and thread priorities, including so-called "real-time" ones... but there seem to be no mentions of them in the article, as opposed to Linux. Why?
amluto 7y ago
I’m not convinced the measurements are really meaningful in this article. The author seems to be running a bunch of threads, measuring the time from when one thread starts unlocking the lock to when another thread gets it and calling this “idle”. I can’t find any mention of how many threads there are, how many CPUs, or what else the system is doing. So this is measuring a mess of a few things: For mutexes (assuming all the implementations actually make syscalls for unlocking), this has something to do with how long it takes for the scheduler to activate the waiter and run it, plus how long the scheduler waits because the system is doing something else or it wants to try to avoid bouncing a task between CPUs. For anything that does not involve the kernel in unlocking, this is really just a measurement of the pauses in execution of long-running threads that continuously hog the CPU. If the thread is also calling sched_yield(), the results are erratic, since sched_yield() more or less means “I don’t want to run now, but I’m not actually waiting for anything visible to the scheduler and, um, run me again soon maybe?” This is almost always the wrong solution. Other than that, this test has essentially nothing to do with which spinlock is in use, unless the spinlock itself wastes time failing to figure out that it’s ready. From old memory, the Windows scheduler is (was?) mostly based on per-thread priorities, highest priority wins, where the priorities are occasionally automatically adjusted. So, if you set a high-ish priority, you get to hog the CPU. In contrast, Linux tries quite hard not to let normal (non-RT) threads hog the CPU, so a thread that effectively runs continuously measuring pauses will detect significant pauses in which Linux decides that the rest of the system deserves to run too.
- RossBencina 7y ago
  I agree that the post needs to clarify the number of threads, what thread priorities were assigned, and what measures were taken to associate the threads with logical CPUs (affinities). I think your characterization of sched_yield() is a bit off. The man page is clear: "sched_yield() causes the calling thread to relinquish the CPU. The thread is moved to the end of the queue for its static priority and a new thread gets to run." and "If the calling thread is the only thread in the highest priority list at that time, it will continue to run after a call to sched_yield()." In particular, it does not say "I’m not actually waiting for anything visible to the scheduler and, um, run me again soon maybe?". So assuming that the threads are running at some relatively high priority, I'm struggling to see how delays on the order of 60ms could arise. EDIT: reading further: "sched_yield() is intended for use with real-time scheduling policies (i.e., SCHED_FIFO or SCHED_RR). Use of sched_yield() with nondeterministic scheduling policies such as SCHED_OTHER is unspecified and very likely means your application design is broken." So maybe that's it. [1] http://man7.org/linux/man-pages/man2/sched_yield.2.html http://man7.org/linux/man-pages/man2/sched_yield.2.html
newnewpdro 7y ago
I would like to see the measurements when the threads are explicitly assigned to their respective CPUs. It surprised me to not see even a mention of CPU affinity.
- dpc_pw 7y ago
  For any sort of benchmarking like that you have to take care of affinities and cpufreq governor at minimum.
  - newnewpdro 7y ago
    yep, I was assuming they at least didn't have any frequency scaling or powersave governor junk going on but you're right - it wasn't even mentioned so...
cryptica 7y ago
IMO mutexes, semaphores, spinlocks should be used only in special cases (e.g. games or other high perf logic where you need to maximize performance by a fixed percentage) because they are anti-patterns for scalability. They only help to scale up to a point after which all the threads either spend all their time waiting for each other to release the locks or they can never acquire the locks because the demand for that shared memory is too high. There are exceptions for example if you have unlimited reader threads/processes compared to a fixed number of writer threads/processes but even in those cases, I feel that shared memory locks add invisible bottlenecks to scalability as the code evolves over time. For most of my use cases, I prefer to keep processes/threads parallel and communicate via IPC chanels/sockets. This makes it easier to write code that can scale without limit. For most use cases, I don't see much point of writing scalable code that you know only scales up to a certain point and then needs to be rewritten. Avoid using shared memory if you have an embarassingly parallel problem.
- tsimionescu 7y ago
  Approaches using IPC/sockets are significantly more complicated than shared-memory parallelism in most programming languages. Sockets at least are also an absurdly wasteful communication mechanism in low-concurrency situations, compared to direct shared memory access. If you have a simple REST web server, single-thread is simply not a realistic option. The next simplest thing is to do shared memory parallelism, which works perfectly for a few dozens to low hundreds of threads. That already covers a lot of scale for many realistic problems. Moving from that to a distributed system design is a significant jump in implementation complexity, and will likely increase per-request latency with most straight-forward implementations.
  - imtringued 7y ago
    In my experience it is very to easy get into situations where using only mutexes is impossible. As soon as you need a lock per object and access two objects then you have to make sure to only acquire one lock at a time. The end result is that you are effectively using the stack as a message queue that can only hold one element.
p0nce 7y ago
A typical mutex has essentially two very different costs depending on whether the lock is already taken by another thread: - Uncontended case + mutex: no syscall, fast path is basically the cost of the memory barrier. - Uncontended case + spinlock: no syscall, fast path is basically the cost of the memory barrier. Essentially same cost than a mutex, sometimes a tiny bit cheaper but _if your lock isn't contented in the first place it will be very hard to measure, since not being a bottleneck_. - Contended case + mutex: thread is waiting in the mutex list without taking CPU. Hyper-threading may also give hand immediately to another thread, perhaps lucky enough to run. The OS mutex may have a bit of capped spinning before waiting in the scheduler. - Contended case + spinlock: Anything goes. CPU gets consumed just for spinning. Wrong thread might get priority. If you are lucky you did put a HLT instruction to mitigate the complete disaster that spinlocks are, perhaps it even does something. Your consolation: no syscall or thread pausing... because they are spinning. tl;dr: spinlock are worse in the contended case and essentially the same performance in the uncontended case against your typical OS mutex. SPINLOCKS WON'T YIELD THE EXPECTED BENEFITS, USE REGULAR OS MUTEXES.
- ketzu 7y ago
  I believe the supposed beneficial case of blocking vs spinning can't be captured well by those categories, as it's "contended, but not for long" and "contended, but for longer". That's the reason for the "may have a bit of capped spinning before waiting in the scheduler".
  - p0nce 7y ago
    Honestly I'm not so sure about the case for spinning; in x264 source you can see CRITICAL_SECTION is tuned to have a spincount of 0. This is a very optimized, multi-threaded app. They didnt want any spinning. https://github.com/mirror/x264/blob/d4099dd4c722f52c4f3c14575d7d39eb8fadb97f/common/win32thread.c#L47 https://github.com/mirror/x264/blob/d4099dd4c722f52c4f3c1457... In my own attempts I've been unable to measure the impact of the spinlock count, and took spincount = 40 like in https://trac.webkit.org/browser/webkit/trunk/Source/WTF/wtf/Lock.cpp?rev=200444#L44 https://trac.webkit.org/browser/webkit/trunk/Source/WTF/wtf/... ...who also took measurement from elsewhere. The default is 4000 on Windows! I don't argue spinning isn't valuable ; what I say is that it's necessarily never the bottleneck (else your task size really is too small). After all, if you spend all your time in synchronization, that means you probably need to have bigger tasks, not more clever synchronization primitives.
RossBencina 7y ago
I'm curious what is going on with the "Idle Time" measurements. Does anyone have any theories? My guess is that if the thread gets descheduled inside the lock() spin loop (either by an explicit call to yield() or otherwise) then the "Four longest idle times" reflect the fact that all of the worker threads have remained descheduled for an extended period. But assuming that the threads have elevated priority (why would you use spinlocks on non-high-priority threads?) this seems implausible on an 8 core machine. I would be curious to know what the results are if isolcpus was used and the workers were explicitly assigned to those CPUs.
- atq2119 7y ago
  The whole "idle time" vs. "longest wait" distinction is suspect and it's surprising they don't go to more effort to justify it. What "longest wait" measures is (b_i - a_i) in: Time a_0 lock Time b_0 unlock Time a_1 lock Time b_1 unlock ... What "idle time" measures is (b_i - a_i) in: lock Time a_0 unlock lock Time b_0 Time a_1 unlock lock Time b_1 ... At least for the spinlock variants, "unlock" should be an extremely cheap operation (just a store for most variants), which means that those two sequences ought to be essentially identical in terms of timing: it ought to be possible to move the "Time a_i"s across the "unlock" operations with a timing impact less than a microsecond, i.e. the two sequences ought to have essentially the same timings. The fact that the timings are supposedly different on a millisecond scale is therefore quite suspicious. Perhaps the chosen clock ends up calling a syscall, which can end up in the scheduler on syscall return occasionally and throw off the measurements that way? Or just the fact that there's one extra syscall in the critical section sometimes causes other threads to make different yielding decisions which throws off the scheduling? More generally, it would have been great to see a deeper investigation into scheduling behavior, which is possible on Linux using the tracing infrastructure and visualizing with different tools like Hotspot. Getting a worst-case delay of ~1.5ms with a naive ticket_spinlock that can yield is really not surprising, to be honest. All it takes is for patterns like: 1. 3 threads pull their tickets in order. 2. The middle thread yields and something else is chosen to run by the scheduler, or perhaps the scheduler decides not to run anything for a short while on the off-chance that something else becomes runnable, which is a fair choice because after all, you yielded. 3. The last thread is then blocked by the middle thread. It just boils down to the fact that "yield" is a bad primitive. You should fall back to futex-based synchronization instead so that the kernel has a better idea of what you're trying to do. The article comes to the same conclusion anyway, in the form of "just use std::mutex".
tonetheman 7y ago
This is a GREAT post. Super technical. Lots of stuff to learn.
ezoe 7y ago
My take on this article is it doesn't worth implementing your own spinlock. The OS can take advantage of their implementation details while you can't portably implement it. The OS implementation changes in the future or varies. Even if you use _mm_pause() to let CPU know it's doing spinlock, for the eye of the OS, it still looks like a busy thread, it can't be distinguished from non-spinlock computation heavy thread.

331 points by bazzargh 7y ago

Why isn't the conclusion to just use the mutex at least on Linux? It seems to have both consistently low latency and great throughput. What else can you get from the spinlock?

jiveturkey 7y ago
> What these benchmarks have in common is that they measure code in which there is nothing else to do except fight over the lock. In that environment the only thing that makes sense is to use a spinlock. Because if you go to sleep, all that will happen is that some other thread will wake up that will fight over the same lock. That said, his conclusion is in fact just as you stated, if you read in between the lines. (This paper is really about the scheduler, so it's not exactly that conclusion.)
- trasz 7y ago
  And that’s precisely what most operating systems other than Linux do: use adaptive mutexes as the default mechanism, not spinlocks.
  - gpderetta 7y ago
    Pthread_mutex on linux is also an adaptive mutex, although the spinning count might not be optimal.
- banachtarski 7y ago
  You don't even need to read in between the lines. He literally states that in his conclusion...
7532yahoogmail 7y ago
No that was the conclusion: use mutexes
banachtarski 7y ago
> Why isn't the conclusion to just ... Sigh. From the article itself: > I hope to have convinced you to avoid spinlocks, even for very short sections. Spinlocks are only a benefit if you really really care about the fast path and are certain that the lock will essentially always be free to take. On my computer the fast path on a spinlock is roughly 7ns and on a mutex it’s roughly 14ns, so both of those numbers are very fast. But when spinlocks go bad, the scheduler can be really confused, at least on Linux.
- pedrocr 7y ago
  I did read it till the end but missed that bit about the fast path somehow. I struggle to see a case where you care enough about those 7ns but the Windows scheduler was a different story.

pixel_fcker 7y ago

I think the answer, as always, is to measure on your own workloads. I’ve seen real-world production code get significant speed ups by switching to spinlocks from mutexes. Very interesting post though. I’ve never considered the idle latency before.

pmoriarty 7y ago

Can someone knowledgable explain what a mutex is, what a spinlock is, and the difference between mutexes and spinlocks?

ptr 7y ago
A spinlock is a kind of mutex (“mutual exclusion”) where in a condition is checked as fast as possible in a loop. This is useful when the expected wait times are short as you don’t have to pay the context switch penalty. Typically done when you have real parallelism with multiple CPUs/cores. A mutex can also refer to a particular group of “mutual exclusion” methods where in the current process/thread is suspended until the condition is true. Hope this helps.
- jonny383 7y ago
  Additional note that mutual exclusion is a concept that pops up a lot when dealing with concurrent processing (think threads, multi-process type architectures). Typically mutex / spinlock is implemented to reduce and prevent race conditions
  - edoceo 7y ago
    One can see this at a higher level in Golang, where a gofunc are reading/updating a map - and run with -race then it shows where you have to use a Mutex call to lock that Map for the access, R or RW. Higher level but pretty simple to see.
    - zozbot234 7y ago
      One can see this at an even higher level in Rust, where you don't even need a "race checker" to avoid data races in safe code - the compiler will force the use of patterns like Mutex<> or Rwlock<> (or others) for stuff that might be accessed concurrently in ways that would otherwise break mutual exclusion.
      - jonny383 7y ago

PaulDavisThe1st 7y ago

(reposting my comment from the original) There’s some potentially misleading information here. Background: I’ve spent the last 20+ years writing low-latency realtime audio applications, technically cross-platform but focused on Linux. If you care about low latency on any general purpose OS, you need to use a realtime scheduling policy. The default scheduling on these OS’s is intended to maximise some combination of bandwidth and/or fairness. Low latency requires ditching both of those in favor of limiting the maximum scheduling delay of a thread that is otherwise ready to run. Measuring how long synchronization primitives take without SCHED_FIFO is illustrative, but only of why, if you care about scheduling latency, you need SCHED_FIFO. There are several alternative schedulers for Linux – none of them remove the need for SCHED_FIFO if latency is important. It is absolutely not the case that using SCHED_FIFO automatically starves non-SCHED_FIFO threads. Scheduling policy is set per-thread, and SCHED_FIFO will only cause issues if the threads that use it really do “burn the CPU” (e.g. by using spinlocks). If you combine SCHED_FIFO with spinlocks you need to be absolutely certain that the locks have low contention and/or are held for extremely short periods (preferably just a few instructions). If you use mutexes (which ultimately devolve to futexes at the kernel level), the kernel will take care of you a little better, unless your SCHED_FIFO thread doesn’t block – if it doesn’t do that, that’s entirely on you. Blocking means making some sort of system call that will cause the scheduler to put the thread to sleep – could be a wait on a futex, waiting for data, or an explicit sleep. In particular, this: “This was known for a while simply because audio can stutter on Linux when all cores are busy (which doesn’t happen on Windows)” is NOT true. Linux actually has better audio performance than Windows or macOS, but only if the app developer understands a few basic principles. One of them is using SCHED_FIFO appropriately. Pro-audio/music creation scheduling is MUCH more demanding than video, and a bit more demanding than games. Linux handles this stuff just fine – it just gives you enough rope to shoot yourself in the foot if you don’t fully understand what you’re doing.

segfaultbuserr 7y ago
For the same reason, by default, PulseAudio uses rtkit to escalate its privileges and set its scheduler policy to SCHED_FIFO (then drop the privilege). Many people don't understand it and see it as another example of how Lennart's software is taking over the world (especially when you use a distribution like Arch that didn't already have rtkil configured for you), but it's essential for good audio latency (but the audio player needs SCHED_FIFO as well, there's nothing to help if the player itself is locking up). > SCHEDULING > high-priority= Renice the daemon after startup to become a high-priority process. This a good idea if you experience drop-outs during playback. However, this is a certain security issue, since it works when called SUID root only, or RLIMIT_NICE is used. root is dropped immediately after gaining the nice level on startup, thus it is presumably safe. See pulseaudio(1) for more information. > Takes a boolean argument, defaults to yes. The --high-priority command line option takes precedence. > realtime-scheduling= Try to acquire SCHED_FIFO scheduling for the IO threads. The same security concerns as mentioned above apply. However, if PA enters an endless loop, realtime scheduling causes a system lockup. Thus, realtime scheduling should only be enabled on trusted machines for now. Please note that only the IO threads of PulseAudio are made real-time. The controlling thread is left a normally scheduled thread. Thus enabling the high-priority option is orthogonal. See pulseaudio(1) for more information. > Takes a boolean argument, defaults to yes. The --realtime command line option takes precedence.

devit 7y ago

The claim that "the Linux scheduler is bad" seems wrong. First of all, a program that calls sched_yield() for synchronization is simply broken, since doing so can cause 100% CPU usage (if the other thread is stopped at an unfortunate place), so the only correct method among the ones benchmarked is std::mutex. When using std::mutex (the only correct approach), Linux and Windows both seem to have similar average performance, but Windows has 10x latency, so Linux is better.

newnewpdro 7y ago
sched_yield() isn't being used for synchronization, it's to yield the calling thread before its timeslice is exhausted because it's potentially preventing the lock-holder thread from getting scheduled to run and releasing it. Spinlocks assume the critical section is fast and non-blocking, so when the spinning lasts longer than expected, throwing in a yield can help by handing some CPU time to something else. The lock-holder might be getting scheduled on the same CPU and waiting for this thread to yield, or there might just be excessive threads runnable right now and burning cycles pointlessly spinning isn't helping get the lock-holder to run and release the lock any sooner. In a situation where you have exactly as many threads as there are CPUs, and they've been assigned their own respective CPUs, and there's nothing else running on the system, I wouldn't expect the yield to help. But that ideal isn't how things generally look in practice.
- gpderetta 7y ago
  If a spin lock ends up in a call to sched_yeld, it means that it is already outside its intended use case (uncontrnded or nearly uncontented), so it is a bit pointless to optimize this path or expect any sane scheduling behaviour. If contention is probable it is better to fall back on a futex after a few[1] busy spins. This is what pthread_mutex (and pretty much every decent OS provided mutex does) on glibc by default. [1] how much is 'few' of course is often application dependent.
- devit 7y ago
  You must not use sched_yield() and also must not spin indefinitely. Instead, one should optionally spin for up to a constant number of iterations and then call sys_futex.

mehrdadn 7y ago

Windows has process and thread priorities, including so-called "real-time" ones... but there seem to be no mentions of them in the article, as opposed to Linux. Why?

amluto 7y ago

I’m not convinced the measurements are really meaningful in this article. The author seems to be running a bunch of threads, measuring the time from when one thread starts unlocking the lock to when another thread gets it and calling this “idle”. I can’t find any mention of how many threads there are, how many CPUs, or what else the system is doing. So this is measuring a mess of a few things: For mutexes (assuming all the implementations actually make syscalls for unlocking), this has something to do with how long it takes for the scheduler to activate the waiter and run it, plus how long the scheduler waits because the system is doing something else or it wants to try to avoid bouncing a task between CPUs. For anything that does not involve the kernel in unlocking, this is really just a measurement of the pauses in execution of long-running threads that continuously hog the CPU. If the thread is also calling sched_yield(), the results are erratic, since sched_yield() more or less means “I don’t want to run now, but I’m not actually waiting for anything visible to the scheduler and, um, run me again soon maybe?” This is almost always the wrong solution. Other than that, this test has essentially nothing to do with which spinlock is in use, unless the spinlock itself wastes time failing to figure out that it’s ready. From old memory, the Windows scheduler is (was?) mostly based on per-thread priorities, highest priority wins, where the priorities are occasionally automatically adjusted. So, if you set a high-ish priority, you get to hog the CPU. In contrast, Linux tries quite hard not to let normal (non-RT) threads hog the CPU, so a thread that effectively runs continuously measuring pauses will detect significant pauses in which Linux decides that the rest of the system deserves to run too.

RossBencina 7y ago
I agree that the post needs to clarify the number of threads, what thread priorities were assigned, and what measures were taken to associate the threads with logical CPUs (affinities). I think your characterization of sched_yield() is a bit off. The man page is clear: "sched_yield() causes the calling thread to relinquish the CPU. The thread is moved to the end of the queue for its static priority and a new thread gets to run." and "If the calling thread is the only thread in the highest priority list at that time, it will continue to run after a call to sched_yield()." In particular, it does not say "I’m not actually waiting for anything visible to the scheduler and, um, run me again soon maybe?". So assuming that the threads are running at some relatively high priority, I'm struggling to see how delays on the order of 60ms could arise. EDIT: reading further: "sched_yield() is intended for use with real-time scheduling policies (i.e., SCHED_FIFO or SCHED_RR). Use of sched_yield() with nondeterministic scheduling policies such as SCHED_OTHER is unspecified and very likely means your application design is broken." So maybe that's it. [1] http://man7.org/linux/man-pages/man2/sched_yield.2.html http://man7.org/linux/man-pages/man2/sched_yield.2.html

newnewpdro 7y ago

I would like to see the measurements when the threads are explicitly assigned to their respective CPUs. It surprised me to not see even a mention of CPU affinity.

dpc_pw 7y ago
For any sort of benchmarking like that you have to take care of affinities and cpufreq governor at minimum.
- newnewpdro 7y ago
  yep, I was assuming they at least didn't have any frequency scaling or powersave governor junk going on but you're right - it wasn't even mentioned so...

cryptica 7y ago

IMO mutexes, semaphores, spinlocks should be used only in special cases (e.g. games or other high perf logic where you need to maximize performance by a fixed percentage) because they are anti-patterns for scalability. They only help to scale up to a point after which all the threads either spend all their time waiting for each other to release the locks or they can never acquire the locks because the demand for that shared memory is too high. There are exceptions for example if you have unlimited reader threads/processes compared to a fixed number of writer threads/processes but even in those cases, I feel that shared memory locks add invisible bottlenecks to scalability as the code evolves over time. For most of my use cases, I prefer to keep processes/threads parallel and communicate via IPC chanels/sockets. This makes it easier to write code that can scale without limit. For most use cases, I don't see much point of writing scalable code that you know only scales up to a certain point and then needs to be rewritten. Avoid using shared memory if you have an embarassingly parallel problem.

tsimionescu 7y ago
Approaches using IPC/sockets are significantly more complicated than shared-memory parallelism in most programming languages. Sockets at least are also an absurdly wasteful communication mechanism in low-concurrency situations, compared to direct shared memory access. If you have a simple REST web server, single-thread is simply not a realistic option. The next simplest thing is to do shared memory parallelism, which works perfectly for a few dozens to low hundreds of threads. That already covers a lot of scale for many realistic problems. Moving from that to a distributed system design is a significant jump in implementation complexity, and will likely increase per-request latency with most straight-forward implementations.
- imtringued 7y ago
  In my experience it is very to easy get into situations where using only mutexes is impossible. As soon as you need a lock per object and access two objects then you have to make sure to only acquire one lock at a time. The end result is that you are effectively using the stack as a message queue that can only hold one element.

p0nce 7y ago

A typical mutex has essentially two very different costs depending on whether the lock is already taken by another thread: - Uncontended case + mutex: no syscall, fast path is basically the cost of the memory barrier. - Uncontended case + spinlock: no syscall, fast path is basically the cost of the memory barrier. Essentially same cost than a mutex, sometimes a tiny bit cheaper but _if your lock isn't contented in the first place it will be very hard to measure, since not being a bottleneck_. - Contended case + mutex: thread is waiting in the mutex list without taking CPU. Hyper-threading may also give hand immediately to another thread, perhaps lucky enough to run. The OS mutex may have a bit of capped spinning before waiting in the scheduler. - Contended case + spinlock: Anything goes. CPU gets consumed just for spinning. Wrong thread might get priority. If you are lucky you did put a HLT instruction to mitigate the complete disaster that spinlocks are, perhaps it even does something. Your consolation: no syscall or thread pausing... because they are spinning. tl;dr: spinlock are worse in the contended case and essentially the same performance in the uncontended case against your typical OS mutex. SPINLOCKS WON'T YIELD THE EXPECTED BENEFITS, USE REGULAR OS MUTEXES.

ketzu 7y ago
I believe the supposed beneficial case of blocking vs spinning can't be captured well by those categories, as it's "contended, but not for long" and "contended, but for longer". That's the reason for the "may have a bit of capped spinning before waiting in the scheduler".
- p0nce 7y ago
  Honestly I'm not so sure about the case for spinning; in x264 source you can see CRITICAL_SECTION is tuned to have a spincount of 0. This is a very optimized, multi-threaded app. They didnt want any spinning. https://github.com/mirror/x264/blob/d4099dd4c722f52c4f3c14575d7d39eb8fadb97f/common/win32thread.c#L47 https://github.com/mirror/x264/blob/d4099dd4c722f52c4f3c1457... In my own attempts I've been unable to measure the impact of the spinlock count, and took spincount = 40 like in https://trac.webkit.org/browser/webkit/trunk/Source/WTF/wtf/Lock.cpp?rev=200444#L44 https://trac.webkit.org/browser/webkit/trunk/Source/WTF/wtf/... ...who also took measurement from elsewhere. The default is 4000 on Windows! I don't argue spinning isn't valuable ; what I say is that it's necessarily never the bottleneck (else your task size really is too small). After all, if you spend all your time in synchronization, that means you probably need to have bigger tasks, not more clever synchronization primitives.

RossBencina 7y ago

I'm curious what is going on with the "Idle Time" measurements. Does anyone have any theories? My guess is that if the thread gets descheduled inside the lock() spin loop (either by an explicit call to yield() or otherwise) then the "Four longest idle times" reflect the fact that all of the worker threads have remained descheduled for an extended period. But assuming that the threads have elevated priority (why would you use spinlocks on non-high-priority threads?) this seems implausible on an 8 core machine. I would be curious to know what the results are if isolcpus was used and the workers were explicitly assigned to those CPUs.

atq2119 7y ago
The whole "idle time" vs. "longest wait" distinction is suspect and it's surprising they don't go to more effort to justify it. What "longest wait" measures is (b_i - a_i) in: Time a_0 lock Time b_0 unlock Time a_1 lock Time b_1 unlock ... What "idle time" measures is (b_i - a_i) in: lock Time a_0 unlock lock Time b_0 Time a_1 unlock lock Time b_1 ... At least for the spinlock variants, "unlock" should be an extremely cheap operation (just a store for most variants), which means that those two sequences ought to be essentially identical in terms of timing: it ought to be possible to move the "Time a_i"s across the "unlock" operations with a timing impact less than a microsecond, i.e. the two sequences ought to have essentially the same timings. The fact that the timings are supposedly different on a millisecond scale is therefore quite suspicious. Perhaps the chosen clock ends up calling a syscall, which can end up in the scheduler on syscall return occasionally and throw off the measurements that way? Or just the fact that there's one extra syscall in the critical section sometimes causes other threads to make different yielding decisions which throws off the scheduling? More generally, it would have been great to see a deeper investigation into scheduling behavior, which is possible on Linux using the tracing infrastructure and visualizing with different tools like Hotspot. Getting a worst-case delay of ~1.5ms with a naive ticket_spinlock that can yield is really not surprising, to be honest. All it takes is for patterns like: 1. 3 threads pull their tickets in order. 2. The middle thread yields and something else is chosen to run by the scheduler, or perhaps the scheduler decides not to run anything for a short while on the off-chance that something else becomes runnable, which is a fair choice because after all, you yielded. 3. The last thread is then blocked by the middle thread. It just boils down to the fact that "yield" is a bad primitive. You should fall back to futex-based synchronization instead so that the kernel has a better idea of what you're trying to do. The article comes to the same conclusion anyway, in the form of "just use std::mutex".

tonetheman 7y ago

This is a GREAT post. Super technical. Lots of stuff to learn.

ezoe 7y ago

My take on this article is it doesn't worth implementing your own spinlock. The OS can take advantage of their implementation details while you can't portably implement it. The OS implementation changes in the future or varies. Even if you use _mm_pause() to let CPU know it's doing spinlock, for the eye of the OS, it still looks like a busy thread, it can't be distinguished from non-spinlock computation heavy thread.