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: <1189683320.21778.213.camel@twins>
Date:	Thu, 13 Sep 2007 13:35:20 +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 00:17 +0200, Roman Zippel wrote:

> The rest of the math is indeed different - it's simply missing. What is 
> there is IMO not really adequate. I guess you will see the differences, 
> once you test a bit more with different nice levels.

The rounding error we now still have is accumulative over the long time
but has no real effect. The only effect is that a nice level would be a
little different that it would have been had the division been perfect,
not dissimilar to having a small error in the divisor series to being
with. (note that in order to see this little fuzz you need amazingly
high context switch rates)

We've measured the effect with the strongest nice levels -20 and 19, a
normal loop against two yield loops (this generated 700.000 context
switches per second), and the effect is <1%. Not something worth fixing
IMHO (unless it comes for free). 

At that high switching rates the overhead of scheduling itself and
caching causes more skew than this - the small error is totally swamped
by the time lost scheduling.

>  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).

I solved the wrap around problem in cfs-devel, and from that base I
_could_ probably maintain the average without overflow problems, but
have yet to try.

>  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.

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