linux-kernel - Re: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2

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: <20211027100659.00ec702b@gandalf.local.home>
Date:   Wed, 27 Oct 2021 10:06:59 -0400
From:   Steven Rostedt <rostedt@...dmis.org>
To:     Kalesh Singh <kaleshsingh@...gle.com>
Cc:     surenb@...gle.com, hridya@...gle.com, namhyung@...nel.org,
        kernel-team@...roid.com, Jonathan Corbet <corbet@....net>,
        Ingo Molnar <mingo@...hat.com>, Shuah Khan <shuah@...nel.org>,
        Masami Hiramatsu <mhiramat@...nel.org>,
        Tom Zanussi <zanussi@...nel.org>, linux-doc@...r.kernel.org,
        linux-kernel@...r.kernel.org, linux-kselftest@...r.kernel.org
Subject: Re: [PATCH v4 6/8] tracing/histogram: Optimize division by a power
 of 2

On Tue, 26 Oct 2021 21:04:29 -0700
Kalesh Singh <kaleshsingh@...gle.com> wrote:

> On Tue, Oct 26, 2021 at 8:16 PM Steven Rostedt <rostedt@...dmis.org> wrote:
> >
> > On Tue, 26 Oct 2021 22:21:23 -0400
> > Steven Rostedt <rostedt@...dmis.org> wrote:
> >  
> > > I'm sure there's an algorithm somewhere that can give as the real max.  
> >
> > You got me playing with this more ;-)
> >
> > OK, I added the rounding in the wrong place. I found that we can make
> > the max_div to be the same as the shift! The bigger the shift, the
> > bigger the max!  
> 
> Nice! :)
> >
> >         mult = (1 << shift) / div;
> >         max_div = (1 << shift)
> >
> > But the rounding needs to be with the mult / shift:
> >
> >         return (val * mult + ((1 << shift) - 1)) >> shift;
> >
> >
> > When val goes pass 1 << shift, then the error will be off by more than
> > one.  
> Did you mean, val should be such that when we do the (val * mult) we
> only get rounding errors less than (1 << shift)?

We get rounding errors when val is greater than (1 << shift) because then
it exposes the bits that are not shifted out.

> 
> I think we also need to flip the delta now since we round down initially:
> 
>     delta =  (1 << shift) - (mult * div)
> 

Actually, we don't need the delta at all. Just what I showed above.

Pick some arbitrary shift (let's say 20 as that seems to be commonly used,
and works for 32 bit as well) and then we figure out the multiplier.

	mult = (1 << shift) / div;


No delta needed. Our max is going to be 1 << shift, and then all we need is:

	if (val < (1 << shift))
		return (val * mult + ((1 << shift) - 1)) >> shift;
	else
		return val / div;

All we need to save to do the operation is the shift, the constant div and
the calculated constant mult.

-- Steve