Messages in this thread | | | From | Davide Libenzi <> | Subject | Re: Interesting analysis of linux kernel threading by IBM | Date | Sun, 23 Jan 2000 15:50:32 +0100 |
| |
On Sat, 22 Jan 2000, Sean Hunter wrote: > 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. >
We can write this :
TS_old = Ko + O( N ) TS_new = Kn + O( log( N ) )
Where N is the RQ size.
Now the curve of TS_new( N ) goes down ( intersect ) the curve TS_old( N ) in a point that in the worse case I've measured is N = 8 ( I prefer always to report worse cases to avoid to be shooted ), but I've measured even 4 with a medium that I can think to be near to six.
> > > > > 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.
I'm working on a new version of my cluster scheduler that behave :
0 < N < Nx TS( T ) = TS_old( T )
Nx <= N < INF TS( T ) = TS_new( T )
I don't know if I'll succed but I'll try.
Davide.
-- All this stuff is IMVHO
- 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/
| |