Re: [PATCH] bitmap: optimize bitmap_remap()

From: Yury Norov
Date: Fri Aug 18 2023 - 22:08:54 EST


On Thu, Aug 17, 2023 at 06:37:01PM +0300, Andy Shevchenko wrote:
> On Thu, Aug 17, 2023 at 07:21:59AM -0700, Yury Norov wrote:
> > On Thu, Aug 17, 2023 at 12:38:28PM +0300, Andy Shevchenko wrote:
> > > On Thu, Aug 17, 2023 at 12:37:05PM +0300, Andy Shevchenko wrote:
> > > > On Tue, Aug 15, 2023 at 04:59:34PM -0700, Yury Norov wrote:
>
> ...
>
> > > > > int n = bitmap_pos_to_ord(old, oldbit, nbits);
> > > > >
> > > > > + bit = (n < 0) ? oldbit : /* identity map */
> > > >
> > > > Can't you also optimize this case?
> > > >
> > > > Something like
> > > >
> > > > bitmap_xor(tmp, old, new) // maybe even better approach, dunno
> > >
> > > > bitmap_empty(tmp) // can be replaced by find first bit
> > >
> > > Or reuse bitmap_weight()...
> >
> > That way it wouldn't work,
>
> Why not? AFAIU there are two cases when we may copy:
> 1) the new mapping is empty;
> 2) the old == new.
>
> The other cases we need to remap.
>
> The case 2) is easy with xor and weight.
>
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index 24284caadbcc..917eea5219ac 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -958,7 +958,7 @@ EXPORT_SYMBOL(bitmap_parse);
> * gets mapped to (returns) @ord value 3 in this example, that means
> * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
> *
> - * The bit positions 0 through @bits are valid positions in @buf.
> + * The bit positions 0 through @nbits are valid positions in @buf.
> */
> static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
> {
> @@ -1008,17 +1008,30 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
>
> if (dst == src) /* following doesn't handle inplace remaps */
> return;
> - bitmap_zero(dst, nbits);
> +
> + bitmap_xor(dst, old, new, nbits);
> + if (bitmap_empty(dst, nbits))
> + goto identity_map;

Now you see? The complexity of this test is 2*O(N). Assuming that people
know better than us when they can optimize their trivial cases with just
copying, this will slow those conscientious users because for them, of
course, old == new is highly unlikely.

Of course, we can do 'if (bitmap_equal(old, new, nbits))', but it's
still O(N), and the above is applicable just as well.

> w = bitmap_weight(new, nbits);
> + if (w == 0)
> + goto identity_map;

In contrast, this test is O(1), because we need the weight of new
bitmap anyways.

> +
> + bitmap_zero(dst, nbits);
> +
> for_each_set_bit(oldbit, src, nbits) {
> int n = bitmap_pos_to_ord(old, oldbit, nbits);
>
> - if (n < 0 || w == 0)
> + if (n < 0)
> set_bit(oldbit, dst); /* identity map */
> else
> set_bit(find_nth_bit(new, nbits, n % w), dst);
> }
> +
> + return;
> +
> +identity_map:
> + bitmap_copy(dst, src, nbits);
> }
> EXPORT_SYMBOL(bitmap_remap);
>
> But this gives +89 bytes on x86_64... :-(

Who cares if it gives a boost of performance for regular users?

> Inside the loop we can also break when n gets equal to w, but it seems
> a special case (we don't need bitmap_weight_from() for that, do we?).

No, we can't. Instead, we should wrap around 0, exactly what the existing
code does. See the comment:

* Let @old and @new define a mapping of bit positions, such that
* whatever position is held by the n-th set bit in @old is mapped
* to the n-th set bit in @new. In the more general case, allowing
* for the possibility that the weight 'w' of @new is less than the
* weight of @old, map the position of the n-th set bit in @old to
* the position of the m-th set bit in @new, where m == n % w.

This is written 18 years ago, and it seems it needs to get illustrated.
I didn't find anything else describing bitmap_remap() for more except
my own comment in a random discussion more than a year ago:

https://lkml.org/lkml/2022/6/13/3126

Thanks,
Yury