All of lore.kernel.org
 help / color / mirror / Atom feed
From: Kalesh Singh <kaleshsingh@google.com>
To: Steven Rostedt <rostedt@goodmis.org>
Cc: surenb@google.com, hridya@google.com, namhyung@kernel.org,
	kernel-team@android.com, Jonathan Corbet <corbet@lwn.net>,
	Ingo Molnar <mingo@redhat.com>, Shuah Khan <shuah@kernel.org>,
	Masami Hiramatsu <mhiramat@kernel.org>,
	Tom Zanussi <zanussi@kernel.org>,
	linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
	linux-kselftest@vger.kernel.org
Subject: Re: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2
Date: Tue, 26 Oct 2021 21:04:29 -0700	[thread overview]
Message-ID: <CAC_TJveyKhZ3jyTZ33jbxSKTxxJ1WG+NUUUbf11pJ8Gqk7UeaQ@mail.gmail.com> (raw)
In-Reply-To: <20211026231557.1eedad9b@rorschach.local.home>

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

  reply	other threads:[~2021-10-27  4:04 UTC|newest]

Thread overview: 44+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-10-25 20:08 [PATCH v4 0/8] tracing: Extend histogram triggers expression parsing Kalesh Singh
2021-10-25 20:08 ` [PATCH v4 1/8] tracing: Add support for creating hist trigger variables from literal Kalesh Singh
2021-10-25 20:08 ` [PATCH v4 2/8] tracing: Add division and multiplication support for hist triggers Kalesh Singh
2021-10-25 20:08 ` [PATCH v4 3/8] tracing: Fix operator precedence for hist triggers expression Kalesh Singh
2021-10-25 20:08 ` [PATCH v4 4/8] tracing/histogram: Simplify handling of .sym-offset in expressions Kalesh Singh
2021-10-25 20:08 ` [PATCH v4 5/8] tracing/histogram: Covert expr to const if both operands are constants Kalesh Singh
2021-10-25 20:08 ` [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2 Kalesh Singh
2021-10-26 19:14   ` Steven Rostedt
2021-10-26 23:39     ` Kalesh Singh
2021-10-27  0:18       ` Steven Rostedt
2021-10-27  1:09         ` Kalesh Singh
2021-10-27  1:15           ` Steven Rostedt
2021-10-27  1:31             ` Kalesh Singh
2021-10-27  2:21               ` Steven Rostedt
2021-10-27  3:15                 ` Steven Rostedt
2021-10-27  4:04                   ` Kalesh Singh [this message]
2021-10-27 14:06                     ` Steven Rostedt
2021-10-25 20:08 ` [PATCH v4 7/8] tracing/selftests: Add tests for hist trigger expression parsing Kalesh Singh
2021-10-26 12:43   ` Masami Hiramatsu
2021-10-26 14:28     ` Kalesh Singh
2021-10-26 21:44       ` Steven Rostedt
2021-10-26 23:36         ` Kalesh Singh
2021-10-27  0:20           ` Steven Rostedt
2021-10-27  1:15             ` Kalesh Singh
2021-10-27  3:14               ` Masami Hiramatsu
2021-10-27  4:27                 ` Kalesh Singh
2021-10-27 14:31                   ` Steven Rostedt
2021-10-27 14:52                     ` Masami Hiramatsu
2021-10-27 15:01                       ` Steven Rostedt
2021-10-27 15:50                         ` Steven Rostedt
2021-10-27 15:55                           ` Kalesh Singh
2021-10-27 17:17                             ` Steven Rostedt
2021-10-27  2:34       ` Masami Hiramatsu
2021-10-27 17:36         ` Steven Rostedt
2021-10-26 15:07     ` Steven Rostedt
2021-10-29  6:48   ` [tracing/selftests] cfece71411: kernel-selftests.ftrace.event_trigger_-_test_inter-event_histogram_trigger_onchange_action.fail kernel test robot
2021-10-29  6:48     ` kernel test robot
2021-10-29 12:00     ` Masami Hiramatsu
2021-10-29 12:00       ` Masami Hiramatsu
2021-10-29 13:10       ` Steven Rostedt
2021-10-29 13:10         ` Steven Rostedt
2021-11-01  3:43       ` [LKP] " Li Zhijian
2021-11-01  3:43         ` Li Zhijian
2021-10-25 20:08 ` [PATCH v4 8/8] tracing/histogram: Document expression arithmetic and constants Kalesh Singh

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAC_TJveyKhZ3jyTZ33jbxSKTxxJ1WG+NUUUbf11pJ8Gqk7UeaQ@mail.gmail.com \
    --to=kaleshsingh@google.com \
    --cc=corbet@lwn.net \
    --cc=hridya@google.com \
    --cc=kernel-team@android.com \
    --cc=linux-doc@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-kselftest@vger.kernel.org \
    --cc=mhiramat@kernel.org \
    --cc=mingo@redhat.com \
    --cc=namhyung@kernel.org \
    --cc=rostedt@goodmis.org \
    --cc=shuah@kernel.org \
    --cc=surenb@google.com \
    --cc=zanussi@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.