Re: [PATCH] lib: test module for find_*_bit() functions

[Geert Uytterhoeven]

Hi Yury,

On Fri, Nov 24, 2017 at 3:30 PM, Yury Norov  wrote:
> Below the updates proposed in this thread.

Thank you!

> From 959700bd7e7f586171c15a4130a9888acac02daf Mon Sep 17 00:00:00 2001
> From: Yury Norov 
> Date: Wed, 22 Nov 2017 17:21:40 +0300
> Subject: [PATCH] improve lib/test_find_bit
>
> As suggested in review comments:
> * printk: align numbers using whitespaces instead of tabs;
> * return error value from init() to avoid calling rmmod if testing again;
> * use ktime_get instead of get_cycles as some arches don't support it;
> * rename test_find_bit.c to find_bit_benchmark.c.
>
> The output in dmesg (on QEMU arm64):
> [   38.823430] Start testing find_bit() with random-filled bitmap
> [   38.845358] find_next_bit:20138448 ns, 163968 iterations
> [   38.856217] find_next_zero_bit:   10615328 ns, 163713 iterations
> [   38.863564] find_last_bit: 7111888 ns, 163967 iterations
> [   40.944796] find_first_bit: 2081007216 ns, 163968 iterations
> [   40.944975]
> [   40.944975] Start testing find_bit() with sparse bitmap
> [   40.945268] find_next_bit:   73216 ns,656 iterations
> [   40.967858] find_next_zero_bit:   22461008 ns, 327025 iterations
> [   40.968047] find_last_bit:   62320 ns,656 iterations
> [   40.978060] find_first_bit:9889360 ns,656 iterations
>
> Signed-off-by: Yury Norov 

Tested-by: Geert Uytterhoeven 

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- ge...@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

Re: [PATCH] lib: test module for find_*_bit() functions

[Geert Uytterhoeven]

Hi Yury,

On Fri, Nov 24, 2017 at 3:30 PM, Yury Norov  wrote:
> Below the updates proposed in this thread.

Thank you!

> From 959700bd7e7f586171c15a4130a9888acac02daf Mon Sep 17 00:00:00 2001
> From: Yury Norov 
> Date: Wed, 22 Nov 2017 17:21:40 +0300
> Subject: [PATCH] improve lib/test_find_bit
>
> As suggested in review comments:
> * printk: align numbers using whitespaces instead of tabs;
> * return error value from init() to avoid calling rmmod if testing again;
> * use ktime_get instead of get_cycles as some arches don't support it;
> * rename test_find_bit.c to find_bit_benchmark.c.
>
> The output in dmesg (on QEMU arm64):
> [   38.823430] Start testing find_bit() with random-filled bitmap
> [   38.845358] find_next_bit:20138448 ns, 163968 iterations
> [   38.856217] find_next_zero_bit:   10615328 ns, 163713 iterations
> [   38.863564] find_last_bit: 7111888 ns, 163967 iterations
> [   40.944796] find_first_bit: 2081007216 ns, 163968 iterations
> [   40.944975]
> [   40.944975] Start testing find_bit() with sparse bitmap
> [   40.945268] find_next_bit:   73216 ns,656 iterations
> [   40.967858] find_next_zero_bit:   22461008 ns, 327025 iterations
> [   40.968047] find_last_bit:   62320 ns,656 iterations
> [   40.978060] find_first_bit:9889360 ns,656 iterations
>
> Signed-off-by: Yury Norov 

Tested-by: Geert Uytterhoeven 

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- ge...@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

