lkml.org 
[lkml]   [2021]   [Oct]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2
On Tue, 26 Oct 2021 18:31:21 -0700
Kalesh Singh <kaleshsingh@google.com> wrote:

> And IIUC max_div is an arbitrary value we decide on that's <= 2^shift?
> Is there a rule of thumb for choosing this?

The way I came up with the max was to figure out at what point is it no
longer guaranteed to be accurate. That is, what number can make the
mult/shift no longer match the division.

If we have some number div that is not a power of two. At some point:

(X * mult) >> shift != X / div

Now I simply picked

max = 1 << shift / (mult * div - (1 << shift))

Because that will always be within the precision of the actual number.

But I believe we can make max bigger, but because that deals with
truncation, it's not simple math.

That is, the above X / div is truncated and not the real number.

I'm sure there's an algorithm somewhere that can give as the real max.

-- Steve

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