lkml.org 
[lkml]   [2021]   [Oct]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2
On Tue, Oct 26, 2021 at 8:16 PM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Tue, 26 Oct 2021 22:21:23 -0400
> Steven Rostedt <rostedt@goodmis.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)?

I think we also need to flip the delta now since we round down initially:

delta = (1 << shift) - (mult * div)

Thanks,
Kalesh
>
> -- Steve

\
 
 \ /
  Last update: 2021-10-27 06:05    [W:0.074 / U:0.992 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site