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

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]

Date:   Tue, 25 Jul 2017 10:17:05 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Linus Torvalds <torvalds@...ux-foundation.org>
Cc:     Andrew Morton <akpm@...ux-foundation.org>,
        Davidlohr Bueso <dave@...olabs.net>,
        Anshul Garg <aksgarg1989@...il.com>,
        Thomas Gleixner <tglx@...utronix.de>,
        Ingo Molnar <mingo@...nel.org>,
        Will Deacon <will.deacon@....com>,
        Joe Perches <joe@...ches.com>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute

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.