Re: [PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

Hi Geert, all

Below the updates proposed in this thread.

Yury


>From 959700bd7e7f586171c15a4130a9888acac02daf Mon Sep 17 00:00:00 2001
From: Yury Norov 
Date: Wed, 22 Nov 2017 17:21:40 +0300
Subject: [PATCH] improve lib/test_find_bit

As suggested in review comments:
* printk: align numbers using whitespaces instead of tabs;
* return error value from init() to avoid calling rmmod if testing again;
* use ktime_get instead of get_cycles as some arches don't support it;
* rename test_find_bit.c to find_bit_benchmark.c.

The output in dmesg (on QEMU arm64):
[   38.823430] Start testing find_bit() with random-filled bitmap
[   38.845358] find_next_bit:20138448 ns, 163968 iterations
[   38.856217] find_next_zero_bit:   10615328 ns, 163713 iterations
[   38.863564] find_last_bit: 7111888 ns, 163967 iterations
[   40.944796] find_first_bit: 2081007216 ns, 163968 iterations
[   40.944975]
[   40.944975] Start testing find_bit() with sparse bitmap
[   40.945268] find_next_bit:   73216 ns,656 iterations
[   40.967858] find_next_zero_bit:   22461008 ns, 327025 iterations
[   40.968047] find_last_bit:   62320 ns,656 iterations
[   40.978060] find_first_bit:9889360 ns,656 iterations

Signed-off-by: Yury Norov 
---
 lib/Kconfig.debug |  2 +-
 lib/Makefile  |  2 +-
 lib/{test_find_bit.c => find_bit_benchmark.c} | 47 ---
 3 files changed, 23 insertions(+), 28 deletions(-)
 rename lib/{test_find_bit.c => find_bit_benchmark.c} (79%)

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 138034cc68a3..1c57c36ad79a 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1838,7 +1838,7 @@ config TEST_BPF
 
  If unsure, say N.
 
-config TEST_FIND_BIT
+config FIND_BIT_BENCHMARK
tristate "Test find_bit functions"
default n
help
diff --git a/lib/Makefile b/lib/Makefile
index 97ec69d843f2..1688cc84536e 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -45,8 +45,8 @@ obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
 obj-y += hexdump.o
 obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
+obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
-obj-$(CONFIG_TEST_FIND_BIT) += test_find_bit.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
 obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o
 obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
diff --git a/lib/test_find_bit.c b/lib/find_bit_benchmark.c
similarity index 79%
rename from lib/test_find_bit.c
rename to lib/find_bit_benchmark.c
index f4394a36f9aa..67b19233c28f 100644
--- a/lib/test_find_bit.c
+++ b/lib/find_bit_benchmark.c
@@ -43,16 +43,15 @@ static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
 static int __init test_find_first_bit(void *bitmap, unsigned long len)
 {
unsigned long i, cnt;
-   cycles_t cycles;
+   ktime_t time;
 
-   cycles = get_cycles();
+   time = ktime_get();
for (cnt = i = 0; i < len; cnt++) {
i = find_first_bit(bitmap, len);
__clear_bit(i, bitmap);
}
-   cycles = get_cycles() - cycles;
-   pr_err("find_first_bit:\t\t%llu cycles,\t%ld iterations\n",
-  (u64)cycles, cnt);
+   time = ktime_get() - time;
+   pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt);
 
return 0;
 }
@@ -60,14 +59,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;
-   cycles_t cycles;
+   ktime_t time;
 
-   cycles = get_cycles();
+   time = ktime_get();
for (cnt = i = 0; i < BITMAP_LEN; cnt++)
i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
-   cycles = get_cycles() - cycles;
-   pr_err("find_next_bit:\t\t%llu cycles,\t%ld iterations\n",
-  (u64)cycles, cnt);
+   time = ktime_get() - time;
+   pr_err("find_next_bit:  %18llu ns, %6ld iterations\n", time, cnt);
 
return 0;
 }
@@ -75,14 +73,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;
-   cycles_t cycles;
+   ktime_t time;
 
-   cycles = get_cycles();
+   time = ktime_get();
for (cnt = i = 0; i < BITMAP_LEN; cnt++)
i = find_next_zero_bit(bitmap, len, i) + 1;
-   cycles = get_cycles() - cycles;
-   pr_err("find_next_zero_bit:\t%llu cycles,\t%ld iterations\n",
-  (u64)cycles, cnt);
+   time = ktime_get() - time;
+   pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
 
return 0;
 }
@@ -90,9 +87,9 @@ static int 

Re: [PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

Hi Geert, all

Below the updates proposed in this thread.

Yury


>From 959700bd7e7f586171c15a4130a9888acac02daf Mon Sep 17 00:00:00 2001
From: Yury Norov 
Date: Wed, 22 Nov 2017 17:21:40 +0300
Subject: [PATCH] improve lib/test_find_bit

As suggested in review comments:
* printk: align numbers using whitespaces instead of tabs;
* return error value from init() to avoid calling rmmod if testing again;
* use ktime_get instead of get_cycles as some arches don't support it;
* rename test_find_bit.c to find_bit_benchmark.c.

The output in dmesg (on QEMU arm64):
[   38.823430] Start testing find_bit() with random-filled bitmap
[   38.845358] find_next_bit:20138448 ns, 163968 iterations
[   38.856217] find_next_zero_bit:   10615328 ns, 163713 iterations
[   38.863564] find_last_bit: 7111888 ns, 163967 iterations
[   40.944796] find_first_bit: 2081007216 ns, 163968 iterations
[   40.944975]
[   40.944975] Start testing find_bit() with sparse bitmap
[   40.945268] find_next_bit:   73216 ns,656 iterations
[   40.967858] find_next_zero_bit:   22461008 ns, 327025 iterations
[   40.968047] find_last_bit:   62320 ns,656 iterations
[   40.978060] find_first_bit:9889360 ns,656 iterations

Signed-off-by: Yury Norov 
---
 lib/Kconfig.debug |  2 +-
 lib/Makefile  |  2 +-
 lib/{test_find_bit.c => find_bit_benchmark.c} | 47 ---
 3 files changed, 23 insertions(+), 28 deletions(-)
 rename lib/{test_find_bit.c => find_bit_benchmark.c} (79%)

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 138034cc68a3..1c57c36ad79a 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1838,7 +1838,7 @@ config TEST_BPF
 
  If unsure, say N.
 
-config TEST_FIND_BIT
+config FIND_BIT_BENCHMARK
tristate "Test find_bit functions"
default n
help
diff --git a/lib/Makefile b/lib/Makefile
index 97ec69d843f2..1688cc84536e 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -45,8 +45,8 @@ obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
 obj-y += hexdump.o
 obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
+obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
-obj-$(CONFIG_TEST_FIND_BIT) += test_find_bit.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
 obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o
 obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
diff --git a/lib/test_find_bit.c b/lib/find_bit_benchmark.c
similarity index 79%
rename from lib/test_find_bit.c
rename to lib/find_bit_benchmark.c
index f4394a36f9aa..67b19233c28f 100644
--- a/lib/test_find_bit.c
+++ b/lib/find_bit_benchmark.c
@@ -43,16 +43,15 @@ static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
 static int __init test_find_first_bit(void *bitmap, unsigned long len)
 {
unsigned long i, cnt;
-   cycles_t cycles;
+   ktime_t time;
 
-   cycles = get_cycles();
+   time = ktime_get();
for (cnt = i = 0; i < len; cnt++) {
i = find_first_bit(bitmap, len);
__clear_bit(i, bitmap);
}
-   cycles = get_cycles() - cycles;
-   pr_err("find_first_bit:\t\t%llu cycles,\t%ld iterations\n",
-  (u64)cycles, cnt);
+   time = ktime_get() - time;
+   pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt);
 
return 0;
 }
