Messages in this thread | | | From | "Sean Hunter" <> | Date | Sun, 23 Jan 2000 10:51:22 +0000 | Subject | Re: Linux scheduler, overscheduling performance, threads |
| |
On Sat, Jan 22, 2000 at 03:29:50AM -0600, Brian Hurt wrote: > > This discussion is rapidly degenerating into a "does too!" "does not!" > match. So let me turn the question around. Assume, for a moment, that a > patch for Linux existed which did two things: > 1) Ran signifigantly faster for large run queues- for example it switched > from the current O(n) algorithm to an O(log n) algorithm.
O(n) vs O(log n) is not the issue here. It is how much _overhead_ the algorithm has. Of course for some value of n a O(log n) algorithm will run faster than a O(n) algorithm. In this case its demonstrably true that n is higher than the numbers which are practical outside of benchmarks. Hence the slowdown for all real-world cases.
Also once you get to these states, the scheduler is not the main problem. Cache misses etc hurt you much more than the scheduler, as everyone has alredy said.
> 2) Ran slower than the current scheduling algorithm for short run > queues. > And the patch had no other effects on the kernel at large and was > otherwise well written, etc. > > Am I right in assuming that wether the patch would be accepted would > depend upon how much slower it made the common case? Obviously, if it > made the common case no slower, no one would mind putting it in the > kernel. On the other hand, if it made the common case a million times > slower, there is no way it'd ever get into the kernel, and rightfully so. > Where (roughly) inbetween is the breakpoint?
I don't speak for Linus, Alan et al, but I firmly believe that this patch is quite happily left on a patches website somewhere so that if you have very long runqueues and you think the scheduler is the problem, you can patch the kernel yourself.
One cycle more in the common case of the scheduler is one cycle too many.
Sean
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |