Messages in this thread | | | Date | Thu, 7 Jul 2022 14:03:45 -0700 | From | Yury Norov <> | Subject | Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit() |
| |
On Thu, Jul 07, 2022 at 09:25:07AM +0200, Rasmus Villemoes wrote: > 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_?
I didn't change the pr_err("find_nth_bit: ...") line in the test, and had to edit manually when preparing the series. The numbers are fair, it's just manual edit issue.
> > 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.
I'm not sure I understand your concern. The fns() returns an index of Nth bit (0...31 or 0...63 correspondingly), or 32/64 if such bit doesn't exit.
> And I don't > like that the index is apparently 1-based (and that surprising API isn't > spelled out anywhere).
Yeah... My motivation to start counting from 1 is to keep consistency with ffs: __ffs(word) <=> fns(word, 1). So, the argument is not an index - we are looking for the index; instead, it's an order - first, second, third etc.
But the return value - is index, counting from 0. It looks weird, but after some poking around, I think this is the most logical way to go. I'll add a note in the comments for v2.
> This is also way too big to be inline IMO.
Maybe yes... I've got nothing against moving it into c-file. On the other hand, arch/alpha/include/asm/bitops.h is full of 5-line inline functions, just for example. Let's see what others say.
> > #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.
I'll try.
Thanks for review!
Thanks, Yury
| |