Messages in this thread | | | From | "Sean Hunter" <> | Date | Sat, 22 Jan 2000 11:18:58 +0000 | Subject | Re: Interesting analysis of linux kernel threading by IBM |
| |
On Fri, Jan 21, 2000 at 06:14:09PM +0100, Davide Libenzi wrote: > Hi James, > > Friday, January 21, 2000 3:02 PM > James A Simmons <jsimmons@acsu.buffalo.edu> wrote : > > I know the guy form IBM is watching this thread. I see alot of boo and hah > > about this patch. > > sure ? anyway everyone has its own opinions, but remember that You can > optimize the fast path and CPU cacheline > as You want, the algorithm still remain an O( N ) where N is the number of > processes in RQ.
Now, since we're talking Big-O notation, lets get some facts in with the theory. O(log n) or even O(1) is not a benefit if the overhead of the implementation is high and n is low. Low-overhead O(n^2) may be faster than high-overhead O(log n) for small values of n. Now, since n is the number of runnable processes (usually low in all the real-world non-benchmark cases people have stepped up with), and the scheduler is very sensitive to overhead (being called hundereds or even thousands of times a second), its very likely that low-overhead O(n) will beat even a pretty good O(log n) in the real world.
That's why everyone is talking about how the performance is "only x% worse in the case of less than y runnable tasks". In other words, only a little bit worse for all the real people doing real things, but a whole lot better at the specARSE3000 benchmark.
> > > Before we do anything the patch really needs to be > > tested and studied under all types of conditions. When we have really > > numbers then we can chose what to do with the patch. > > This is the thing we all want.
What I want is a scheduler that does _better_ not worse, at real loads, then we're on to a winner.
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/
| |