Re: [announce] CFS-devel, performance improvements

[Peter Zijlstra <a.p.zijlstra@chello.nl>]

[-- Attachment #1: Type: text/plain, Size: 2193 bytes --]

On Thu, 2007-09-13 at 14:14 +0200, Roman Zippel wrote:
> Hi,
> 
> On Thu, 13 Sep 2007, Peter Zijlstra wrote:
> 
> > >  There's a good reason 
> > > I put that much effort into maintaining a good, but still cheap average, 
> > > it's needed for a good task placement.
> > 
> > While I agree that having this average is nice, your particular
> > implementation has the problem that it quickly overflows u64 at which
> > point it becomes a huge problem (a CPU hog could basically lock up your
> > box when that happens).
> 
> If you look at the math, you'll see that I took the overflow into account, 
> I even expected it. If you see this effect in my implementation, it would 
> be a bug.

Ah, ok, I shall look to your patches in more detail, it was not obvious
from the formulae you posted.

> > >  There is of course more than one 
> > > way to implement this, so you'll have good chances to simply reimplement 
> > > it somewhat differently, but I'd be surprised if it would be something 
> > > completely different.
> > 
> > Currently we have 2 approximations in place:
> > 
> >   (leftmost + rightmost) / 2
> > 
> > and
> > 
> >   leftmost + period/2   (where period should match the span of the tree)
> > 
> > neither are perfect but they seem to work quite well.
> 
> You need more than two busy loops. 

I'm missing context here, are you referring to the nice level error or
the avg approximation?

> There's a reason I implemented a simple simulator first, so I could 
> actually study the scheduling behaviour of different load situations. That 
> doesn't protect from all surprises of course, but it gives me the 
> necessary confidence the scheduler will work reasonably even in weird 
> situations.

Right, I've build user-space simulators too, handy little things to play
with :-)

> From these tests I already know that your approximations only work with 
> rather simple loads.

I've not yet seen it go spectacularly wrong, although admittedly a
highly concurrent kbuild is the most complex task I let loose on it.

Could you perhaps be more specific on the circumstances it breaks down
and what the negative impact is?

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]