From: Kalesh Singh <kaleshsingh@google.com>
To: unlisted-recipients:; (no To-header on input)
Cc: surenb@google.com, hridya@google.com, namhyung@kernel.org,
kernel-team@android.com, Kalesh Singh <kaleshsingh@google.com>,
Steven Rostedt <rostedt@goodmis.org>,
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: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2
Date: Mon, 25 Oct 2021 13:08:38 -0700 [thread overview]
Message-ID: <20211025200852.3002369-7-kaleshsingh@google.com> (raw)
In-Reply-To: <20211025200852.3002369-1-kaleshsingh@google.com>
The division is a slow operation. If the divisor is a power of 2, use a
shift instead.
Results were obtained using Android's version of perf (simpleperf[1]) as
described below:
1. hist_field_div() is modified to call 2 test functions:
test_hist_field_div_[not]_optimized(); passing them the
same args. Use noinline and volatile to ensure these are
not optimized out by the compiler.
2. Create a hist event trigger that uses division:
events/kmem/rss_stat$ echo 'hist:keys=common_pid:x=size/<divisor>'
>> trigger
events/kmem/rss_stat$ echo 'hist:keys=common_pid:vals=$x'
>> trigger
3. Run Android's lmkd_test[2] to generate rss_stat events, and
record CPU samples with Android's simpleperf:
simpleperf record -a --exclude-perf --post-unwind=yes -m 16384 -g
-f 2000 -o perf.data
== Results ==
Divisor is a power of 2 (divisor == 32):
test_hist_field_div_not_optimized | 8,717,091 cpu-cycles
test_hist_field_div_optimized | 1,643,137 cpu-cycles
If the divisor is a power of 2, the optimized version is ~5.3x faster.
Divisor is not a power of 2 (divisor == 33):
test_hist_field_div_not_optimized | 4,444,324 cpu-cycles
test_hist_field_div_optimized | 5,497,958 cpu-cycles
If the divisor is not a power of 2, as expected, the optimized version is
slightly slower (~24% slower).
[1] https://android.googlesource.com/platform/system/extras/+/master/simpleperf/doc/README.md
[2] https://cs.android.com/android/platform/superproject/+/master:system/memory/lmkd/tests/lmkd_test.cpp
Signed-off-by: Kalesh Singh <kaleshsingh@google.com>
Suggested-by: Steven Rostedt <rostedt@goodmis.org>
---
kernel/trace/trace_events_hist.c | 4 ++++
1 file changed, 4 insertions(+)
diff --git a/kernel/trace/trace_events_hist.c b/kernel/trace/trace_events_hist.c
index db28bcf976f4..364cb3091789 100644
--- a/kernel/trace/trace_events_hist.c
+++ b/kernel/trace/trace_events_hist.c
@@ -304,6 +304,10 @@ static u64 hist_field_div(struct hist_field *hist_field,
if (!val2)
return -1;
+ /* Use shift if the divisor is a power of 2 */
+ if (!(val2 & (val2 - 1)))
+ return val1 >> __ffs64(val2);
+
return div64_u64(val1, val2);
}
--
2.33.0.1079.g6e70778dc9-goog
next prev parent reply other threads:[~2021-10-25 20:24 UTC|newest]
Thread overview: 40+ 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 ` Kalesh Singh [this message]
2021-10-26 19:14 ` [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2 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
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 12:00 ` Masami Hiramatsu
2021-10-29 13:10 ` Steven Rostedt
2021-11-01 3:43 ` [LKP] " 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=20211025200852.3002369-7-kaleshsingh@google.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).