@@ -60,14 +59,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;
-   cycles_t cycles;
+   ktime_t time;
 
-   cycles = get_cycles();
+   time = ktime_get();
for (cnt = i = 0; i < BITMAP_LEN; cnt++)
i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
-   cycles = get_cycles() - cycles;
-   pr_err("find_next_bit:\t\t%llu cycles,\t%ld iterations\n",
-  (u64)cycles, cnt);
+   time = ktime_get() - time;
+   pr_err("find_next_bit:  %18llu ns, %6ld iterations\n", time, cnt);
 
return 0;
 }
@@ -75,14 +73,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;
-   cycles_t cycles;
+   ktime_t time;
 
-   cycles = get_cycles();
+   time = ktime_get();
for (cnt = i = 0; i < BITMAP_LEN; cnt++)
i = find_next_zero_bit(bitmap, len, i) + 1;
-   cycles = get_cycles() - cycles;
-   pr_err("find_next_zero_bit:\t%llu cycles,\t%ld iterations\n",
-  (u64)cycles, cnt);
+   time = ktime_get() - time;
+   pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
 
return 0;
 }
@@ -90,9 +87,9 @@ static int __init test_find_next_zero_bit(const void *bitmap, 

Re: [PATCH] lib: test module for find_*_bit() functions

[Geert Uytterhoeven]

Hi Yury,

On Thu, Nov 9, 2017 at 3:07 PM, Yury Norov  wrote:
> find_bit functions are widely used in the kernel, including hot paths.
> This module tests performance of that functions in 2 typical scenarios:
> randomly filled bitmap with relatively equal distribution of set and
> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.

Thanks for your patch!

> On ThunderX machine:
>
>  Start testing find_bit() with random-filled bitmap
> [1032111.632383] find_next_bit: 240043 cycles,  164062 iterations
> [1032111.647236] find_next_zero_bit:312848 cycles,  163619 iterations
> [1032111.661585] find_last_bit: 193748 cycles,  164062 iterations
> [1032113.450517] find_first_bit:177720874 cycles,   164062 
> iterations
> [1032113.462930]
>  Start testing find_bit() with sparse bitmap
> [1032113.477229] find_next_bit: 3633 cycles,656 iterations
> [1032113.494281] find_next_zero_bit:620399 cycles,  327025 iterations
> [1032113.506723] find_last_bit: 3038 cycles,656 iterations
> [1032113.524485] find_first_bit:691407 cycles,  656 iterations

That's what ends up in dmesg, but that's not what it prints on the console:
"\t" prints an ugly placeholder, as TABs are not supported.

> --- /dev/null
> +++ b/lib/test_find_bit.c
> @@ -0,0 +1,141 @@

> +static int __init test_find_first_bit(void *bitmap, unsigned long len)
> +{
> +   unsigned long i, cnt;
> +   cycles_t cycles;
> +
> +   cycles = get_cycles();

get_cycles() returns zero on half of the architectures.

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- ge...@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

Re: [PATCH] lib: test module for find_*_bit() functions

[Geert Uytterhoeven]

Hi Yury,

On Thu, Nov 9, 2017 at 3:07 PM, Yury Norov  wrote:
> find_bit functions are widely used in the kernel, including hot paths.
> This module tests performance of that functions in 2 typical scenarios:
> randomly filled bitmap with relatively equal distribution of set and
> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.

Thanks for your patch!

> On ThunderX machine:
>
>  Start testing find_bit() with random-filled bitmap
> [1032111.632383] find_next_bit: 240043 cycles,  164062 iterations
> [1032111.647236] find_next_zero_bit:312848 cycles,  163619 iterations
> [1032111.661585] find_last_bit: 193748 cycles,  164062 iterations
> [1032113.450517] find_first_bit:177720874 cycles,   164062 
> iterations
> [1032113.462930]
>  Start testing find_bit() with sparse bitmap
> [1032113.477229] find_next_bit: 3633 cycles,656 iterations
> [1032113.494281] find_next_zero_bit:620399 cycles,  327025 iterations
> [1032113.506723] find_last_bit: 3038 cycles,656 iterations
> [1032113.524485] find_first_bit:691407 cycles,  656 iterations

That's what ends up in dmesg, but that's not what it prints on the console:
"\t" prints an ugly placeholder, as TABs are not supported.

> --- /dev/null
> +++ b/lib/test_find_bit.c
> @@ -0,0 +1,141 @@

> +static int __init test_find_first_bit(void *bitmap, unsigned long len)
> +{
> +   unsigned long i, cnt;
> +   cycles_t cycles;
> +
> +   cycles = get_cycles();

get_cycles() returns zero on half of the architectures.

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- ge...@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

Re: [PATCH] lib: test module for find_*_bit() functions

[Andrew Morton]

On Tue, 14 Nov 2017 13:07:30 +0300 Yury Norov  wrote:

> > Yyra, you can grab CONFIG_BENCHMARK_* namespace :-)
>  
> There's no CONFIG_BENCHMARK_* namespace actually.

Alexey means you can be the first user of CONFIG_BENCHMARK_*.

> The 'CONFIG_*_BENCHMARK' is
> referenced only 3 times in linux sources - CONFIG_RING_BUFFER_BENCHMARK,
> CONFIG_TRACEPOINT_BENCHMARK and CONFIG_GUP_BENCHMARK, so I simply didn't know
> about it. Some other tests like lib/rbtree_test.c also measure performance and
> use TEST namespace, but if you think it's better, I don't object to change it.
>  
> > Another thing:
> > 
> > > +
> > > +   return 0;
> > > +}
> > > +module_init(find_bit_test);
> > > +
> > > +static void __exit test_find_bit_cleanup(void)
> > > +{
> > > +}
> > > +module_exit(test_find_bit_cleanup);
> > 
> > module exit hook is entirely unnecessary as you can return -E from init 
> > hook.
> > See lib/test-kstrtox.c
> 
> Ack. 
> 
> I thought to send v3, but the patch is already in next tree, so I'll
> send fix in separated patch. OK?

Either approach is OK.

Re: [PATCH] lib: test module for find_*_bit() functions

[Andrew Morton]

On Tue, 14 Nov 2017 13:07:30 +0300 Yury Norov  wrote:

> > Yyra, you can grab CONFIG_BENCHMARK_* namespace :-)
>  
> There's no CONFIG_BENCHMARK_* namespace actually.

