linux-kernel - Re: [PATCH v2 5/6] lib: benchmark bitmap sets binary operation find

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <ZtHptgtLhgpGQTga@yury-ThinkPad>
Date: Fri, 30 Aug 2024 08:48:06 -0700
From: Yury Norov <yury.norov@...il.com>
To: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: Rasmus Villemoes <linux@...musvillemoes.dk>,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 5/6] lib: benchmark bitmap sets binary operation find

On Thu, Aug 29, 2024 at 09:59:25AM -0400, Mathieu Desnoyers wrote:
> Benchmark the following bitmap find functions applying binary operations
> on sets of two bitmaps:
> 
> - find_first_andnot_bit,
> - find_first_nor_bit,
> - find_next_andnot_bit,
> - find_next_nor_bit,
> - find_next_or_bit.
> 
> Note that find_first_or_bit is not part of the current API, so it is not
> covered.

Can you please show how the test output looks on your system now? I'll
add that in commit message.

> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
> Cc: Yury Norov <yury.norov@...il.com>
> Cc: Rasmus Villemoes <linux@...musvillemoes.dk>
> ---
>  lib/find_bit_benchmark.c | 93 ++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 93 insertions(+)
> 
> diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> index aee2ebb6b3cd..3b16254dec23 100644
> --- a/lib/find_bit_benchmark.c
> +++ b/lib/find_bit_benchmark.c
> @@ -70,6 +70,44 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
>  	return 0;
>  }
>  
> +static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, unsigned long len)
> +{
> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	bitmap_copy(cp, bitmap, BITMAP_LEN);
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < len; cnt++) {
> +		i = find_first_andnot_bit(cp, bitmap2, len);
> +		__clear_bit(i, cp);
> +	}
> +	time = ktime_get() - time;
> +	pr_err("find_first_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
> +static int __init test_find_first_nor_bit(void *bitmap, const void *bitmap2, unsigned long len)
> +{
> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	bitmap_copy(cp, bitmap, BITMAP_LEN);
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < len; cnt++) {
> +		i = find_first_nor_bit(cp, bitmap2, len);
> +		__set_bit(i, cp);
> +	}
> +	time = ktime_get() - time;
> +	pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
>  static int __init test_find_next_bit(const void *bitmap, unsigned long len)
>  {
>  	unsigned long i, cnt;
> @@ -148,6 +186,51 @@ static int __init test_find_next_and_bit(const void *bitmap,
>  	return 0;
>  }
>  
> +static int __init test_find_next_andnot_bit(const void *bitmap,
> +		const void *bitmap2, unsigned long len)
> +{
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
> +		i = find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> +	time = ktime_get() - time;
> +	pr_err("find_next_andnot_bit:  %18llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
> +static int __init test_find_next_nor_bit(const void *bitmap,
> +		const void *bitmap2, unsigned long len)
> +{
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
> +		i = find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> +	time = ktime_get() - time;
> +	pr_err("find_next_nor_bit:  %18llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
> +static int __init test_find_next_or_bit(const void *bitmap,
> +		const void *bitmap2, unsigned long len)
> +{
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
> +		i = find_next_or_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> +	time = ktime_get() - time;
> +	pr_err("find_next_or_bit:  %18llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
>  static int __init find_bit_test(void)
>  {
>  	unsigned long nbits = BITMAP_LEN / SPARSE;
> @@ -169,6 +252,11 @@ static int __init find_bit_test(void)
>  	test_find_first_bit(bitmap, BITMAP_LEN / 10);
>  	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2);
>  	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> +	test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
>  
>  	pr_err("\nStart testing find_bit() with sparse bitmap\n");
>  
> @@ -187,6 +275,11 @@ static int __init find_bit_test(void)
>  	test_find_first_bit(bitmap, BITMAP_LEN);
>  	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
>  	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
>  
>  	/*
>  	 * Everything is OK. Return error just to let user run benchmark
> -- 
> 2.39.2