One caveat is that calling sched_yield is a fantastic throughput optimization for the spinning portion of an adaptive mutex. If you have parallel code that sporadically contends for short critical sections then my data has always said this:
- something like a futex lock is optimal
- you want barging, not fairness
- spinning the CPU is a t questionable idea even if you do it for a short time. The pause instruction does something like jack and shit. Busy waiting of any kind seems great for microbenchmarks sometimes but it’s pretty bad for anything complex.
- spinning 40 times while calling sched_yield prior to futex_wait (or whatever) appears optimal on many schedulers and benchmarks. It’s hard to tell why. Best I can tell it’s because in the large parallel apps I’ve worked on and benchmarked, there are often threads that are ready to do some useful work right now, so yielding from a thread that can’t get a lock to one of those is a system throughput optimization. If there are no such threads then it’s a bit like spinning the CPU.
The 40 yields thing has a funny story for me. I learned of it from a comment in the JikesRVM code that was more than a decade old claiming it was optimal on their custom scheduler on a 12 core POWER box running AIX. The benchmark cited was something I’d never heard of. When I rewrote how JikesRVM did thread scheduling, I was sure that this would need tuning. Nope. It’s optimal on Linux and Darwin on x86 on basically any Java benchmark that has lock contention. I later implemented the same heuristic in WebKit’s locks. It’s still optimal.
To be sure, there is a broad plateau of goodness around 40. Like, 50 is about as good. But if you go order of magnitude in either direction, performance tanks. I’m superstitious so I’ve stayed with exactly 40 whenever I have to write this code.
I wrote a lot more about this stuff once: https://webkit.org/blog/6161/locking-in-webkit/
It would be interesting to see a distribution of wait time per lock for different locks. If such a two step approach performs well, a hypothesis might be that there are three kinds of locks:
- mostly uncontended: lock succeeds without spinning
- held for exceptionally short amounts of time: lock usually gets released again before waiting thread on different CPU stops spinning. Wait time is lower than the time it takes to yield to the scheduler and/or reschedule.
- held for a really long time: wait time is much longer than scheduling another thread and re-scheduling the initial one.
And what you are saying seems to indicate that optimizing for the first and second one is worth it because the overhead is negligible for the third type, that is, there are few locks that are held for an amount of time so that spinning adds noticable overhead.
https://docs.microsoft.com/en-us/windows/win32/sync/critical...
The paragraph about InitializeCriticalSectionAndSpinCount and SetCriticalSectionSpinCount describe the behavior. IIRC, the default spin count used to be pretty high (1000 loops or so). Not sure if that was changed.
I’ve tested this over the course of a decade on multiple Linuxes, multiple Darwins, multiple x86 flavors (Intel, amd, and lots of core counts and topologies), POWER, and various arms, and on many large benchmarks in two very different languages (Java and C/C++). In Java I tested in in two very different VMs (JikesRVM and FijiVM). I think the key is that a typical benchmark for me is >million lines of code with very heterogenous and chaotic locking behavior stemming from the fact that there are hundreds (at least) of different hot critical sections of varying lengths and subtle relationships between them. So you get a law of large numbers or maybe wisdom of the masses kind of “averaging” of differences between CPUs and schedulers.
I’d love to see some contradictory data on similarly big stuff. But if you’re just saying that some benchmark that had a very homogenous lock behavior (like ~one hot critical section in the code that always runs for a predictable amount of time and never blocks on weird OS stuff) experiences wild differences between CPUs and schedulers then sure. But that just means there are no ideal answers for that scenario, not that there aren’t ideal answers for anyone.
- you cannot implement a functioning spin lock in user space (for all practical intents and purposes and if you don't resort to extreme measures and talking modern general purpose operating systems)
Only then it makes sense tu use spin locks.
In general you should expect userspace code to be scheduled out at any time and use locking primitives that the kernel knows about.
Even if your thread won't be scheduled off the core I don't know if you might still have irqs stealing time during the critical section.
> Lots of users, all of which are basically buggy-by-definition, and all you can do is a bad half-arsed job of trying to make it "kind of work".
> Reality is messy.
> Linus
I don’t buy claims about lock behavior based on microbenchmarks. Microbenchmarks have wildly different behavior from one another so it stands to reason that they have wildly different behavior from real code.
Linus’s excuse is that if you use a real lock then shit is good. That’s a pretty good excuse IMO.
[0]: https://nitter.net/dotstdy/status/1213582199615901696#m
There are runnable threads that are not being run. It would be nice to know why.
Tell a person their code is wrong and you may have saved them from one mistake. Tell them why their code is wrong and you will save them from a dozen.
Perhaps Linus' concern is that sched_yield doesn't guarantee any particular behavior, it just happens to be implemented that way now.
> There are runnable threads that are not being run. It would be nice to know why.
More extreme. It only applies to the same core, more or less. The original benchmarks are on a one-node CPU, after all.
1. Scheduler looks through all the processes on the system, decides A is the one that should run right now
2. A decides it doesn't want to run, calls yield.
3. Scheduler looks again, thinks A is still the right one to run, and runs it again.
That is, in most cases, if the scheduler thought there was a better process to run, it would already have been running.
He states (paraphrasing) - it's undefined because there's no real way (unless in a realtime scheduler) to find what to yield to without instigating complexity.
The search itself is the quest that the kernel would rather not do at all. Step 3 is undefined and thus sched_yield itself is undefined.
So let's look over our cores:
6 of them are churning through processes that do nothing but call sched_yield. Nothing has been waiting to run for more than 3 microseconds.
2 of them are doing real work, and the benchmark threads that happen to be on the same core have been waiting to run for most of a millisecond.
If you're stuck, then B is one of the processes that has been waiting.
So the obvious change would be to move threads around in sched_yield. Then B will get scheduled within microseconds.
What's your CPU use right now? I bet it's less than 200%. Or will be if you exclude your web browser.
The typical background process is active far less than one percent of the time.
Right, but you would expect the "switch to another thread" function to eventually pick the one that's sitting there with a growing and growing time since it last got a chance to run.
It would be easy to guarantee that if any thread has been waiting for at least x amount of time, then any context switch without long-waiting local threads will pick that thread. (If it's on the same NUMA node, at least.) But in the actual implementation that time can build up to a huge amount with no effect, even as thousands of yield calls go by.
> Especially not if that process is soft locked to a different core.
Yeah, that's the problem, it's getting locked to a core even though other cores are desperate for threads to run.
Pipes have a small buffer. Once it's full, the caller will block, and the scheduler will know precisely what to schedule to unblock it.
What about just temporarily increasing the process' nice value?
That should be simple to do, and the scheduler already knows how to yield to processes with lower nice values.
Tell the kernel why you want to yield CPU. Work with the kernel, not against it. Do you want to yield because you genuinely want to wait until some future point in time? Use sleep. Is it because you're waiting for some I/O? Use poll or its variants. Is it because you're waiting for a signal from another thread? Use mutexes, condition variables, etc. that call futex under the hood.
Think of it as a speculative optimization on top of busy waiting, not as a way to control the scheduler.
Why don't you want to call sleep?
The scheduler itself uses fixed time interrupts for its basic functions, so "sleep(fixed_time_interval)" is what you will get in the end anyway on a preemptive system.
https://www.realworldtech.com/forum/?threadid=189711&curpost...
Followed by Linus response to Malte:
https://www.realworldtech.com/forum/?threadid=189711&curpost...
The long and the short of it:
- It's nearly impossible to make meaningful benchmarks for this because reality will almost always be different and more complicated
- Calling sched_yield() is almost always a mistake
- Any scheduling optimization is probably a waste of time because either your running env will change, or the kernel will change, or someone else's optimizations will clash with yours.
- Even with decades of research into locking, everyone (including the experts) continually gets it wrong.
- If you're not running a specialized embedded setup where you control all of the running processes and other such variables, just use sleep locks and call it a day.