Alexey means you can be the first user of CONFIG_BENCHMARK_*.

> The 'CONFIG_*_BENCHMARK' is
> referenced only 3 times in linux sources - CONFIG_RING_BUFFER_BENCHMARK,
> CONFIG_TRACEPOINT_BENCHMARK and CONFIG_GUP_BENCHMARK, so I simply didn't know
> about it. Some other tests like lib/rbtree_test.c also measure performance and
> use TEST namespace, but if you think it's better, I don't object to change it.
>  
> > Another thing:
> > 
> > > +
> > > +   return 0;
> > > +}
> > > +module_init(find_bit_test);
> > > +
> > > +static void __exit test_find_bit_cleanup(void)
> > > +{
> > > +}
> > > +module_exit(test_find_bit_cleanup);
> > 
> > module exit hook is entirely unnecessary as you can return -E from init 
> > hook.
> > See lib/test-kstrtox.c
> 
> Ack. 
> 
> I thought to send v3, but the patch is already in next tree, so I'll
> send fix in separated patch. OK?

Either approach is OK.

Re: [PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

Hi Michael,

On Sun, Nov 12, 2017 at 10:33:55PM +1100, Michael Ellerman wrote:
> Yury Norov  writes:
> 
> > find_bit functions are widely used in the kernel, including hot paths.
> > This module tests performance of that functions in 2 typical scenarios:
> > randomly filled bitmap with relatively equal distribution of set and
> > cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
> >
> > On ThunderX machine:
> >
> >  Start testing find_bit() with random-filled bitmap
> > [1032111.632383] find_next_bit: 240043 cycles,  164062 
> > iterations
> > [1032111.647236] find_next_zero_bit:312848 cycles,  163619 
> > iterations
> > [1032111.661585] find_last_bit: 193748 cycles,  164062 
> > iterations
> > [1032113.450517] find_first_bit:177720874 cycles,   164062 
> > iterations
> > [1032113.462930]
> >  Start testing find_bit() with sparse bitmap
> > [1032113.477229] find_next_bit: 3633 cycles,656 iterations
> > [1032113.494281] find_next_zero_bit:620399 cycles,  327025 
> > iterations
> > [1032113.506723] find_last_bit: 3038 cycles,656 iterations
> > [1032113.524485] find_first_bit:691407 cycles,  656 iterations
> 
> Have you thought about timing it rather than using get_cycles()?
> 
> get_cycles() has the downside that it can't be compared across different
> architectures or even platforms within an architecture.

This test is written to benchmark find_bit() on the same target if algorithm
is changed. Comparing different architectures looks problematic anyway.

Different architectures may have different clock rates, and even implementations
of the function, like ARM. And many CPUs support dynamic changing of CPU speed
which will directly affect time of execution. So I don't think that direct
comparison of time across platforms would be informative without additional
precautions.

Also, other tests, like lib/interval_tree_test.c or lib/rbtree_test.c print
get_cycles() where they need to estimate performance, and it looks like common
practice.

Do you have real usecase for it?

Yury

Re: [PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

Hi Michael,

On Sun, Nov 12, 2017 at 10:33:55PM +1100, Michael Ellerman wrote:
> Yury Norov  writes:
> 
> > find_bit functions are widely used in the kernel, including hot paths.
> > This module tests performance of that functions in 2 typical scenarios:
> > randomly filled bitmap with relatively equal distribution of set and
> > cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
> >
> > On ThunderX machine:
> >
> >  Start testing find_bit() with random-filled bitmap
> > [1032111.632383] find_next_bit: 240043 cycles,  164062 
> > iterations
> > [1032111.647236] find_next_zero_bit:312848 cycles,  163619 
> > iterations
> > [1032111.661585] find_last_bit: 193748 cycles,  164062 
> > iterations
> > [1032113.450517] find_first_bit:177720874 cycles,   164062 
> > iterations
> > [1032113.462930]
> >  Start testing find_bit() with sparse bitmap
> > [1032113.477229] find_next_bit: 3633 cycles,656 iterations
> > [1032113.494281] find_next_zero_bit:620399 cycles,  327025 
> > iterations
> > [1032113.506723] find_last_bit: 3038 cycles,656 iterations
> > [1032113.524485] find_first_bit:691407 cycles,  656 iterations
> 
> Have you thought about timing it rather than using get_cycles()?
> 
> get_cycles() has the downside that it can't be compared across different
> architectures or even platforms within an architecture.

This test is written to benchmark find_bit() on the same target if algorithm
is changed. Comparing different architectures looks problematic anyway.

Different architectures may have different clock rates, and even implementations
of the function, like ARM. And many CPUs support dynamic changing of CPU speed
which will directly affect time of execution. So I don't think that direct
comparison of time across platforms would be informative without additional
precautions.

Also, other tests, like lib/interval_tree_test.c or lib/rbtree_test.c print
get_cycles() where they need to estimate performance, and it looks like common
practice.

Do you have real usecase for it?

Yury

Re: [PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

Hi Alexey, Andrew,

Thanks for comments.

On Fri, Nov 10, 2017 at 12:45:18PM +0200, Alexey Dobriyan wrote:
> On 11/10/17, Andrew Morton  wrote:
> > On Thu,  9 Nov 2017 17:07:14 +0300 Yury Norov 
> > wrote:
> >
> >> find_bit functions are widely used in the kernel, including hot paths.
> >> This module tests performance of that functions in 2 typical scenarios:
> >> randomly filled bitmap with relatively equal distribution of set and
> >> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
> >>
> >> ...
> >>
> >> +config TEST_FIND_BIT
> >
> > Well.  It doesn't actually "test" the code.  It measures its performance ;)
> 
> Yes!
> 
> Yyra, you can grab CONFIG_BENCHMARK_* namespace :-)
 
There's no CONFIG_BENCHMARK_* namespace actually. The 'CONFIG_*_BENCHMARK' is
referenced only 3 times in linux sources - CONFIG_RING_BUFFER_BENCHMARK,
CONFIG_TRACEPOINT_BENCHMARK and CONFIG_GUP_BENCHMARK, so I simply didn't know
about it. Some other tests like lib/rbtree_test.c also measure performance and
use TEST namespace, but if you think it's better, I don't object to change it.
 
> Another thing:
> 
> > +
> > +   return 0;
> > +}
> > +module_init(find_bit_test);
> > +
> > +static void __exit test_find_bit_cleanup(void)
> > +{
> > +}
> > +module_exit(test_find_bit_cleanup);
> 
> module exit hook is entirely unnecessary as you can return -E from init hook.
> See lib/test-kstrtox.c

Ack. 

I thought to send v3, but the patch is already in next tree, so I'll
send fix in separated patch. OK?

Yury

Re: [PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

Hi Alexey, Andrew,

Thanks for comments.

On Fri, Nov 10, 2017 at 12:45:18PM +0200, Alexey Dobriyan wrote:
> On 11/10/17, Andrew Morton  wrote:
> > On Thu,  9 Nov 2017 17:07:14 +0300 Yury Norov 
> > wrote:
> >
> >> find_bit functions are widely used in the kernel, including hot paths.
> >> This module tests performance of that functions in 2 typical scenarios:
> >> randomly filled bitmap with relatively equal distribution of set and
> >> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
> >>
> >> ...
> >>
> >> +config TEST_FIND_BIT
> >
> > Well.  It doesn't actually "test" the code.  It measures its performance ;)
> 
> Yes!
> 
> Yyra, you can grab CONFIG_BENCHMARK_* namespace :-)
 
There's no CONFIG_BENCHMARK_* namespace actually. The 'CONFIG_*_BENCHMARK' is
referenced only 3 times in linux sources - CONFIG_RING_BUFFER_BENCHMARK,
CONFIG_TRACEPOINT_BENCHMARK and CONFIG_GUP_BENCHMARK, so I simply didn't know
about it. Some other tests like lib/rbtree_test.c also measure performance and
use TEST namespace, but if you think it's better, I don't object to change it.
 
> Another thing:
> 
> > +
> > +   return 0;
> > +}
> > +module_init(find_bit_test);
> > +
> > +static void __exit test_find_bit_cleanup(void)
> > +{
> > +}
> > +module_exit(test_find_bit_cleanup);
> 
> module exit hook is entirely unnecessary as you can return -E from init hook.
> See lib/test-kstrtox.c

