From: Yury Norov <yury.norov@gmail.com>
To: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>,
linux-kernel@vger.kernel.org
Subject: Re: [PATCH v2 5/6] lib: benchmark bitmap sets binary operation find
Date: Fri, 30 Aug 2024 10:33:13 -0700 [thread overview]
Message-ID: <ZtICWbRiTuPcN6mT@yury-ThinkPad> (raw)
In-Reply-To: <ab577998-946a-4844-a67f-60d17a31ed3c@efficios.com>
On Fri, Aug 30, 2024 at 12:07:53PM -0400, Mathieu Desnoyers wrote:
> On 2024-08-30 17:48, Yury Norov wrote:
> > On Thu, Aug 29, 2024 at 09:59:25AM -0400, Mathieu Desnoyers wrote:
> > > Benchmark the following bitmap find functions applying binary operations
> > > on sets of two bitmaps:
> > >
> > > - find_first_andnot_bit,
> > > - find_first_nor_bit,
> > > - find_next_andnot_bit,
> > > - find_next_nor_bit,
> > > - find_next_or_bit.
> > >
> > > Note that find_first_or_bit is not part of the current API, so it is not
> > > covered.
> >
> > Can you please show how the test output looks on your system now? I'll
> > add that in commit message.
>
> Start testing find_bit() with random-filled bitmap
> find_next_bit: 576314 ns, 163810 iterations
> find_next_zero_bit: 626847 ns, 163871 iterations
> find_last_bit: 465050 ns, 163810 iterations
> find_nth_bit: 2720718 ns, 16329 iterations
> find_first_bit: 1409431 ns, 16330 iterations
> find_first_and_bit: 15216406 ns, 40975 iterations
> find_next_and_bit: 324624 ns, 81708 iterations
> find_first_andnot_bit: 23856039 ns, 40955 iterations
> find_next_andnot_bit: 327734 ns, 82103 iterations
> find_first_nor_bit: 21911075 ns, 40956 iterations
> find_next_nor_bit: 345315 ns, 81919 iterations
> find_next_or_bit: 886338 ns, 245762 iterations
>
> Start testing find_bit() with sparse bitmap
> find_next_bit: 8870 ns, 656 iterations
> find_next_zero_bit: 1188951 ns, 327025 iterations
> find_last_bit: 8380 ns, 656 iterations
> find_nth_bit: 1110068 ns, 655 iterations
> find_first_bit: 455799 ns, 656 iterations
> find_first_and_bit: 6521 ns, 2 iterations
> find_next_and_bit: 3540 ns, 2 iterations
> find_first_andnot_bit: 785844 ns, 655 iterations
> find_next_andnot_bit: 8950 ns, 655 iterations
> find_first_nor_bit: 338646832 ns, 326373 iterations
0.3 sec is too much. Consider a slower CPU where it may be 10
times slower... Can you keep that in a range of few milliseconds?
It's more than enough to grab stable perf results.
> find_next_nor_bit: 1264144 ns, 326372 iterations
> find_next_or_bit: 14020 ns, 1309 iterations
Before the columns were all aligned. Can you please send a v3
with this fixed, and address the other comments?
Thanks,
Yury
>
> Relevant lscpu output:
>
> Architecture: x86_64
> CPU op-mode(s): 32-bit, 64-bit
> Address sizes: 52 bits physical, 57 bits virtual
> Byte Order: Little Endian
> CPU(s): 384
> On-line CPU(s) list: 0-383
> Vendor ID: AuthenticAMD
> Model name: AMD EPYC 9654 96-Core Processor
> CPU family: 25
> Model: 17
> Thread(s) per core: 2
> Core(s) per socket: 96
> Socket(s): 2
> Stepping: 1
> Frequency boost: enabled
> CPU(s) scaling MHz: 100%
> CPU max MHz: 3709.0000
> CPU min MHz: 400.0000
> BogoMIPS: 4799.80
> Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext
> fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good amd_lbr_v2 nopl xtopology nonstop_tsc cpuid extd_apicid aperfmperf rap
> l pni pclmulqdq monitor ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_leg
> acy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb
> bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba perfmon_v2 ibrs ibpb stibp ibrs_enhanced vmmcall fsgsbase
> bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb avx512cd sha_ni
> avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local user_shstk avx512_b
> f16 clzero irperf xsaveerptr rdpru wbnoinvd amd_ppin cppc arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushby
> asid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif x2avic v_spec_ctrl vnmi avx512vbmi umip pku ospke
> avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq la57 rdpid overflow_recov succor smca fsrm
> flush_l1d debug_swap
> Virtualization features:
> Virtualization: AMD-V
> Caches (sum of all):
> L1d: 6 MiB (192 instances)
> L1i: 6 MiB (192 instances)
> L2: 192 MiB (192 instances)
> L3: 768 MiB (24 instances)
> NUMA:
> NUMA node(s): 24
> NUMA node0 CPU(s): 0-7,192-199
> NUMA node1 CPU(s): 8-15,200-207
> NUMA node2 CPU(s): 16-23,208-215
> NUMA node3 CPU(s): 24-31,216-223
> NUMA node4 CPU(s): 32-39,224-231
> NUMA node5 CPU(s): 40-47,232-239
> NUMA node6 CPU(s): 48-55,240-247
> NUMA node7 CPU(s): 56-63,248-255
> NUMA node8 CPU(s): 64-71,256-263
> NUMA node9 CPU(s): 72-79,264-271
> NUMA node10 CPU(s): 80-87,272-279
> NUMA node11 CPU(s): 88-95,280-287
> NUMA node12 CPU(s): 96-103,288-295
> NUMA node13 CPU(s): 104-111,296-303
> NUMA node14 CPU(s): 112-119,304-311
> NUMA node15 CPU(s): 120-127,312-319
> NUMA node16 CPU(s): 128-135,320-327
> NUMA node17 CPU(s): 136-143,328-335
> NUMA node18 CPU(s): 144-151,336-343
> NUMA node19 CPU(s): 152-159,344-351
> NUMA node20 CPU(s): 160-167,352-359
> NUMA node21 CPU(s): 168-175,360-367
> NUMA node22 CPU(s): 176-183,368-375
> NUMA node23 CPU(s): 184-191,376-383
> Vulnerabilities:
> Gather data sampling: Not affected
> Itlb multihit: Not affected
> L1tf: Not affected
> Mds: Not affected
> Meltdown: Not affected
> Mmio stale data: Not affected
> Reg file data sampling: Not affected
> Retbleed: Not affected
> Spec rstack overflow: Vulnerable
> Spec store bypass: Vulnerable
> Spectre v1: Vulnerable: __user pointer sanitization and usercopy barriers only; no swapgs barriers
> Spectre v2: Vulnerable; IBPB: disabled; STIBP: disabled; PBRSB-eIBRS: Not affected; BHI: Not affected
> Srbds: Not affected
> Tsx async abort: Not affected
>
>
>
> >
> > >
> > > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > Cc: Yury Norov <yury.norov@gmail.com>
> > > Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> > > ---
> > > lib/find_bit_benchmark.c | 93 ++++++++++++++++++++++++++++++++++++++++
> > > 1 file changed, 93 insertions(+)
> > >
> > > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> > > index aee2ebb6b3cd..3b16254dec23 100644
> > > --- a/lib/find_bit_benchmark.c
> > > +++ b/lib/find_bit_benchmark.c
> > > @@ -70,6 +70,44 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
> > > return 0;
> > > }
> > > +static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, unsigned long len)
> > > +{
> > > + static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> > > + unsigned long i, cnt;
> > > + ktime_t time;
> > > +
> > > + bitmap_copy(cp, bitmap, BITMAP_LEN);
> > > +
> > > + time = ktime_get();
> > > + for (cnt = i = 0; i < len; cnt++) {
> > > + i = find_first_andnot_bit(cp, bitmap2, len);
> > > + __clear_bit(i, cp);
> > > + }
> > > + time = ktime_get() - time;
> > > + pr_err("find_first_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt);
> > > +
> > > + return 0;
> > > +}
> > > +
> > > +static int __init test_find_first_nor_bit(void *bitmap, const void *bitmap2, unsigned long len)
> > > +{
> > > + static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> > > + unsigned long i, cnt;
> > > + ktime_t time;
> > > +
> > > + bitmap_copy(cp, bitmap, BITMAP_LEN);
> > > +
> > > + time = ktime_get();
> > > + for (cnt = i = 0; i < len; cnt++) {
> > > + i = find_first_nor_bit(cp, bitmap2, len);
> > > + __set_bit(i, cp);
> > > + }
> > > + time = ktime_get() - time;
> > > + pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
> > > +
> > > + return 0;
> > > +}
> > > +
> > > static int __init test_find_next_bit(const void *bitmap, unsigned long len)
> > > {
> > > unsigned long i, cnt;
> > > @@ -148,6 +186,51 @@ static int __init test_find_next_and_bit(const void *bitmap,
> > > return 0;
> > > }
> > > +static int __init test_find_next_andnot_bit(const void *bitmap,
> > > + const void *bitmap2, unsigned long len)
> > > +{
> > > + unsigned long i, cnt;
> > > + ktime_t time;
> > > +
> > > + time = ktime_get();
> > > + for (cnt = i = 0; i < BITMAP_LEN; cnt++)
> > > + i = find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> > > + time = ktime_get() - time;
> > > + pr_err("find_next_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt);
> > > +
> > > + return 0;
> > > +}
> > > +
> > > +static int __init test_find_next_nor_bit(const void *bitmap,
> > > + const void *bitmap2, unsigned long len)
> > > +{
> > > + unsigned long i, cnt;
> > > + ktime_t time;
> > > +
> > > + time = ktime_get();
> > > + for (cnt = i = 0; i < BITMAP_LEN; cnt++)
> > > + i = find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> > > + time = ktime_get() - time;
> > > + pr_err("find_next_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
> > > +
> > > + return 0;
> > > +}
> > > +
> > > +static int __init test_find_next_or_bit(const void *bitmap,
> > > + const void *bitmap2, unsigned long len)
> > > +{
> > > + unsigned long i, cnt;
> > > + ktime_t time;
> > > +
> > > + time = ktime_get();
> > > + for (cnt = i = 0; i < BITMAP_LEN; cnt++)
> > > + i = find_next_or_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> > > + time = ktime_get() - time;
> > > + pr_err("find_next_or_bit: %18llu ns, %6ld iterations\n", time, cnt);
> > > +
> > > + return 0;
> > > +}
> > > +
> > > static int __init find_bit_test(void)
> > > {
> > > unsigned long nbits = BITMAP_LEN / SPARSE;
> > > @@ -169,6 +252,11 @@ static int __init find_bit_test(void)
> > > test_find_first_bit(bitmap, BITMAP_LEN / 10);
> > > test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> > > test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> > > + test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> > > + test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
> > > pr_err("\nStart testing find_bit() with sparse bitmap\n");
> > > @@ -187,6 +275,11 @@ static int __init find_bit_test(void)
> > > test_find_first_bit(bitmap, BITMAP_LEN);
> > > test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
> > > test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> > > + test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
> > > /*
> > > * Everything is OK. Return error just to let user run benchmark
> > > --
> > > 2.39.2
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
next prev parent reply other threads:[~2024-08-30 17:33 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-08-29 13:59 [PATCH v2 0/6] lib: Extend bitmap find binary operations Mathieu Desnoyers
2024-08-29 13:59 ` [PATCH v2 1/6] lib: Clarify comment on top of find_next_andnot_bit Mathieu Desnoyers
2024-08-29 13:59 ` [PATCH v2 2/6] lib: Implement find_{first,next,nth}_nor_bit, for_each_nor_bit, find_first_andnot_bit Mathieu Desnoyers
2024-08-29 13:59 ` [PATCH v2 3/6] lib: test bitmap sets binary operation iterators Mathieu Desnoyers
2024-08-29 13:59 ` [PATCH v2 4/6] lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark Mathieu Desnoyers
2024-08-30 15:46 ` Yury Norov
2024-08-30 15:50 ` Mathieu Desnoyers
2024-08-29 13:59 ` [PATCH v2 5/6] lib: benchmark bitmap sets binary operation find Mathieu Desnoyers
2024-08-30 15:48 ` Yury Norov
2024-08-30 16:07 ` Mathieu Desnoyers
2024-08-30 17:33 ` Yury Norov [this message]
2024-08-29 13:59 ` [PATCH v2 6/6] cpumask: Implement cpumask_{first,next}_{nor,andnot} Mathieu Desnoyers
2024-08-30 15:56 ` [PATCH v2 0/6] lib: Extend bitmap find binary operations Yury Norov
2024-08-30 16:10 ` Mathieu Desnoyers
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=ZtICWbRiTuPcN6mT@yury-ThinkPad \
--to=yury.norov@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=mathieu.desnoyers@efficios.com \
/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.