]> git.baikalelectronics.ru Git - kernel.git/commit
lib: add find_nth{,_and,_andnot}_bit()
authorYury Norov <yury.norov@gmail.com>
Sun, 18 Sep 2022 03:07:13 +0000 (20:07 -0700)
committerYury Norov <yury.norov@gmail.com>
Mon, 26 Sep 2022 19:19:12 +0000 (12:19 -0700)
commitcbb2a8ce2c4a6790a0d42d0b48f8001c75e5a05a
treea9ae97708cf840672349bb19e0e1eec57fcc5c32
parent297a264ed0e8166b5537a1273a5493b6d406adb0
lib: add find_nth{,_and,_andnot}_bit()

Kernel lacks for a function that searches for Nth bit in a bitmap.
Usually people do it like this:
for_each_set_bit(bit, mask, size)
if (n-- == 0)
return bit;

We can do it more efficiently, if we:
1. find a word containing Nth bit, using hweight(); and
2. find the bit, using a helper fns(), that works similarly to
   __ffs() and ffz().

fns() is implemented as a simple loop. For x86_64, there's PDEP instruction
to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the
most of improvement comes from using hweight(), so I kept fns() simple.

New find_nth_bit() is ~70 times faster on x86_64/kvm in find_bit benchmark:
find_nth_bit:                  7154190 ns,  16411 iterations
for_each_bit:                505493126 ns,  16315 iterations

With all that, a family of 3 new functions is added, and used where
appropriate in the following patches.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
include/linux/bitops.h
include/linux/find.h
lib/find_bit.c