Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute

[Peter Zijlstra]

On Mon, Jul 24, 2017 at 10:35:56AM -0700, Linus Torvalds wrote:
> Ack. You have numbers, it's all good.

Thanks!

> Except I'd still want you to comment on why you cared and about which
> piece of your upcoming code this is going to matter for, ok?

I did an RFC here:

  https://lkml.kernel.org/r/20170719133940.uytsixvfgpmo3ane@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

And that is the patch that, through Thomas asking me about our sqrt(),
kick started these here patches.

There are a few more sites that would need similar treatment, but I've
not gone through the entire idle predictor yet.


Basically the observation is that, for performance, we seem to pick too
deep an idle state. The result is that the exit latency from this state
is higher than we'd like and performance hurts because of that.

The thinking is that if you estimate the average idle duration, you'll
be too long 50% of the time -- that is after all a fundamental part of
being the average. My proposed solution in that patch is computing the
value for which we're too long less than n%, in statistic speak:

  P(X < x)

Which is given by the CDF(x). In any case, assuming a normal
distribution, you end up with something like:

  avg - Z * stdev

Where Z depends on our cut-off and is basically a table lookup.  The
whole sqrt() comes from having to compute the stdev, as that is the
square root of the variance.