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, mhiramat@kernel.org,
Jonathan Corbet <corbet@lwn.net>, Ingo Molnar <mingo@redhat.com>,
Shuah Khan <shuah@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 v2 1/4] tracing/histogram: Optimize division by constants
Date: Fri, 29 Oct 2021 11:53:16 -0700 [thread overview]
Message-ID: <CAC_TJve9OsL5taBN0ckgjG4=HxvmWfP6ULwwqnVsDyRxuQuRkg@mail.gmail.com> (raw)
In-Reply-To: <20211029144524.367d6789@gandalf.local.home>
On Fri, Oct 29, 2021 at 11:45 AM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Fri, 29 Oct 2021 11:33:27 -0700
> Kalesh Singh <kaleshsingh@google.com> wrote:
>
> > If the divisor is a constant use specific division functions to
> > avoid extra branches when the trigger is hit.
> >
> > If the divisor constant but not a power of 2, the division can be
> > replaced with a multiplication and shift in the following case:
> >
> > Let X = dividend and Y = divisor.
> >
> > Choose Z = some power of 2. If Y <= Z, then:
> > X / Y = (X * (Z / Y)) / Z
> >
> > (Z / Y) is a constant (mult) which is calculated at parse time, so:
> > X / Y = (X * mult) / Z
> >
> > The division by Z can be replaced by a shift since Z is a power of 2:
> > X / Y = (X * mult) >> shift
> >
> > As long, as X < Z the results will not be off by more than 1.
> >
> > Signed-off-by: Kalesh Singh <kaleshsingh@google.com>
> > Suggested-by: Steven Rostedt <rostedt@goodmis.org>
> > ---
> >
> > Changes in v2:
> > - Return -EDOM if divisor is a constant and zero, per Steve
> >
> > kernel/trace/trace_events_hist.c | 117 ++++++++++++++++++++++++++++++-
> > 1 file changed, 116 insertions(+), 1 deletion(-)
> >
> > diff --git a/kernel/trace/trace_events_hist.c b/kernel/trace/trace_events_hist.c
> > index 364cb3091789..1084aa41f047 100644
> > --- a/kernel/trace/trace_events_hist.c
> > +++ b/kernel/trace/trace_events_hist.c
> > @@ -68,7 +68,8 @@
> > C(INVALID_SORT_FIELD, "Sort field must be a key or a val"), \
> > C(INVALID_STR_OPERAND, "String type can not be an operand in expression"), \
> > C(EXPECT_NUMBER, "Expecting numeric literal"), \
> > - C(UNARY_MINUS_SUBEXPR, "Unary minus not supported in sub-expressions"),
> > + C(UNARY_MINUS_SUBEXPR, "Unary minus not supported in sub-expressions"), \
> > + C(DIVISION_BY_ZERO, "Division by zero"),
> >
> > #undef C
> > #define C(a, b) HIST_ERR_##a
> > @@ -92,6 +93,7 @@ typedef u64 (*hist_field_fn_t) (struct hist_field *field,
> > #define HIST_FIELDS_MAX (TRACING_MAP_FIELDS_MAX + TRACING_MAP_VARS_MAX)
> > #define HIST_ACTIONS_MAX 8
> > #define HIST_CONST_DIGITS_MAX 21
> > +#define HIST_DIV_SHIFT 20 /* For optimizing division by constants */
> >
> > enum field_op_id {
> > FIELD_OP_NONE,
> > @@ -160,6 +162,8 @@ struct hist_field {
> >
> > /* Numeric literals are represented as u64 */
> > u64 constant;
> > + /* Used to optimize division by constants */
> > + u64 div_multiplier;
> > };
> >
> > static u64 hist_field_none(struct hist_field *field,
> > @@ -311,6 +315,72 @@ static u64 hist_field_div(struct hist_field *hist_field,
> > return div64_u64(val1, val2);
> > }
> >
> > +static u64 div_by_power_of_two(struct hist_field *hist_field,
> > + struct tracing_map_elt *elt,
> > + struct trace_buffer *buffer,
> > + struct ring_buffer_event *rbe,
> > + void *event)
> > +{
> > + struct hist_field *operand1 = hist_field->operands[0];
> > + struct hist_field *operand2 = hist_field->operands[1];
> > +
> > + u64 val1 = operand1->fn(operand1, elt, buffer, rbe, event);
> > + u64 val2 = operand2->fn(operand2, elt, buffer, rbe, event);
>
> If these functions are only called when val2 is constant, can't we make it
> such that we get val2 from the hist_field directly? That is:
>
> u64 val2 = operand2->constant;
operand2 might be a var ref to a constant, so we would need to resolve
that with hist_field_var_ref().
-Kalesh
>
> That would save us a function call, and an indirect on at that (that gets
> slowed down by spectre).
>
> Same for the ones below.
>
> -- Steve
>
>
> > +
> > + return val1 >> __ffs64(val2);
> > +}
> > +
> > +static u64 div_by_not_power_of_two(struct hist_field *hist_field,
> > + struct tracing_map_elt *elt,
> > + struct trace_buffer *buffer,
> > + struct ring_buffer_event *rbe,
> > + void *event)
> > +{
> > + struct hist_field *operand1 = hist_field->operands[0];
> > + struct hist_field *operand2 = hist_field->operands[1];
> > +
> > + u64 val1 = operand1->fn(operand1, elt, buffer, rbe, event);
> > + u64 val2 = operand2->fn(operand2, elt, buffer, rbe, event);
> > +
> > + return div64_u64(val1, val2);
> > +}
> > +
> > +static u64 div_by_mult_and_shift(struct hist_field *hist_field,
> > + struct tracing_map_elt *elt,
> > + struct trace_buffer *buffer,
> > + struct ring_buffer_event *rbe,
> > + void *event)
> > +{
> > + struct hist_field *operand1 = hist_field->operands[0];
> > + struct hist_field *operand2 = hist_field->operands[1];
> > +
> > + u64 val1 = operand1->fn(operand1, elt, buffer, rbe, event);
> > +
> > + /*
> > + * If the divisor is a constant, do a multiplication and shift instead.
> > + *
> > + * Choose Z = some power of 2. If Y <= Z, then:
> > + * X / Y = (X * (Z / Y)) / Z
> > + *
> > + * (Z / Y) is a constant (mult) which is calculated at parse time, so:
> > + * X / Y = (X * mult) / Z
> > + *
> > + * The division by Z can be replaced by a shift since Z is a power of 2:
> > + * X / Y = (X * mult) >> HIST_DIV_SHIFT
> > + *
> > + * As long, as X < Z the results will not be off by more than 1.
> > + */
> > + if (val1 < (1 << HIST_DIV_SHIFT)) {
> > + u64 mult = operand2->div_multiplier;
> > +
> > + return (val1 * mult + ((1 << HIST_DIV_SHIFT) - 1)) >> HIST_DIV_SHIFT;
> > + } else {
> > + u64 val2 = operand2->fn(operand2, elt, buffer, rbe, event);
> > +
> > + return div64_u64(val1, val2);
> > + }
> > +}
> > +
> > static u64 hist_field_mult(struct hist_field *hist_field,
> > struct tracing_map_elt *elt,
> > struct trace_buffer *buffer,
> > @@ -573,6 +643,37 @@ struct snapshot_context {
> > void *key;
> > };
> >
> > +
> > +static struct hist_field *find_var_field(struct hist_trigger_data *hist_data,
> > + const char *var_name);
> > +
> > +/*
> > + * Returns the specific division function to use if the divisor
> > + * is constant. This avoids extra branches when the trigger is hit.
> > + */
> > +static hist_field_fn_t hist_field_get_div_fn(struct hist_field *divisor)
> > +{
> > + u64 div;
> > +
> > + if (divisor->flags & HIST_FIELD_FL_VAR_REF) {
> > + struct hist_field *var;
> > +
> > + var = find_var_field(divisor->var.hist_data, divisor->name);
> > + div = var->constant;
> > + } else
> > + div = divisor->constant;
> > +
> > + if (!(div & (div - 1)))
> > + return div_by_power_of_two;
> > +
> > + /* If the divisor is too large, do a regular division */
> > + if (div > (1 << HIST_DIV_SHIFT))
> > + return div_by_not_power_of_two;
> > +
> > + divisor->div_multiplier = div64_u64((u64)(1 << HIST_DIV_SHIFT), div);
> > + return div_by_mult_and_shift;
> > +}
> > +
> > static void track_data_free(struct track_data *track_data)
> > {
> > struct hist_elt_data *elt_data;
> > @@ -2575,6 +2676,20 @@ static struct hist_field *parse_expr(struct hist_trigger_data *hist_data,
> > expr->operands[0] = operand1;
> > expr->operands[1] = operand2;
> >
> > +
> > + if (field_op == FIELD_OP_DIV &&
> > + operand2_flags & HIST_FIELD_FL_CONST) {
> > + u64 divisor = (var2) ? var2->constant : operand2->constant;
> > +
> > + if (!divisor) {
> > + hist_err(file->tr, HIST_ERR_DIVISION_BY_ZERO, errpos(str));
> > + ret = -EDOM;
> > + goto free;
> > + }
> > +
> > + op_fn = hist_field_get_div_fn(operand2);
> > + }
> > +
> > if (combine_consts) {
> > if (var1)
> > expr->operands[0] = var1;
>
next prev parent reply other threads:[~2021-10-29 18:53 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-29 18:33 [PATCH 0/4] tracing/histogram: Division optimization and expression kselftests Kalesh Singh
2021-10-29 18:33 ` [PATCH v2 1/4] tracing/histogram: Optimize division by constants Kalesh Singh
2021-10-29 18:45 ` Steven Rostedt
2021-10-29 18:53 ` Kalesh Singh [this message]
2021-10-29 19:16 ` Kalesh Singh
2021-10-29 20:25 ` Steven Rostedt
2021-10-29 22:31 ` Kalesh Singh
2021-10-29 23:24 ` [PATCH v3] " Kalesh Singh
2021-10-29 18:33 ` [PATCH 2/4] tracing/histogram: Update division by 0 documentation Kalesh Singh
2021-10-29 18:33 ` [PATCH v3 3/4] tracing/histogram: Document hist trigger variables Kalesh Singh
2021-10-29 18:33 ` [PATCH v7 4/4] tracing/selftests: Add tests for hist trigger expression parsing 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_TJve9OsL5taBN0ckgjG4=HxvmWfP6ULwwqnVsDyRxuQuRkg@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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).