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

[Steven Rostedt]

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

> On Tue, Oct 26, 2021 at 8:16 PM Steven Rostedt <rostedt@xxxxxxxxxxx> wrote:
> >
> > On Tue, 26 Oct 2021 22:21:23 -0400
> > Steven Rostedt <rostedt@xxxxxxxxxxx> 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