diff options
author | Yury Norov <yury.norov@gmail.com> | 2022-09-18 06:07:13 +0300 |
---|---|---|
committer | Yury Norov <yury.norov@gmail.com> | 2022-09-26 22:19:12 +0300 |
commit | 3cea8d475327756066e2a54f0b651bb7284dd448 (patch) | |
tree | a9ae97708cf840672349bb19e0e1eec57fcc5c32 /lib/test_bitmap.c | |
parent | 24291caf8447f6fc060c8d00136bdc30ee207f38 (diff) | |
download | linux-3cea8d475327756066e2a54f0b651bb7284dd448.tar.xz |
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>
Diffstat (limited to 'lib/test_bitmap.c')
0 files changed, 0 insertions, 0 deletions