lib: add find_first_and_bit()
authorYury Norov <yury.norov@gmail.com>
Sat, 14 Aug 2021 21:17:01 +0000 (14:17 -0700)
committerYury Norov <yury.norov@gmail.com>
Sat, 15 Jan 2022 16:47:31 +0000 (08:47 -0800)
commitf68edc9297bf3f7c94abb54b9b0b053607f7587b
treef4e963ec2db91a06210c3b7886a233c16e411323
parentc126a53c276048125b4a950072bab37ad0fea120
lib: add find_first_and_bit()

Currently find_first_and_bit() is an alias to find_next_and_bit(). However,
it is widely used in cpumask, so it worth to optimize it. This patch adds
its own implementation for find_first_and_bit().

On x86_64 find_bit_benchmark says:

Before (#define find_first_and_bit(...) find_next_and_bit(..., 0):
Start testing find_bit() with random-filled bitmap
[  140.291468] find_first_and_bit:           46890919 ns,  32671 iterations
Start testing find_bit() with sparse bitmap
[  140.295028] find_first_and_bit:               7103 ns,      1 iterations

After:
Start testing find_bit() with random-filled bitmap
[  162.574907] find_first_and_bit:           25045813 ns,  32846 iterations
Start testing find_bit() with sparse bitmap
[  162.578458] find_first_and_bit:               4900 ns,      1 iterations

(Thanks to Alexey Klimov for thorough testing.)

Signed-off-by: Yury Norov <yury.norov@gmail.com>
Tested-by: Wolfram Sang <wsa+renesas@sang-engineering.com>
Tested-by: Alexey Klimov <aklimov@redhat.com>
include/linux/find.h
lib/find_bit.c
lib/find_bit_benchmark.c