linux-kernel - Re: [announce] CFS-devel, performance improvements

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1189687469.21778.229.camel@twins>
Date:	Thu, 13 Sep 2007 14:44:28 +0200
From:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
To:	Roman Zippel <zippel@...ux-m68k.org>
Cc:	Ingo Molnar <mingo@...e.hu>, linux-kernel@...r.kernel.org,
	Mike Galbraith <efault@....de>
Subject: Re: [announce] CFS-devel, performance improvements

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?

Download attachment "signature.asc" of type "application/pgp-signature" (190 bytes)