Ack. 

I thought to send v3, but the patch is already in next tree, so I'll
send fix in separated patch. OK?

Yury

Re: [PATCH] lib: test module for find_*_bit() functions

[Michael Ellerman]

Yury Norov  writes:

> find_bit functions are widely used in the kernel, including hot paths.
> This module tests performance of that functions in 2 typical scenarios:
> randomly filled bitmap with relatively equal distribution of set and
> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
>
> On ThunderX machine:
>
>Start testing find_bit() with random-filled bitmap
> [1032111.632383] find_next_bit:   240043 cycles,  164062 
> iterations
> [1032111.647236] find_next_zero_bit:  312848 cycles,  163619 iterations
> [1032111.661585] find_last_bit:   193748 cycles,  164062 
> iterations
> [1032113.450517] find_first_bit:  177720874 cycles,   164062 
> iterations
> [1032113.462930]
>Start testing find_bit() with sparse bitmap
> [1032113.477229] find_next_bit:   3633 cycles,656 iterations
> [1032113.494281] find_next_zero_bit:  620399 cycles,  327025 iterations
> [1032113.506723] find_last_bit:   3038 cycles,656 iterations
> [1032113.524485] find_first_bit:  691407 cycles,  656 iterations

Have you thought about timing it rather than using get_cycles()?

