Messages in this thread | | | Date | Thu, 7 Jul 2022 09:25:07 +0200 | Subject | Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit() | From | Rasmus Villemoes <> |
| |
On 06/07/2022 20.22, Yury Norov wrote: > 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: > for_each_bit: 7154190 ns, 16411 iterations > find_nth_bit: 505493126 ns, 16315 iterations
Eh, have you interchanged these somehow, otherwise this reads as find_nth_bit being ~70 times _slower_?
> 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 | 19 ++++++++++ > include/linux/find.h | 79 ++++++++++++++++++++++++++++++++++++++++++ > lib/find_bit.c | 20 +++++++++++ > 3 files changed, 118 insertions(+) > > diff --git a/include/linux/bitops.h b/include/linux/bitops.h > index 7aaed501f768..86072cfcbe17 100644 > --- a/include/linux/bitops.h > +++ b/include/linux/bitops.h > @@ -196,6 +196,25 @@ static inline unsigned long __ffs64(u64 word) > return __ffs((unsigned long)word); > } > > +/** > + * fns - find N'th set bit in a 64 bit word > + * @word: The 64 bit word > + * @n: Bit to find > + */ > +static inline unsigned long fns(unsigned long word, unsigned int n) > +{ > + unsigned int bit; > + > + while (word) { > + bit = __ffs(word); > + if (--n == 0) > + return bit; > + __clear_bit(bit, &word); > + } > + > + return BITS_PER_LONG; > +}
Urgh. "unsigned long" is not necessarily a 64 bit word. And I don't like that the index is apparently 1-based (and that surprising API isn't spelled out anywhere). This is also way too big to be inline IMO.
> #ifndef find_first_and_bit > /** > * find_first_and_bit - find the first set bit in both memory regions > diff --git a/lib/find_bit.c b/lib/find_bit.c > index 1b8e4b2a9cba..7b8ad12c8cc7 100644 > --- a/lib/find_bit.c > +++ b/lib/find_bit.c > @@ -89,6 +89,26 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) > EXPORT_SYMBOL(_find_first_bit); > #endif > > +unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2, > + unsigned long size, unsigned long n, bool not) > +{ > + unsigned long val, idx, w; > + > + for (idx = 0; idx * BITS_PER_LONG < size; idx++, n -= w) { > + val = addr1[idx]; > + if (addr2) > + val &= not ? ~addr2[idx] : addr2[idx];
Maybe this could be microoptimized by doing
unsigned long addr2mask = not ? ~0UL : 0UL; ...
val &= (addr2[idx] ^ addr2mask);
but I don't think it'll make a difference.
Rasmus
| |