Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1695477

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

Show all headers | View raw

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@hirez.programming.kicks-ass.net

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.

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH 0/3] lib/int_sqrt: Fix, optimize and document Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
  [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
    Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Linus Torvalds <torvalds@linux-foundation.org> - 2017-07-24 19:40 +0200
      Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Peter Zijlstra <peterz@infradead.org> - 2017-07-25 10:20 +0200
        Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Linus Torvalds <torvalds@linux-foundation.org> - 2017-07-25 17:50 +0200
          Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Peter Zijlstra <peterz@infradead.org> - 2017-07-25 18:10 +0200
    Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Will Deacon <will.deacon@arm.com> - 2017-07-25 14:00 +0200
  [PATCH 1/3] lib/int_sqrt: Optimize small argument Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
  [PATCH 3/3] lib/int_sqrt: Adjust comments Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
  Re: [PATCH 0/3] lib/int_sqrt: Fix, optimize and document Joe Perches <joe@perches.com> - 2017-07-24 17:50 +0200

csiph-web