* [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt
@ 2020-12-11 8:50 Levi Yun
2020-12-11 16:11 ` Andy Shevchenko
2020-12-11 17:20 ` Yury Norov
0 siblings, 2 replies; 6+ messages in thread
From: Levi Yun @ 2020-12-11 8:50 UTC (permalink / raw)
To: dushistov, arnd, akpm, gustavo, vilhelm.gray, richard.weiyang,
andriy.shevchenko, joseph.qi, skalluru, yury.norov, jpoimboe
Cc: linux-kernel
We should have same iteration count when we walk the same bitmap
regardless of using find_next_bit or find_last_bit.
When we run the find_bit_benchmark.ko, we sometime get
unmatched iterations count below:
Start testing find_bit() with random-filled bitmap
[+...] find_next_bit: 875085 ns, 163755 iterations <
[+...] find_next_zero_bit: 865319 ns, 163926 iterations
[+...] find_last_bit: 611807 ns, 163756 iterations <
[+...] find_first_bit: 1601016 ns, 16335 iterations
[+...] find_next_and_bit: 400645 ns, 74040 iterations
[+...]
Start testing find_bit() with sparse bitmap
[+...] find_next_bit: 9942 ns, 654 iterations
[+...] find_next_zero_bit: 1678445 ns, 327027 iterations
[+...] find_last_bit: 7131 ns, 654 iterations
[+...] find_first_bit: 551383 ns, 654 iterations
[+...] find_next_and_bit: 3027 ns, 1 iterations
Normally, this is happen when the last bit of bitmap was set.
This patch fix the unmatched iterations count between
test_find_next_bit and test_find_last_bit.
Signed-off-by: Levi Yun <ppbuk5246@gmail.com>
---
lib/find_bit_benchmark.c | 30 ++++++++++++++++--------------
1 file changed, 16 insertions(+), 14 deletions(-)
diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 5637c5711db9..766e0487852b 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -35,14 +35,14 @@ static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata;
*/
static int __init test_find_first_bit(void *bitmap, unsigned long len)
{
- unsigned long i, cnt;
+ unsigned long i = 0, cnt = 0;
ktime_t time;
time = ktime_get();
- for (cnt = i = 0; i < len; cnt++) {
+ do {
i = find_first_bit(bitmap, len);
__clear_bit(i, bitmap);
- }
+ } while (i++ < len && ++cnt);
time = ktime_get() - time;
pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt);
@@ -51,12 +51,13 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len)
static int __init test_find_next_bit(const void *bitmap, unsigned long len)
{
- unsigned long i, cnt;
+ unsigned long i = 0, cnt = 0;
ktime_t time;
time = ktime_get();
- for (cnt = i = 0; i < BITMAP_LEN; cnt++)
- i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
+ do {
+ i = find_next_bit(bitmap, BITMAP_LEN, i);
+ } while (i++ < BITMAP_LEN && ++cnt);
time = ktime_get() - time;
pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt);
@@ -65,12 +66,13 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len)
static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
{
- unsigned long i, cnt;
+ unsigned long i = 0, cnt = 0;
ktime_t time;
time = ktime_get();
- for (cnt = i = 0; i < BITMAP_LEN; cnt++)
- i = find_next_zero_bit(bitmap, len, i) + 1;
+ do {
+ i = find_next_zero_bit(bitmap, len, i);
+ } while (i++ < BITMAP_LEN && ++cnt);
time = ktime_get() - time;
pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
@@ -84,12 +86,11 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
time = ktime_get();
do {
- cnt++;
l = find_last_bit(bitmap, len);
if (l >= len)
break;
len = l;
- } while (len);
+ } while (len >= 0 && ++cnt);
time = ktime_get() - time;
pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt);
@@ -99,12 +100,13 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
static int __init test_find_next_and_bit(const void *bitmap,
const void *bitmap2, unsigned long len)
{
- unsigned long i, cnt;
+ unsigned long i = 0, cnt = 0;
ktime_t time;
time = ktime_get();
- for (cnt = i = 0; i < BITMAP_LEN; cnt++)
- i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
+ do {
+ i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i);
+ } while (i++ < BITMAP_LEN && ++cnt);
time = ktime_get() - time;
pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
--
2.27.0
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt 2020-12-11 8:50 [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt Levi Yun @ 2020-12-11 16:11 ` Andy Shevchenko 2020-12-11 17:20 ` Yury Norov 1 sibling, 0 replies; 6+ messages in thread From: Andy Shevchenko @ 2020-12-11 16:11 UTC (permalink / raw) To: Levi Yun Cc: dushistov, arnd, akpm, gustavo, vilhelm.gray, richard.weiyang, joseph.qi, skalluru, yury.norov, jpoimboe, linux-kernel On Fri, Dec 11, 2020 at 05:50:39PM +0900, Levi Yun wrote: > We should have same iteration count when we walk the same bitmap > regardless of using find_next_bit or find_last_bit. I didn't understand why is so (I mean "same", I think you rather talking about same order of amount of itterations). > When we run the find_bit_benchmark.ko, we sometime get > unmatched iterations count below: > > Start testing find_bit() with random-filled bitmap > [+...] find_next_bit: 875085 ns, 163755 iterations < > [+...] find_next_zero_bit: 865319 ns, 163926 iterations > [+...] find_last_bit: 611807 ns, 163756 iterations < > [+...] find_first_bit: 1601016 ns, 16335 iterations > [+...] find_next_and_bit: 400645 ns, 74040 iterations > [+...] > Start testing find_bit() with sparse bitmap > [+...] find_next_bit: 9942 ns, 654 iterations > [+...] find_next_zero_bit: 1678445 ns, 327027 iterations > [+...] find_last_bit: 7131 ns, 654 iterations > [+...] find_first_bit: 551383 ns, 654 iterations > [+...] find_next_and_bit: 3027 ns, 1 iterations > > Normally, this is happen when the last bit of bitmap was set. > > This patch fix the unmatched iterations count between > test_find_next_bit and test_find_last_bit. Can you provide before and after to compare? -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt 2020-12-11 8:50 [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt Levi Yun 2020-12-11 16:11 ` Andy Shevchenko @ 2020-12-11 17:20 ` Yury Norov 2020-12-12 0:09 ` Yun Levi 1 sibling, 1 reply; 6+ messages in thread From: Yury Norov @ 2020-12-11 17:20 UTC (permalink / raw) To: Levi Yun Cc: dushistov, Arnd Bergmann, Andrew Morton, Gustavo A. R. Silva, William Breathitt Gray, richard.weiyang, Andy Shevchenko, joseph.qi, skalluru, Josh Poimboeuf, Linux Kernel Mailing List On Fri, Dec 11, 2020 at 12:50 AM Levi Yun <ppbuk5246@gmail.com> wrote: > > We should have same iteration count when we walk the same bitmap > regardless of using find_next_bit or find_last_b I think it's not that important, because the difference is not measurable. But if this part raises questions, I have nothing against aligning numbers. > When we run the find_bit_benchmark.ko, we sometime get > unmatched iterations count below: > > Start testing find_bit() with random-filled bitmap > [+...] find_next_bit: 875085 ns, 163755 iterations < > [+...] find_next_zero_bit: 865319 ns, 163926 iterations > [+...] find_last_bit: 611807 ns, 163756 iterations < > [+...] find_first_bit: 1601016 ns, 16335 iterations > [+...] find_next_and_bit: 400645 ns, 74040 iterations > [+...] > Start testing find_bit() with sparse bitmap > [+...] find_next_bit: 9942 ns, 654 iterations > [+...] find_next_zero_bit: 1678445 ns, 327027 iterations > [+...] find_last_bit: 7131 ns, 654 iterations > [+...] find_first_bit: 551383 ns, 654 iterations > [+...] find_next_and_bit: 3027 ns, 1 iterations > > Normally, this is happen when the last bit of bitmap was set. Can you please confirm that for bitmap 0001, test_find_{first,next,next_and}_bit reports cnt == 0, and test_find_last_bit() reports 1? > This patch fix the unmatched iterations count between > test_find_next_bit and test_find_last_bit. > > Signed-off-by: Levi Yun <ppbuk5246@gmail.com> > --- > lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- > 1 file changed, 16 insertions(+), 14 deletions(-) > > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c > index 5637c5711db9..766e0487852b 100644 > --- a/lib/find_bit_benchmark.c > +++ b/lib/find_bit_benchmark.c > @@ -35,14 +35,14 @@ static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; > */ > static int __init test_find_first_bit(void *bitmap, unsigned long len) > { > - unsigned long i, cnt; > + unsigned long i = 0, cnt = 0; > ktime_t time; > > time = ktime_get(); > - for (cnt = i = 0; i < len; cnt++) { > + do { > i = find_first_bit(bitmap, len); > __clear_bit(i, bitmap); > - } > + } while (i++ < len && ++cnt); What for this check against ++cnt? I doubt that the counter can overflow. > time = ktime_get() - time; > pr_err("find_first_bit: %18llu ns, %6ld\n", time, cnt); > > @@ -51,12 +51,13 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len) > > static int __init test_find_next_bit(const void *bitmap, unsigned long len) > { > - unsigned long i, cnt; > + unsigned long i = 0, cnt = 0; > ktime_t time; > > time = ktime_get(); > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > - i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; > + do { > + i = find_next_bit(bitmap, BITMAP_LEN, i); > + } while (i++ < BITMAP_LEN && ++cnt); > time = ktime_get() - time; > pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); > > @@ -65,12 +66,13 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len) > > static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) > { > - unsigned long i, cnt; > + unsigned long i = 0, cnt = 0; > ktime_t time; > > time = ktime_get(); > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > - i = find_next_zero_bit(bitmap, len, i) + 1; > + do { > + i = find_next_zero_bit(bitmap, len, i); > + } while (i++ < BITMAP_LEN && ++cnt); > time = ktime_get() - time; > pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); > > @@ -84,12 +86,11 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > > time = ktime_get(); > do { > - cnt++; > l = find_last_bit(bitmap, len); > if (l >= len) > break; > len = l; > - } while (len); > + } while (len >= 0 && ++cnt); Why this? > time = ktime_get() - time; > pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); > > @@ -99,12 +100,13 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > static int __init test_find_next_and_bit(const void *bitmap, > const void *bitmap2, unsigned long len) > { > - unsigned long i, cnt; > + unsigned long i = 0, cnt = 0; > ktime_t time; > > time = ktime_get(); > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > - i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); > + do { > + i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i); > + } while (i++ < BITMAP_LEN && ++cnt); Do you experience the same problem with find_next_and_bit() as well? > time = ktime_get() - time; > pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); > > -- > 2.27.0 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt 2020-12-11 17:20 ` Yury Norov @ 2020-12-12 0:09 ` Yun Levi 2020-12-12 18:55 ` Yury Norov 0 siblings, 1 reply; 6+ messages in thread From: Yun Levi @ 2020-12-12 0:09 UTC (permalink / raw) To: Yury Norov Cc: dushistov, Arnd Bergmann, Andrew Morton, Gustavo A. R. Silva, William Breathitt Gray, richard.weiyang, Andy Shevchenko, joseph.qi, skalluru, Josh Poimboeuf, Linux Kernel Mailing List > I didn't understand why is so (I mean "same", I think you rather talking about > same order of amount of itterations). Yes. That's what I want to talk about. Thanks! > Can you provide before and after to compare? I tested when the bitmap's 0 bit is set only. and below are before and after results. before: Start testing find_bit() with random-filled bitmap [ +0.000481] find_next_bit: 8966 ns, 2 iterations [ +0.001739] find_next_zero_bit: 1726335 ns, 327679 iterations [ +0.000020] find_last_bit: 7428 ns, 1 iterations [ +0.000017] find_first_bit: 5523 ns, 2 iterations [ +0.000022] find_next_and_bit: 9643 ns, 1 iterations [ +0.000007] Start testing find_bit() with sparse bitmap [ +0.000041] find_next_bit: 16343 ns, 656 iterations [ +0.001943] find_next_zero_bit: 1928324 ns, 327025 iterations [ +0.000029] find_last_bit: 14398 ns, 656 iterations [ +0.000725] find_first_bit: 711383 ns, 656 iterations [ +0.000022] find_next_and_bit: 9581 ns, 1 iterations after: [Dec12 08:25] Start testing find_bit() with random-filled bitmap [ +0.000687] find_next_bit: 11079 ns, 1 iterations [ +0.002156] find_next_zero_bit: 2055752 ns, 327679 iterations [ +0.000022] find_last_bit: 8052 ns, 1 iterations [ +0.000020] find_first_bit: 6270 ns, 1 iterations [ +0.000024] find_next_and_bit: 9519 ns, 0 iterations [ +0.000007] Start testing find_bit() with sparse bitmap [ +0.000047] find_next_bit: 18389 ns, 655 iterations [ +0.001807] find_next_zero_bit: 1793314 ns, 327025 iterations [ +0.000027] find_last_bit: 13600 ns, 655 iterations [ +0.000604] find_first_bit: 591173 ns, 655 iterations [ +0.000023] find_next_and_bit: 9392 ns, 0 iterations >I think it's not that important, because the difference is not measurable. > But if this part raises questions, I have nothing against aligning numbers. Right it's not that important, But if the amount of iteration value is not same to the same bitmap, makes people confused when they run the test cases. so I just fix. > What for this check against ++cnt? I doubt that the counter can overflow. This test case suppose the bitmap size is 327680 (4096UL * 8 * 10) So I think there is no case that the counter can overflow in the testcase. >> time = ktime_get() - time; >> pr_err("find_first_bit: %18llu ns, %6ld\n", time, cnt); > Why this? Sorry, I don't catch what you are saying. Could you tell me in detail? > Can you please confirm that for bitmap 0001, > test_find_{first,next,next_and}_bit reports cnt == 0, and > test_find_last_bit() reports 1? This happens because "test_find_first_bit" calls __clear_bit in case of bitmap 0001 (only 0 bit set), the test_find_first_bit will clear the 0 bit that makes no match with bitmap2 so it reports 0. In the view we need to call the find_last_bit or find_next_bit to know bitmap is empty so cnt should be the 1 in that case, I think it possible by initializing cnt as 1. > Do you experience the same problem with find_next_and_bit() as well? Nope, But compared to other test cases, I think it's better to integrate their format. Should I sustain the former one? On Sat, Dec 12, 2020 at 2:20 AM Yury Norov <yury.norov@gmail.com> wrote: > > On Fri, Dec 11, 2020 at 12:50 AM Levi Yun <ppbuk5246@gmail.com> wrote: > > > > We should have same iteration count when we walk the same bitmap > > regardless of using find_next_bit or find_last_b > > I think it's not that important, because the difference is not measurable. > But if this part raises questions, I have nothing against aligning numbers. > > > When we run the find_bit_benchmark.ko, we sometime get > > unmatched iterations count below: > > > > Start testing find_bit() with random-filled bitmap > > [+...] find_next_bit: 875085 ns, 163755 iterations < > > [+...] find_next_zero_bit: 865319 ns, 163926 iterations > > [+...] find_last_bit: 611807 ns, 163756 iterations < > > [+...] find_first_bit: 1601016 ns, 16335 iterations > > [+...] find_next_and_bit: 400645 ns, 74040 iterations > > [+...] > > Start testing find_bit() with sparse bitmap > > [+...] find_next_bit: 9942 ns, 654 iterations > > [+...] find_next_zero_bit: 1678445 ns, 327027 iterations > > [+...] find_last_bit: 7131 ns, 654 iterations > > [+...] find_first_bit: 551383 ns, 654 iterations > > [+...] find_next_and_bit: 3027 ns, 1 iterations > > > > Normally, this is happen when the last bit of bitmap was set. > > Can you please confirm that for bitmap 0001, > test_find_{first,next,next_and}_bit reports cnt == 0, and > test_find_last_bit() reports 1? > > > This patch fix the unmatched iterations count between > > test_find_next_bit and test_find_last_bit. > > > > Signed-off-by: Levi Yun <ppbuk5246@gmail.com> > > --- > > lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- > > 1 file changed, 16 insertions(+), 14 deletions(-) > > > > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c > > index 5637c5711db9..766e0487852b 100644 > > --- a/lib/find_bit_benchmark.c > > +++ b/lib/find_bit_benchmark.c > > @@ -35,14 +35,14 @@ static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; > > */ > > static int __init test_find_first_bit(void *bitmap, unsigned long len) > > { > > - unsigned long i, cnt; > > + unsigned long i = 0, cnt = 0; > > ktime_t time; > > > > time = ktime_get(); > > - for (cnt = i = 0; i < len; cnt++) { > > + do { > > i = find_first_bit(bitmap, len); > > __clear_bit(i, bitmap); > > - } > > + } while (i++ < len && ++cnt); > > What for this check against ++cnt? I doubt that the counter can overflow. > > > time = ktime_get() - time; > > pr_err("find_first_bit: %18llu ns, %6ld\n", time, cnt); > > > > @@ -51,12 +51,13 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len) > > > > static int __init test_find_next_bit(const void *bitmap, unsigned long len) > > { > > - unsigned long i, cnt; > > + unsigned long i = 0, cnt = 0; > > ktime_t time; > > > > time = ktime_get(); > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > - i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; > > + do { > > + i = find_next_bit(bitmap, BITMAP_LEN, i); > > + } while (i++ < BITMAP_LEN && ++cnt); > > time = ktime_get() - time; > > pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > @@ -65,12 +66,13 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len) > > > > static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) > > { > > - unsigned long i, cnt; > > + unsigned long i = 0, cnt = 0; > > ktime_t time; > > > > time = ktime_get(); > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > - i = find_next_zero_bit(bitmap, len, i) + 1; > > + do { > > + i = find_next_zero_bit(bitmap, len, i); > > + } while (i++ < BITMAP_LEN && ++cnt); > > time = ktime_get() - time; > > pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > @@ -84,12 +86,11 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > > > > time = ktime_get(); > > do { > > - cnt++; > > l = find_last_bit(bitmap, len); > > if (l >= len) > > break; > > len = l; > > - } while (len); > > + } while (len >= 0 && ++cnt); > > Why this? > > > time = ktime_get() - time; > > pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > @@ -99,12 +100,13 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > > static int __init test_find_next_and_bit(const void *bitmap, > > const void *bitmap2, unsigned long len) > > { > > - unsigned long i, cnt; > > + unsigned long i = 0, cnt = 0; > > ktime_t time; > > > > time = ktime_get(); > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > - i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); > > + do { > > + i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i); > > + } while (i++ < BITMAP_LEN && ++cnt); > > Do you experience the same problem with find_next_and_bit() as well? > > > time = ktime_get() - time; > > pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > -- > > 2.27.0 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt 2020-12-12 0:09 ` Yun Levi @ 2020-12-12 18:55 ` Yury Norov 2020-12-13 0:12 ` Yun Levi 0 siblings, 1 reply; 6+ messages in thread From: Yury Norov @ 2020-12-12 18:55 UTC (permalink / raw) To: Yun Levi Cc: dushistov, Arnd Bergmann, Andrew Morton, Gustavo A. R. Silva, William Breathitt Gray, richard.weiyang, Andy Shevchenko, joseph.qi, skalluru, Josh Poimboeuf, Linux Kernel Mailing List On Fri, Dec 11, 2020 at 4:09 PM Yun Levi <ppbuk5246@gmail.com> wrote: > > > I didn't understand why is so (I mean "same", I think you rather talking about > > same order of amount of itterations). > > Yes. That's what I want to talk about. Thanks! > > > Can you provide before and after to compare? > > I tested when the bitmap's 0 bit is set only. and below are before and > after results. > > before: > Start testing find_bit() with random-filled bitmap > [ +0.000481] find_next_bit: 8966 ns, 2 iterations > [ +0.001739] find_next_zero_bit: 1726335 ns, 327679 iterations > [ +0.000020] find_last_bit: 7428 ns, 1 iterations > [ +0.000017] find_first_bit: 5523 ns, 2 iterations > [ +0.000022] find_next_and_bit: 9643 ns, 1 iterations > [ +0.000007] > Start testing find_bit() with sparse bitmap > [ +0.000041] find_next_bit: 16343 ns, 656 iterations > [ +0.001943] find_next_zero_bit: 1928324 ns, 327025 iterations > [ +0.000029] find_last_bit: 14398 ns, 656 iterations > [ +0.000725] find_first_bit: 711383 ns, 656 iterations > [ +0.000022] find_next_and_bit: 9581 ns, 1 iterations > > after: > [Dec12 08:25] > Start testing find_bit() with random-filled bitmap > [ +0.000687] find_next_bit: 11079 ns, 1 iterations > [ +0.002156] find_next_zero_bit: 2055752 ns, 327679 iterations > [ +0.000022] find_last_bit: 8052 ns, 1 iterations > [ +0.000020] find_first_bit: 6270 ns, 1 iterations > [ +0.000024] find_next_and_bit: 9519 ns, 0 iterations > [ +0.000007] > Start testing find_bit() with sparse bitmap > [ +0.000047] find_next_bit: 18389 ns, 655 iterations > [ +0.001807] find_next_zero_bit: 1793314 ns, 327025 iterations > [ +0.000027] find_last_bit: 13600 ns, 655 iterations > [ +0.000604] find_first_bit: 591173 ns, 655 iterations > [ +0.000023] find_next_and_bit: 9392 ns, 0 iterations > find_next_and_bit: 9392 ns, 0 iterations This is definitely wrong. The test simply says that it has parsed the bitmap without actually parsing it. Bollocks. > >I think it's not that important, because the difference is not measurable. > > But if this part raises questions, I have nothing against aligning numbers. > Right it's not that important, But if the amount of iteration value is > not same to the same bitmap, > makes people confused when they run the test cases. so I just fix. Can you please welcome those people to join the discussion? What exactly confuses them? What is their usecase? Will they be satisfied if we add the comment pointing that we count _iterations_, not number of bits? > > What for this check against ++cnt? I doubt that the counter can overflow. > This test case suppose the bitmap size is 327680 (4096UL * 8 * 10) > So I think there is no case that the counter can overflow in the testcase. > > >> time = ktime_get() - time; > >> pr_err("find_first_bit: %18llu ns, %6ld\n", time, cnt); > > Why this? > Sorry, I don't catch what you are saying. > Could you tell me in detail? This change adds useless check against overflow on each iteration. Except that, nothing is changed. We don't need this change, right? > > Can you please confirm that for bitmap 0001, > > test_find_{first,next,next_and}_bit reports cnt == 0, and > > test_find_last_bit() reports 1? > This happens because "test_find_first_bit" calls __clear_bit > in case of bitmap 0001 (only 0 bit set), the test_find_first_bit will > clear the 0 bit > that makes no match with bitmap2 so it reports 0. > > In the view we need to call the find_last_bit or find_next_bit to know > bitmap is empty so cnt should be the 1 in that case, > I think it possible by initializing cnt as 1. Again, we count iterations, not the number of set bits. If you are able to demonstrate that this test counts iterations wrongly, I'll happily accept the fix. Otherwise NACK. Yury > > Do you experience the same problem with find_next_and_bit() as well? > Nope, But compared to other test cases, I think it's better to > integrate their format. > Should I sustain the former one? > > On Sat, Dec 12, 2020 at 2:20 AM Yury Norov <yury.norov@gmail.com> wrote: > > > > On Fri, Dec 11, 2020 at 12:50 AM Levi Yun <ppbuk5246@gmail.com> wrote: > > > > > > We should have same iteration count when we walk the same bitmap > > > regardless of using find_next_bit or find_last_b > > > > I think it's not that important, because the difference is not measurable. > > But if this part raises questions, I have nothing against aligning numbers. > > > > > When we run the find_bit_benchmark.ko, we sometime get > > > unmatched iterations count below: > > > > > > Start testing find_bit() with random-filled bitmap > > > [+...] find_next_bit: 875085 ns, 163755 iterations < > > > [+...] find_next_zero_bit: 865319 ns, 163926 iterations > > > [+...] find_last_bit: 611807 ns, 163756 iterations < > > > [+...] find_first_bit: 1601016 ns, 16335 iterations > > > [+...] find_next_and_bit: 400645 ns, 74040 iterations > > > [+...] > > > Start testing find_bit() with sparse bitmap > > > [+...] find_next_bit: 9942 ns, 654 iterations > > > [+...] find_next_zero_bit: 1678445 ns, 327027 iterations > > > [+...] find_last_bit: 7131 ns, 654 iterations > > > [+...] find_first_bit: 551383 ns, 654 iterations > > > [+...] find_next_and_bit: 3027 ns, 1 iterations > > > > > > Normally, this is happen when the last bit of bitmap was set. > > > > Can you please confirm that for bitmap 0001, > > test_find_{first,next,next_and}_bit reports cnt == 0, and > > test_find_last_bit() reports 1? > > > > > This patch fix the unmatched iterations count between > > > test_find_next_bit and test_find_last_bit. > > > > > > Signed-off-by: Levi Yun <ppbuk5246@gmail.com> > > > --- > > > lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- > > > 1 file changed, 16 insertions(+), 14 deletions(-) > > > > > > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c > > > index 5637c5711db9..766e0487852b 100644 > > > --- a/lib/find_bit_benchmark.c > > > +++ b/lib/find_bit_benchmark.c > > > @@ -35,14 +35,14 @@ static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; > > > */ > > > static int __init test_find_first_bit(void *bitmap, unsigned long len) > > > { > > > - unsigned long i, cnt; > > > + unsigned long i = 0, cnt = 0; > > > ktime_t time; > > > > > > time = ktime_get(); > > > - for (cnt = i = 0; i < len; cnt++) { > > > + do { > > > i = find_first_bit(bitmap, len); > > > __clear_bit(i, bitmap); > > > - } > > > + } while (i++ < len && ++cnt); > > > > What for this check against ++cnt? I doubt that the counter can overflow. > > > > > time = ktime_get() - time; > > > pr_err("find_first_bit: %18llu ns, %6ld\n", time, cnt); > > > > > > @@ -51,12 +51,13 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len) > > > > > > static int __init test_find_next_bit(const void *bitmap, unsigned long len) > > > { > > > - unsigned long i, cnt; > > > + unsigned long i = 0, cnt = 0; > > > ktime_t time; > > > > > > time = ktime_get(); > > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > > - i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; > > > + do { > > > + i = find_next_bit(bitmap, BITMAP_LEN, i); > > > + } while (i++ < BITMAP_LEN && ++cnt); > > > time = ktime_get() - time; > > > pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > @@ -65,12 +66,13 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len) > > > > > > static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) > > > { > > > - unsigned long i, cnt; > > > + unsigned long i = 0, cnt = 0; > > > ktime_t time; > > > > > > time = ktime_get(); > > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > > - i = find_next_zero_bit(bitmap, len, i) + 1; > > > + do { > > > + i = find_next_zero_bit(bitmap, len, i); > > > + } while (i++ < BITMAP_LEN && ++cnt); > > > time = ktime_get() - time; > > > pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > @@ -84,12 +86,11 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > > > > > > time = ktime_get(); > > > do { > > > - cnt++; > > > l = find_last_bit(bitmap, len); > > > if (l >= len) > > > break; > > > len = l; > > > - } while (len); > > > + } while (len >= 0 && ++cnt); > > > > Why this? > > > > > time = ktime_get() - time; > > > pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > @@ -99,12 +100,13 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > > > static int __init test_find_next_and_bit(const void *bitmap, > > > const void *bitmap2, unsigned long len) > > > { > > > - unsigned long i, cnt; > > > + unsigned long i = 0, cnt = 0; > > > ktime_t time; > > > > > > time = ktime_get(); > > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > > - i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); > > > + do { > > > + i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i); > > > + } while (i++ < BITMAP_LEN && ++cnt); > > > > Do you experience the same problem with find_next_and_bit() as well? > > > > > time = ktime_get() - time; > > > pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > -- > > > 2.27.0 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt 2020-12-12 18:55 ` Yury Norov @ 2020-12-13 0:12 ` Yun Levi 0 siblings, 0 replies; 6+ messages in thread From: Yun Levi @ 2020-12-13 0:12 UTC (permalink / raw) To: Yury Norov Cc: dushistov, Arnd Bergmann, Andrew Morton, Gustavo A. R. Silva, William Breathitt Gray, richard.weiyang, Andy Shevchenko, joseph.qi, skalluru, Josh Poimboeuf, Linux Kernel Mailing List > Can you please welcome those people to join the discussion? What exactly > confuses them? What is their usecase? Will they be satisfied if we add > the comment pointing that we count _iterations_, not number of bits? > Again, we count iterations, not the number of set bits. If you are able to > demonstrate that this test counts iterations wrongly, I'll happily > accept the fix. What I want to ask people is that question is it much better to have the same iteration on the same bitmap regardless of the find_next_bit and find_last_bit. At my first thought the benchmark is much easier to be compared if they have the same iteration count regardless of situation. What I mentioned as "confused" is people think one more time when unmatched iteration happens, (divide time by iteration for getting a benchmark..) I don't point out the iteration is wrong but ask if it is much better to have the same iteration count on the same bitmap regardless of find_next_bit and find_last_bit to be compared easier. > This change adds useless check against overflow on each iteration. > Except that, nothing is changed. We don't need this change, right? it is coming from my misunderstanding it should count the number of bits. You're right it adds useless checks thank you. Thanks. Levi. On Sun, Dec 13, 2020 at 3:56 AM Yury Norov <yury.norov@gmail.com> wrote: > > On Fri, Dec 11, 2020 at 4:09 PM Yun Levi <ppbuk5246@gmail.com> wrote: > > > > > I didn't understand why is so (I mean "same", I think you rather talking about > > > same order of amount of itterations). > > > > Yes. That's what I want to talk about. Thanks! > > > > > Can you provide before and after to compare? > > > > I tested when the bitmap's 0 bit is set only. and below are before and > > after results. > > > > before: > > Start testing find_bit() with random-filled bitmap > > [ +0.000481] find_next_bit: 8966 ns, 2 iterations > > [ +0.001739] find_next_zero_bit: 1726335 ns, 327679 iterations > > [ +0.000020] find_last_bit: 7428 ns, 1 iterations > > [ +0.000017] find_first_bit: 5523 ns, 2 iterations > > [ +0.000022] find_next_and_bit: 9643 ns, 1 iterations > > [ +0.000007] > > Start testing find_bit() with sparse bitmap > > [ +0.000041] find_next_bit: 16343 ns, 656 iterations > > [ +0.001943] find_next_zero_bit: 1928324 ns, 327025 iterations > > [ +0.000029] find_last_bit: 14398 ns, 656 iterations > > [ +0.000725] find_first_bit: 711383 ns, 656 iterations > > [ +0.000022] find_next_and_bit: 9581 ns, 1 iterations > > > > after: > > [Dec12 08:25] > > Start testing find_bit() with random-filled bitmap > > [ +0.000687] find_next_bit: 11079 ns, 1 iterations > > [ +0.002156] find_next_zero_bit: 2055752 ns, 327679 iterations > > [ +0.000022] find_last_bit: 8052 ns, 1 iterations > > [ +0.000020] find_first_bit: 6270 ns, 1 iterations > > [ +0.000024] find_next_and_bit: 9519 ns, 0 iterations > > [ +0.000007] > > Start testing find_bit() with sparse bitmap > > [ +0.000047] find_next_bit: 18389 ns, 655 iterations > > [ +0.001807] find_next_zero_bit: 1793314 ns, 327025 iterations > > [ +0.000027] find_last_bit: 13600 ns, 655 iterations > > [ +0.000604] find_first_bit: 591173 ns, 655 iterations > > [ +0.000023] find_next_and_bit: 9392 ns, 0 iterations > > > find_next_and_bit: 9392 ns, 0 iterations > > This is definitely wrong. The test simply says that it has parsed the bitmap > without actually parsing it. Bollocks. > > > >I think it's not that important, because the difference is not measurable. > > > But if this part raises questions, I have nothing against aligning numbers. > > Right it's not that important, But if the amount of iteration value is > > not same to the same bitmap, > > makes people confused when they run the test cases. so I just fix. > > Can you please welcome those people to join the discussion? What exactly > confuses them? What is their usecase? Will they be satisfied if we add > the comment pointing that we count _iterations_, not number of bits? > > > > What for this check against ++cnt? I doubt that the counter can overflow. > > This test case suppose the bitmap size is 327680 (4096UL * 8 * 10) > > So I think there is no case that the counter can overflow in the testcase. > > > > >> time = ktime_get() - time; > > >> pr_err("find_first_bit: %18llu ns, %6ld\n", time, cnt); > > > Why this? > > Sorry, I don't catch what you are saying. > > Could you tell me in detail? > > This change adds useless check against overflow on each iteration. > Except that, nothing is changed. We don't need this change, right? > > > > Can you please confirm that for bitmap 0001, > > > test_find_{first,next,next_and}_bit reports cnt == 0, and > > > test_find_last_bit() reports 1? > > This happens because "test_find_first_bit" calls __clear_bit > > in case of bitmap 0001 (only 0 bit set), the test_find_first_bit will > > clear the 0 bit > > that makes no match with bitmap2 so it reports 0. > > > > In the view we need to call the find_last_bit or find_next_bit to know > > bitmap is empty so cnt should be the 1 in that case, > > I think it possible by initializing cnt as 1. > > Again, we count iterations, not the number of set bits. If you are able to > demonstrate that this test counts iterations wrongly, I'll happily > accept the fix. > Otherwise NACK. > > Yury > > > > Do you experience the same problem with find_next_and_bit() as well? > > Nope, But compared to other test cases, I think it's better to > > integrate their format. > > Should I sustain the former one? > > > > On Sat, Dec 12, 2020 at 2:20 AM Yury Norov <yury.norov@gmail.com> wrote: > > > > > > On Fri, Dec 11, 2020 at 12:50 AM Levi Yun <ppbuk5246@gmail.com> wrote: > > > > > > > > We should have same iteration count when we walk the same bitmap > > > > regardless of using find_next_bit or find_last_b > > > > > > I think it's not that important, because the difference is not measurable. > > > But if this part raises questions, I have nothing against aligning numbers. > > > > > > > When we run the find_bit_benchmark.ko, we sometime get > > > > unmatched iterations count below: > > > > > > > > Start testing find_bit() with random-filled bitmap > > > > [+...] find_next_bit: 875085 ns, 163755 iterations < > > > > [+...] find_next_zero_bit: 865319 ns, 163926 iterations > > > > [+...] find_last_bit: 611807 ns, 163756 iterations < > > > > [+...] find_first_bit: 1601016 ns, 16335 iterations > > > > [+...] find_next_and_bit: 400645 ns, 74040 iterations > > > > [+...] > > > > Start testing find_bit() with sparse bitmap > > > > [+...] find_next_bit: 9942 ns, 654 iterations > > > > [+...] find_next_zero_bit: 1678445 ns, 327027 iterations > > > > [+...] find_last_bit: 7131 ns, 654 iterations > > > > [+...] find_first_bit: 551383 ns, 654 iterations > > > > [+...] find_next_and_bit: 3027 ns, 1 iterations > > > > > > > > Normally, this is happen when the last bit of bitmap was set. > > > > > > Can you please confirm that for bitmap 0001, > > > test_find_{first,next,next_and}_bit reports cnt == 0, and > > > test_find_last_bit() reports 1? > > > > > > > This patch fix the unmatched iterations count between > > > > test_find_next_bit and test_find_last_bit. > > > > > > > > Signed-off-by: Levi Yun <ppbuk5246@gmail.com> > > > > --- > > > > lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- > > > > 1 file changed, 16 insertions(+), 14 deletions(-) > > > > > > > > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c > > > > index 5637c5711db9..766e0487852b 100644 > > > > --- a/lib/find_bit_benchmark.c > > > > +++ b/lib/find_bit_benchmark.c > > > > @@ -35,14 +35,14 @@ static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; > > > > */ > > > > static int __init test_find_first_bit(void *bitmap, unsigned long len) > > > > { > > > > - unsigned long i, cnt; > > > > + unsigned long i = 0, cnt = 0; > > > > ktime_t time; > > > > > > > > time = ktime_get(); > > > > - for (cnt = i = 0; i < len; cnt++) { > > > > + do { > > > > i = find_first_bit(bitmap, len); > > > > __clear_bit(i, bitmap); > > > > - } > > > > + } while (i++ < len && ++cnt); > > > > > > What for this check against ++cnt? I doubt that the counter can overflow. > > > > > > > time = ktime_get() - time; > > > > pr_err("find_first_bit: %18llu ns, %6ld\n", time, cnt); > > > > > > > > @@ -51,12 +51,13 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len) > > > > > > > > static int __init test_find_next_bit(const void *bitmap, unsigned long len) > > > > { > > > > - unsigned long i, cnt; > > > > + unsigned long i = 0, cnt = 0; > > > > ktime_t time; > > > > > > > > time = ktime_get(); > > > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > > > - i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; > > > > + do { > > > > + i = find_next_bit(bitmap, BITMAP_LEN, i); > > > > + } while (i++ < BITMAP_LEN && ++cnt); > > > > time = ktime_get() - time; > > > > pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > > > @@ -65,12 +66,13 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len) > > > > > > > > static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) > > > > { > > > > - unsigned long i, cnt; > > > > + unsigned long i = 0, cnt = 0; > > > > ktime_t time; > > > > > > > > time = ktime_get(); > > > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > > > - i = find_next_zero_bit(bitmap, len, i) + 1; > > > > + do { > > > > + i = find_next_zero_bit(bitmap, len, i); > > > > + } while (i++ < BITMAP_LEN && ++cnt); > > > > time = ktime_get() - time; > > > > pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > > > @@ -84,12 +86,11 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > > > > > > > > time = ktime_get(); > > > > do { > > > > - cnt++; > > > > l = find_last_bit(bitmap, len); > > > > if (l >= len) > > > > break; > > > > len = l; > > > > - } while (len); > > > > + } while (len >= 0 && ++cnt); > > > > > > Why this? > > > > > > > time = ktime_get() - time; > > > > pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > > > @@ -99,12 +100,13 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len) > > > > static int __init test_find_next_and_bit(const void *bitmap, > > > > const void *bitmap2, unsigned long len) > > > > { > > > > - unsigned long i, cnt; > > > > + unsigned long i = 0, cnt = 0; > > > > ktime_t time; > > > > > > > > time = ktime_get(); > > > > - for (cnt = i = 0; i < BITMAP_LEN; cnt++) > > > > - i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); > > > > + do { > > > > + i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i); > > > > + } while (i++ < BITMAP_LEN && ++cnt); > > > > > > Do you experience the same problem with find_next_and_bit() as well? > > > > > > > time = ktime_get() - time; > > > > pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); > > > > > > > > -- > > > > 2.27.0 ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2020-12-13 0:13 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-12-11 8:50 [PATCH] lib/find_bit_bench: fix the unmatched iterations cnt Levi Yun 2020-12-11 16:11 ` Andy Shevchenko 2020-12-11 17:20 ` Yury Norov 2020-12-12 0:09 ` Yun Levi 2020-12-12 18:55 ` Yury Norov 2020-12-13 0:12 ` Yun Levi
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).