Re: [announce] CFS-devel, performance improvements

Peter Zijlstra
2007-09-13T12:44:40Z

[-- 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 --]