get_cycles() has the downside that it can't be compared across different
architectures or even platforms within an architecture.

cheers

Re: [PATCH] lib: test module for find_*_bit() functions

[Michael Ellerman]

Yury Norov  writes:

> find_bit functions are widely used in the kernel, including hot paths.
> This module tests performance of that functions in 2 typical scenarios:
> randomly filled bitmap with relatively equal distribution of set and
> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
>
> On ThunderX machine:
>
>Start testing find_bit() with random-filled bitmap
> [1032111.632383] find_next_bit:   240043 cycles,  164062 
> iterations
> [1032111.647236] find_next_zero_bit:  312848 cycles,  163619 iterations
> [1032111.661585] find_last_bit:   193748 cycles,  164062 
> iterations
> [1032113.450517] find_first_bit:  177720874 cycles,   164062 
> iterations
> [1032113.462930]
>Start testing find_bit() with sparse bitmap
> [1032113.477229] find_next_bit:   3633 cycles,656 iterations
> [1032113.494281] find_next_zero_bit:  620399 cycles,  327025 iterations
> [1032113.506723] find_last_bit:   3038 cycles,656 iterations
> [1032113.524485] find_first_bit:  691407 cycles,  656 iterations

Have you thought about timing it rather than using get_cycles()?

get_cycles() has the downside that it can't be compared across different
architectures or even platforms within an architecture.

cheers

Re: [PATCH] lib: test module for find_*_bit() functions

[Alexey Dobriyan]

On 11/10/17, Andrew Morton  wrote:
> On Thu,  9 Nov 2017 17:07:14 +0300 Yury Norov 
> wrote:
>
>> find_bit functions are widely used in the kernel, including hot paths.
>> This module tests performance of that functions in 2 typical scenarios:
>> randomly filled bitmap with relatively equal distribution of set and
>> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
>>
>> ...
>>
>> +config TEST_FIND_BIT
>
> Well.  It doesn't actually "test" the code.  It measures its performance ;)

Yes!

Yyra, you can grab CONFIG_BENCHMARK_* namespace :-)


Another thing:

> +
> +   return 0;
> +}
> +module_init(find_bit_test);
> +
> +static void __exit test_find_bit_cleanup(void)
> +{
> +}
> +module_exit(test_find_bit_cleanup);

module exit hook is entirely unnecessary as you can return -E from init hook.
See lib/test-kstrtox.c

Re: [PATCH] lib: test module for find_*_bit() functions

[Alexey Dobriyan]

On 11/10/17, Andrew Morton  wrote:
> On Thu,  9 Nov 2017 17:07:14 +0300 Yury Norov 
> wrote:
>
>> find_bit functions are widely used in the kernel, including hot paths.
>> This module tests performance of that functions in 2 typical scenarios:
>> randomly filled bitmap with relatively equal distribution of set and
>> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
>>
>> ...
>>
>> +config TEST_FIND_BIT
>
> Well.  It doesn't actually "test" the code.  It measures its performance ;)

Yes!

Yyra, you can grab CONFIG_BENCHMARK_* namespace :-)


Another thing:

> +
> +   return 0;
> +}
> +module_init(find_bit_test);
> +
> +static void __exit test_find_bit_cleanup(void)
> +{
> +}
> +module_exit(test_find_bit_cleanup);

module exit hook is entirely unnecessary as you can return -E from init hook.
See lib/test-kstrtox.c

Re: [PATCH] lib: test module for find_*_bit() functions

[Andrew Morton]

