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
With all that, a family of 3 new functions is added, and used where
appropriate in the following patches.
Signed-off-by: Yury Norov <[email protected]>
---
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;
+}
+
/**
* assign_bit - Assign value to a bit in memory
* @nr: the bit to set
diff --git a/include/linux/find.h b/include/linux/find.h
index 424ef67d4a42..00a24bc596d0 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -12,6 +12,8 @@ extern unsigned long _find_next_bit(const unsigned long *addr1,
const unsigned long *addr2, unsigned long nbits,
unsigned long start, unsigned long invert, unsigned long le);
extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
+unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
+ unsigned long size, unsigned long n, bool not);
extern unsigned long _find_first_and_bit(const unsigned long *addr1,
const unsigned long *addr2, unsigned long size);
extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
@@ -125,6 +127,83 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
}
#endif
+/**
+ * find_nth_bit - find N'th set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The maximum number of bits to search
+ * @n: The number of set bit, which position is needed
+ *
+ * Returns the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
+{
+ if (n == 0 || n > size)
+ return size;
+
+ if (small_const_nbits(size)) {
+ unsigned long val = *addr & GENMASK(size - 1, 0);
+
+ return val ? fns(val, n) : size;
+ }
+
+ return _find_nth_bit(addr, NULL, size, n, false);
+}
+
+/**
+ * find_nth_and_bit - find N'th set bit in 2 memory regions
+ * @addr1: The 1st address to start the search at
+ * @addr2: The 2nd address to start the search at
+ * @size: The maximum number of bits to search
+ * @n: The number of set bit, which position is needed
+ *
+ * Returns the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
+ unsigned long size, unsigned long n)
+{
+ if (n == 0 || n > size)
+ return size;
+
+ if (small_const_nbits(size)) {
+ unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
+
+ return val ? fns(val, n) : size;
+ }
+
+ return _find_nth_bit(addr1, addr2, size, n, false);
+}
+
+/**
+ * find_nth_andnot_bit - find N'th set bit in 2 memory regions,
+ * flipping bits in 2nd region
+ * @addr1: The 1st address to start the search at
+ * @addr2: The 2nd address to start the search at
+ * @size: The maximum number of bits to search
+ * @n: The number of set bit, which position is needed
+ *
+ * Returns the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
+ unsigned long size, unsigned long n)
+{
+ if (n == 0 || n > size)
+ return size;
+
+ if (small_const_nbits(size)) {
+ unsigned long val = *addr1 & (~*addr2) & GENMASK(size - 1, 0);
+
+ return val ? fns(val, n) : size;
+ }
+
+ return _find_nth_bit(addr1, addr2, size, n, true);
+}
+
#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];
+
+ w = hweight_long(val);
+ if (w >= n)
+ return min(idx * BITS_PER_LONG + fns(val, n), size);
+ }
+
+ return size;
+
+}
+EXPORT_SYMBOL(_find_nth_bit);
+
#ifndef find_first_and_bit
/*
* Find the first set bit in two memory regions.
--
2.34.1
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 <[email protected]>
> ---
> 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
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 <[email protected]>
> > ---
> > 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
On Fri, Jul 8, 2022 at 10:55 AM Rasmus Villemoes
<[email protected]> wrote:
> On 07/07/2022 23.03, Yury Norov wrote:
>
> >> 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).
>
> I understand that you're translating that second f in ffs (find First
> set) to a 1. But I disagree that that's necessarily a logical thing to
> do. Everybody understands that (given a C or python or... context) when
> some prose talks about "the first element in an array", it's the one at
> [0]. So I find it much more natural that the set bits in a word are
> enumerated 0, 1, ..., popcount(w)-1.
I agree that here we operate with an array of bits, which naturally
starts from bit 0.
--
With Best Regards,
Andy Shevchenko
On 07/07/2022 23.03, Yury Norov wrote:
>> 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).
I understand that you're translating that second f in ffs (find First
set) to a 1. But I disagree that that's necessarily a logical thing to
do. Everybody understands that (given a C or python or... context) when
some prose talks about "the first element in an array", it's the one at
[0]. So I find it much more natural that the set bits in a word are
enumerated 0, 1, ..., popcount(w)-1.
Rasmus
On Fri, Jul 8, 2022 at 2:13 AM Andy Shevchenko
<[email protected]> wrote:
>
> On Fri, Jul 8, 2022 at 10:55 AM Rasmus Villemoes
> <[email protected]> wrote:
> > On 07/07/2022 23.03, Yury Norov wrote:
> >
> > >> 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).
> >
> > I understand that you're translating that second f in ffs (find First
> > set) to a 1. But I disagree that that's necessarily a logical thing to
> > do. Everybody understands that (given a C or python or... context) when
> > some prose talks about "the first element in an array", it's the one at
> > [0]. So I find it much more natural that the set bits in a word are
> > enumerated 0, 1, ..., popcount(w)-1.
>
> I agree that here we operate with an array of bits, which naturally
> starts from bit 0.
OK, I'll send v2 shortly