Messages in this thread Patch in this message | | | Date | Thu, 17 Aug 2023 18:37:01 +0300 | From | Andy Shevchenko <> | Subject | Re: [PATCH] bitmap: optimize bitmap_remap() |
| |
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; w = bitmap_weight(new, nbits); + if (w == 0) + goto identity_map; + + 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... :-( 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?).
-- With Best Regards, Andy Shevchenko
| |