On Thu,  9 Nov 2017 17:07:14 +0300 Yury Norov  wrote:

> find_bit functions are widely used in the kernel, including hot paths.
> This module tests performance of that functions in 2 typical scenarios:
> randomly filled bitmap with relatively equal distribution of set and
> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
> 
> ...
>
> +config TEST_FIND_BIT

Well.  It doesn't actually "test" the code.  It measures its performance ;)

Re: [PATCH] lib: test module for find_*_bit() functions

[Andrew Morton]

On Thu,  9 Nov 2017 17:07:14 +0300 Yury Norov  wrote:

> find_bit functions are widely used in the kernel, including hot paths.
> This module tests performance of that functions in 2 typical scenarios:
> randomly filled bitmap with relatively equal distribution of set and
> cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.
> 
> ...
>
> +config TEST_FIND_BIT

Well.  It doesn't actually "test" the code.  It measures its performance ;)

[PATCH] lib: test module for find_*_bit() functions

[Clement Courbet]

Reviewed-By: Clement Courbet 

Thanks for the addition, Yury ! I've used a modified version of v1
for measuring improvements from find_next_and_bit() on x86 and arm
and found it very useful.

[PATCH] lib: test module for find_*_bit() functions

[Clement Courbet]

Reviewed-By: Clement Courbet 

Thanks for the addition, Yury ! I've used a modified version of v1
for measuring improvements from find_next_and_bit() on x86 and arm
and found it very useful.

[PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

find_bit functions are widely used in the kernel, including hot paths.
This module tests performance of that functions in 2 typical scenarios:
randomly filled bitmap with relatively equal distribution of set and
cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.

On ThunderX machine:

 Start testing find_bit() with random-filled bitmap
[1032111.632383] find_next_bit: 240043 cycles,  164062 iterations
[1032111.647236] find_next_zero_bit:312848 cycles,  163619 iterations
[1032111.661585] find_last_bit: 193748 cycles,  164062 iterations
[1032113.450517] find_first_bit:177720874 cycles,   164062 
iterations
[1032113.462930]
 Start testing find_bit() with sparse bitmap
[1032113.477229] find_next_bit: 3633 cycles,656 iterations
[1032113.494281] find_next_zero_bit:620399 cycles,  327025 iterations
[1032113.506723] find_last_bit: 3038 cycles,656 iterations
[1032113.524485] find_first_bit:691407 cycles,  656 iterations

v2:
 - pretty printing;
 - increase length of bitmap to suppress noise;
 - drop inlining _find_next_bit();

CC: Alexey Dobriyan 
CC: Andrew Morton 
CC: Clement Courbet 
CC: Matthew Wilcox 
CC: Rasmus Villemoes 
Signed-off-by: Yury Norov 
---
 lib/Kconfig.debug   |   9 
 lib/Makefile|   1 +
 lib/test_find_bit.c | 141 
 3 files changed, 151 insertions(+)
 create mode 100644 lib/test_find_bit.c

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index dfdad67d8f6c..138034cc68a3 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1838,6 +1838,15 @@ config TEST_BPF
 
  If unsure, say N.
 
+config TEST_FIND_BIT
+   tristate "Test find_bit functions"
+   default n
+   help
+ This builds the "test_find_bit" module that measure find_*_bit()
+ functions performance.
+
+ If unsure, say N.
+
 config TEST_FIRMWARE
tristate "Test firmware loading via userspace interface"
default n
diff --git a/lib/Makefile b/lib/Makefile
index b8f2c16fccaa..97ec69d843f2 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -46,6 +46,7 @@ obj-y += hexdump.o
 obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
+obj-$(CONFIG_TEST_FIND_BIT) += test_find_bit.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
 obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o
 obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
diff --git a/lib/test_find_bit.c b/lib/test_find_bit.c
new file mode 100644
index ..920d5a0ca456
--- /dev/null
+++ b/lib/test_find_bit.c
@@ -0,0 +1,141 @@
+/*
+ * Test for find_*_bit functions.
+ *
+ * Copyright (c) 2017 Cavium.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ */
+
+/*
+ * find_bit functions are widely used in kernel, so the successful boot
+ * is good enough test for correctness.
+ *
+ * This test is focused on performance of traversing bitmaps. Two typical
+ * scenarios are reproduced:
+ * - randomly filled bitmap with approximately equal number of set and
+ *   cleared bits;
+ * - sparse bitmap with few set bits at random positions.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#define BITMAP_LEN (4096UL * 8 * 10)
+#define SPARSE 500
+
+static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
+
+/*
+ * This is Schlemiel the Painter's algorithm. It should be called after
+ * all other tests for the same bitmap because it sets all bits of bitmap to 1.
+ */
+static int __init test_find_first_bit(void *bitmap, unsigned long len)
+{
+   unsigned long i, cnt;
+   cycles_t cycles;
+
+   cycles = get_cycles();
+   for (cnt = i = 0; i < len; cnt++) {
+   i = find_first_bit(bitmap, len);
+   __clear_bit(i, bitmap);
+   }
+   cycles = get_cycles() - cycles;
+   pr_err("find_first_bit:\t\t%ld cycles,\t%ld iterations\n", cycles, cnt);
+
+   return 0;
+}
+
+static int __init test_find_next_bit(const void *bitmap, unsigned long len)
+{
+   unsigned long i, cnt;
+   cycles_t cycles;
+
+   cycles = get_cycles();
+   for (cnt = i = 0; i < BITMAP_LEN; cnt++)
+   i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
+   cycles = get_cycles() - cycles;
+   pr_err("find_next_bit:\t\t%ld cycles,\t%ld iterations\n", cycles, cnt);
+
+   return 0;
+}
+
+static int __init 

[PATCH] lib: test module for find_*_bit() functions

[Yury Norov]

find_bit functions are widely used in the kernel, including hot paths.
This module tests performance of that functions in 2 typical scenarios:
randomly filled bitmap with relatively equal distribution of set and
cleared bits, and sparse bitmap which has 1 set bit for 500 cleared bits.

On ThunderX machine:

 Start testing find_bit() with random-filled bitmap
[1032111.632383] find_next_bit: 240043 cycles,  164062 iterations
[1032111.647236] find_next_zero_bit:312848 cycles,  163619 iterations
[1032111.661585] find_last_bit: 193748 cycles,  164062 iterations
[1032113.450517] find_first_bit:177720874 cycles,   164062 
iterations
[1032113.462930]
 Start testing find_bit() with sparse bitmap
[1032113.477229] find_next_bit: 3633 cycles,656 iterations
[1032113.494281] find_next_zero_bit:620399 cycles,  327025 iterations
[1032113.506723] find_last_bit: 3038 cycles,656 iterations
[1032113.524485] find_first_bit:691407 cycles,  656 iterations

v2:
 - pretty printing;
 - increase length of bitmap to suppress noise;
 - drop inlining _find_next_bit();

CC: Alexey Dobriyan 
CC: Andrew Morton 
CC: Clement Courbet 
CC: Matthew Wilcox 
CC: Rasmus Villemoes 
Signed-off-by: Yury Norov 
---
 lib/Kconfig.debug   |   9 
 lib/Makefile|   1 +
 lib/test_find_bit.c | 141 
 3 files changed, 151 insertions(+)
 create mode 100644 lib/test_find_bit.c

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index dfdad67d8f6c..138034cc68a3 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1838,6 +1838,15 @@ config TEST_BPF
 
  If unsure, say N.
 
+config TEST_FIND_BIT
+   tristate "Test find_bit functions"
+   default n
+   help
+ This builds the "test_find_bit" module that measure find_*_bit()
+ functions performance.
+
+ If unsure, say N.
+
 config TEST_FIRMWARE
tristate "Test firmware loading via userspace interface"
default n
diff --git a/lib/Makefile b/lib/Makefile
index b8f2c16fccaa..97ec69d843f2 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -46,6 +46,7 @@ obj-y += hexdump.o
 obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
+obj-$(CONFIG_TEST_FIND_BIT) += test_find_bit.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
 obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o
 obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
diff --git a/lib/test_find_bit.c b/lib/test_find_bit.c
new file mode 100644
index ..920d5a0ca456
--- /dev/null
+++ b/lib/test_find_bit.c
@@ -0,0 +1,141 @@
+/*
+ * Test for find_*_bit functions.
+ *
+ * Copyright (c) 2017 Cavium.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ */
+
+/*
+ * find_bit functions are widely used in kernel, so the successful boot
+ * is good enough test for correctness.
+ *
+ * This test is focused on performance of traversing bitmaps. Two typical
+ * scenarios are reproduced:
+ * - randomly filled bitmap with approximately equal number of set and
+ *   cleared bits;
+ * - sparse bitmap with few set bits at random positions.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+#define BITMAP_LEN (4096UL * 8 * 10)
+#define SPARSE 500
+
+static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
+
+/*
+ * This is Schlemiel the Painter's algorithm. It should be called after
+ * all other tests for the same bitmap because it sets all bits of bitmap to 1.
+ */
+static int __init test_find_first_bit(void *bitmap, unsigned long len)
+{
+   unsigned long i, cnt;
+   cycles_t cycles;
+
+   cycles = get_cycles();
+   for (cnt = i = 0; i < len; cnt++) {
+   i = find_first_bit(bitmap, len);
+   __clear_bit(i, bitmap);
+   }
+   cycles = get_cycles() - cycles;
+   pr_err("find_first_bit:\t\t%ld cycles,\t%ld iterations\n", cycles, cnt);
+
+   return 0;
+}
+
+static int __init test_find_next_bit(const void *bitmap, unsigned long len)
+{
+   unsigned long i, cnt;
+   cycles_t cycles;
+
+   cycles = get_cycles();
+   for (cnt = i = 0; i < BITMAP_LEN; cnt++)
+   i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
+   cycles = get_cycles() - cycles;
+   pr_err("find_next_bit:\t\t%ld cycles,\t%ld iterations\n", cycles, cnt);
+
+   return 0;
+}
+
+static int __init test_find_next_zero_bit(const void *bitmap, unsigned long 
len)
+{
+   unsigned long i, cnt;
+   cycles_t cycles;
+
+   cycles =