lib/find_bit_bench: fix the unmatched iterations cnt
Subsystems (2)
PATCH 1/1 lib/find_bit_bench: fix the unmatched iterations cnt
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.
--- lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-)
lib/find_bit_benchmark.c +16 -14
@@ -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);
Signature · 1 line
2.27.0
Quoted 2 lines · Levi Yun
We should have same iteration count when we walk the same bitmap regardless of using
find_next_bitorfind_last_bit.
I didn't understand why is so (I mean "same", I think you rather talking about same order of amount of itterations).
Quoted 17 lines
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 testingfind_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
Quoted 4 lines
Normally, this is happen when the last bit of bitmap was set.
This patch fix the unmatched iterations count between
test_find_next_bitandtest_find_last_bit.
Can you provide before and after to compare?
Signature · 2 lines
With Best Regards, Andy Shevchenko
Yury Norov
maintainerQuoted 3 lines · Levi Yun
We should have same iteration count when we walk the same bitmap regardless of using
find_next_bitorfind_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.
Quoted 17 lines
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 testingfind_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
Quoted 1 line
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?
Quoted 17 lines
This patch fix the unmatched iterations count between
test_find_next_bitandtest_find_last_bit.Signed-off-by Levi Yun <[email protected]>--- lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-)lib/find_bit_benchmark.c +0
-1@@ -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;
lib/find_bit_benchmark.c static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; · line 45
Quoted 10 lines
lib/find_bit_benchmark.c +3
-2+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.
Quoted 38 lines
lib/find_bit_benchmark.c +8
-6time =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);
lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 93
Quoted 10 lines
lib/find_bit_benchmark.c +1
-2@@ -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?
Quoted 7 lines
lib/find_bit_benchmark.c +0
-0time =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) {
lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 109
Quoted 10 lines
lib/find_bit_benchmark.c +4
-3-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?
Quoted 5 lines
lib/find_bit_benchmark.c +0
-1time =ktime_get () - time;pr_err ("find_next_and_bit: %18llu ns, %6ld iterations\n" , time, cnt); --2.27.0
Quoted 2 lines
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!
Quoted 1 line
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 iterationsafter:
[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 iterationsQuoted 2 lines
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.
Quoted 1 line
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.
Quoted 3 lines
Quoted 2 lines
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?
Quoted 3 lines
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.
Quoted 1 line
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?
Quoted 138 lines · Yury Norov
Quoted 3 lines · Levi Yun
We should have same iteration count when we walk the same bitmap regardless of using
find_next_bitorfind_last_bI think it's not that important, because the difference is not measurable. But if this part raises questions, I have nothing against aligning numbers.
Quoted 17 lines
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 testingfind_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 iterationsQuoted 1 line
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?Quoted 17 lines
This patch fix the unmatched iterations count between
test_find_next_bitandtest_find_last_bit.Signed-off-by Levi Yun <[email protected]>--- lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-)lib/find_bit_benchmark.c +0
-1@@ -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;lib/find_bit_benchmark.c static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; · line 45
Quoted 10 lines
lib/find_bit_benchmark.c +3
-2+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.
Quoted 38 lines
lib/find_bit_benchmark.c +8
-6time =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);lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 93
Quoted 10 lines
lib/find_bit_benchmark.c +1
-2@@ -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?
Quoted 7 lines
lib/find_bit_benchmark.c +0
-0time =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) {lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 109
Quoted 10 lines
lib/find_bit_benchmark.c +4
-3-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?Quoted 5 lines
lib/find_bit_benchmark.c +0
-1time =ktime_get () - time;pr_err ("find_next_and_bit: %18llu ns, %6ld iterations\n" , time, cnt); --2.27.0
Yury Norov
maintainerQuoted 42 lines · Yun Levi
Quoted 3 lines
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!
Quoted 1 line
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 testingfind_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 iterationsafter:
[Dec12 08:25]
Start testingfind_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
Quoted 1 line
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.
Quoted 5 lines
Quoted 2 lines
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?
Quoted 9 lines
Quoted 1 line
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.
Quoted 3 lines
Quoted 2 lines
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?
Quoted 11 lines
Quoted 3 lines
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_bitin case of bitmap 0001 (only 0 bit set), thetest_find_first_bitwill clear the 0 bit
that makes no match with bitmap2 so it reports 0.In the view we need to call the
find_last_bitorfind_next_bitto 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
Quoted 144 lines
Quoted 1 line
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?Quoted 138 lines · Yury Norov
Quoted 3 lines · Levi Yun
We should have same iteration count when we walk the same bitmap regardless of using
find_next_bitorfind_last_bI think it's not that important, because the difference is not measurable. But if this part raises questions, I have nothing against aligning numbers.
Quoted 17 lines
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 testingfind_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 iterationsQuoted 1 line
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?Quoted 17 lines
This patch fix the unmatched iterations count between
test_find_next_bitandtest_find_last_bit.Signed-off-by Levi Yun <[email protected]>--- lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-)lib/find_bit_benchmark.c +0
-1@@ -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;lib/find_bit_benchmark.c static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; · line 45
Quoted 10 lines
lib/find_bit_benchmark.c +3
-2+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.
Quoted 38 lines
lib/find_bit_benchmark.c +8
-6time =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);lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 93
Quoted 10 lines
lib/find_bit_benchmark.c +1
-2@@ -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?
Quoted 7 lines
lib/find_bit_benchmark.c +0
-0time =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) {lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 109
Quoted 10 lines
lib/find_bit_benchmark.c +4
-3-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?Quoted 5 lines
lib/find_bit_benchmark.c +0
-1time =ktime_get () - time;pr_err ("find_next_and_bit: %18llu ns, %6ld iterations\n" , time, cnt); --2.27.0
Quoted 7 lines
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.
Quoted 2 lines
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.
Quoted 235 lines · Yury Norov
Quoted 42 lines · Yun Levi
Quoted 3 lines
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!
Quoted 1 line
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 testingfind_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 iterationsafter:
[Dec12 08:25]
Start testingfind_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 iterationsQuoted 1 line
find_next_and_bit: 9392 ns, 0 iterationsThis is definitely wrong. The test simply says that it has parsed the bitmap without actually parsing it. Bollocks.
Quoted 5 lines
Quoted 2 lines
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?
Quoted 9 lines
Quoted 1 line
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.
Quoted 3 lines
Quoted 2 lines
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?
Quoted 11 lines
Quoted 3 lines
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_bitin case of bitmap 0001 (only 0 bit set), thetest_find_first_bitwill clear the 0 bit
that makes no match with bitmap2 so it reports 0.In the view we need to call the
find_last_bitorfind_next_bitto 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
Quoted 144 lines
Quoted 1 line
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?Quoted 138 lines · Yury Norov
Quoted 3 lines · Levi Yun
We should have same iteration count when we walk the same bitmap regardless of using
find_next_bitorfind_last_bI think it's not that important, because the difference is not measurable. But if this part raises questions, I have nothing against aligning numbers.
Quoted 17 lines
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 testingfind_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 iterationsQuoted 1 line
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?Quoted 17 lines
This patch fix the unmatched iterations count between
test_find_next_bitandtest_find_last_bit.Signed-off-by Levi Yun <[email protected]>--- lib/find_bit_benchmark.c | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-)lib/find_bit_benchmark.c +0
-1@@ -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;lib/find_bit_benchmark.c static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; · line 45
Quoted 10 lines
lib/find_bit_benchmark.c +3
-2+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.
Quoted 38 lines
lib/find_bit_benchmark.c +8
-6time =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);lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 93
Quoted 10 lines
lib/find_bit_benchmark.c +1
-2@@ -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?
Quoted 7 lines
lib/find_bit_benchmark.c +0
-0time =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) {lib/find_bit_benchmark.c static int __init test_find_last_bit(const void *bitmap, unsigned long len) · line 109
Quoted 10 lines
lib/find_bit_benchmark.c +4
-3-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?Quoted 5 lines
lib/find_bit_benchmark.c +0
-1time =ktime_get () - time;pr_err ("find_next_and_bit: %18llu ns, %6ld iterations\n" , time, cnt); --2.27.0