8 ms·
It's important to read Malte's response to Linus: https://www.realworldtech.com/forum/?threadid=189711&curpostid=189747 https://www.realworldtech.com/forum/?th
by kstenerud 7y ago
It's important to read Malte's response to Linus:
https://www.realworldtech.com/forum/?threadid=189711&curpostid=189747 https://www.realworldtech.com/forum/?threadid=189711&curpost...
Followed by Linus response to Malte:
https://www.realworldtech.com/forum/?threadid=189711&curpostid=189752 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.
- sillysaurusx 7y agoWhy is calling sched_yield() a mistake? What's the correct way to yield CPU without calling sleep?
- colonwqbang 7y agoIt's explained in the linked post. Why don't you want to call sleep?
- gpderetta 7y agoBeacuse it would act as as an even worse sched yield.
- temac 7y agoNot in every cases, but both are certainly suboptimal compared to a diretected wake up.
- deleted 7y ago[deleted]
- mritun 7y agoCalling sleep(1) instead of thread yield is faster - see the twitter thread for a proof.
- de_watcher 7y agoStill worse: it's a confusing code, and it's also confusing that it's faster.
- colonwqbang 7y agoI guess I can't really see the use case here. If you want to sleep, it's usually because you're waiting for something: file descriptor, semaphore/mutex, or a certain amount of time to pass. If none of these conditions apply, can't you just continue to run and let the scheduler do its work? (maybe with an appropriate nice setting if you are doing "less important" work). 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.
- gpderetta 7y agoFutex wait, or any other blocking syscall.
- dante_dev 7y agoyou may want to read Linus's answer about it https://www.realworldtech.com/forum/?threadid=189711&curpostid=189752 https://www.realworldtech.com/forum/?threadid=189711&curpost...
- atq2119 7y agoYou really should just read the linked article, but the tl;dr is that sched_yield() does not convey intent (except in narrow realtime scenarios that you should not be using in the first place). 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.
- mannykannot 7y agoIf a thread can do no more for the moment, then either it is finished, or it is waiting for something to happen. In the latter case, the best thing is to be woken on that event, and the next best is to poll for it. Sleep is only the best solution when that event is literally the passage of time.
- pizlonator 7y agosched_yield means “yield to any thread if it’s easy to do so or do nothing”. That meaning fits the requirements of some algorithms, particularly if you call it a finite number of times before doing something more drastic like a blocking syscall (like futex wait, lock acquisition, whatever) that will block until the condition you’re waiting for is fulfilled. Think of it as a speculative optimization on top of busy waiting, not as a way to control the scheduler.
- weinzierl 7y agoThe most important point is: - 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)
- cbsmith 7y agoDepends on what you mean by "functioning". You can make one that functions in the sense that you can lock between concurrent threads. However, it's difficult to do right and even more difficult to do in a way that is performant (and the interface to the kernel is so ill defined for this, whatever efficient solution you come up with will likely prove to be far less efficient on other systems with just subtle alterations in the underlying kernel implementation.
- lmilcin 7y agoYou can, but it requires special architecture for the application. The cpuset can be used to disable scheduler use of the core and then you can pin application threads to cores, single thread per core. Only then it makes sense tu use spin locks.
- xakahnx 7y agoThis is still a disaster with hyperthreading where you can have two threads contending for a lock on the same physical core. 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.
- touisteur 7y agoCan't you isolate cores from irqs with irq affinities? I'd be more worried by SMM stealing CPU time (ugh... talk about sad stories of 'real-time' Linux...).
- GhettoMaestro 7y agoObviously you've never heard of DPDK.
- arendtio 7y agoI like the end: > 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
- dooglius 7y agosched_yield does seem like it should have a pretty obvious meaning: do whatever you would do if the preemption timer went off right now. Whether it's a good idea or not, I don't see why it's considered "undefined".
- gwd 7y agoI haven't read Linus' discussions, but often what happens when you take that approach is: 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.
- barkingcat 7y agoPlease read Linus' discussion. 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.
- dooglius 7y agoWell, the scheduler has the same problem when the preemption timer goes off, doesn't it?
- gwd 7y agoGGP had a simple solution: "yield is the same as a preemption tick". I was trying to briefly explain what usually happens when you define things that way. I'm not advocating one thing or another.
- jcranmer 7y agoThat is somewhat surprising to me. My idea of the canonical use case for yield is interprocess communication: process A sent a message to process B, and it wants to yield the remainder of its scheduling quantum to process B because process A has nothing left to do. Although maybe this use case is satisfied by something other than sched_yield.
- MegaDeKay 7y agoLinus is backed up by Josh Simmons on Twitter. He does some perf tracing and also tweaks Malte's "utterly terrible benchmark" to be "about twice as fast". https://twitter.com/dotstdy/status/1213578864842162176 https://twitter.com/dotstdy/status/1213578864842162176
- gok 7y agoThey're talking past each other. Malte is really saying that yield() does what he wants on Windows and BSD, and Linus is giving a bunch of excuses for why Linux doesn't work that way.
- muststopmyths 7y agoEXACTLY! I wish someone would just explain why the behavior is different. Does linux only sched_yield on the same NUMA node ? (Linus' reply seemed to imply that). Windows will not pin threads unless you set processor affinity, AFAIK, so maybe that's the difference. 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.
- wyldfire 7y ago> Does linux only sched_yield on the same NUMA node ? (Linus' reply seemed to imply that). Perhaps Linus' concern is that sched_yield doesn't guarantee any particular behavior, it just happens to be implemented that way now.
- Dylan16807 7y ago> Does linux only sched_yield on the same NUMA node ? > 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.
- pizlonator 7y agoI’m pretty sure that the Linux behavior makes sched_yield more suitable to the 40-yields optimization I use for locks. 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.
- 7y ago
- pizlonator 7y agoBasically Linus is right. 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/ https://webkit.org/blog/6161/locking-in-webkit/
- kitsuac 7y agoAll of these little details vary dramatically depending on the exact CPU and workload. I've developed a wide variety of scheduling strategies and have used neural networks to predict when a given strategy will be better. Scheduling is giant non deterministic mess with no ideal answers.
- pizlonator 7y agoOk but my data disagrees with you. Specifically: when apps get complex enough, the differences between CPUs and schedulers wash out in the chaos. 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.