All of lore.kernel.org
 help / color / mirror / Atom feed
From: Steven Rostedt <rostedt@goodmis.org>
To: Kalesh Singh <kaleshsingh@google.com>
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 22:21:23 -0400	[thread overview]
Message-ID: <20211026222123.5e206fcf@rorschach.local.home> (raw)
In-Reply-To: <CAC_TJvdwqQAKrVs3w6NcQNBT+bAgdyqR+8Zt_An7R9AQSSthGA@mail.gmail.com>

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

  reply	other threads:[~2021-10-27  2:21 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 [this message]
2021-10-27  3:15                 ` Steven Rostedt
2021-10-27  4:04                   ` Kalesh Singh
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=20211026222123.5e206fcf@rorschach.local.home \
    --to=rostedt@goodmis.org \
    --cc=corbet@lwn.net \
    --cc=hridya@google.com \
    --cc=kaleshsingh@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=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.