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/
This archive was generated by hypermail 2b29 : Sun Jan 23 2000 - 21:00:29 EST