bitmap: clean up and (micro?)optimization
Subsystems (2)
cover bitmap: clean up and (micro?)optimization
Just wanted to discuss the idea, which is represented by these two patches. Comments, remarks, tests are all welcome!
Andy Shevchenko (2):
bitmap: Use constants and macros from bits.h
bitmap: Optimize memset() calls
include/linux/bitmap.h | 26 +++++++++++++++++--------- lib/bitmap.c | 4 ++-- 2 files changed, 19 insertions(+), 11 deletions(-)
Signature · 1 line
2.40.0.1.gaa8946217a0b
PATCH 1/2 bitmap: Use constants and macros from bits.h
Use BITS_PER_LONG and BITS_PER_BYTE for BITMAP_MEM_ALIGNMENT. Calculate bytes from bits for memcmp() and memset() with BITS_TO_BYTES().
--- include/linux/bitmap.h | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
include/linux/bitmap.h +5 -5
@@ -354,9 +354,9 @@ static inline void bitmap_complement(unsigned long *dst, const unsigned long *sr }#ifdef __LITTLE_ENDIAN -#define BITMAP_MEM_ALIGNMENT 8 +#define BITMAP_MEM_ALIGNMENT BITS_PER_BYTE#else -#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) +#define BITMAP_MEM_ALIGNMENT BITS_PER_LONG#endif #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
@@ -367,7 +367,7 @@ static inline bool bitmap_equal(const unsigned long *src1,return !((*src1 ^ *src2) &BITMAP_LAST_WORD_MASK (nbits));if (__builtin_constant_p (nbits &BITMAP_MEM_MASK ) &&IS_ALIGNED (nbits,BITMAP_MEM_ALIGNMENT )) -return !memcmp (src1, src2, nbits /8 ); +return !memcmp (src1, src2,BITS_TO_BYTES (nbits));return __bitmap_equal (src1, src2, nbits); }
@@ -454,7 +454,7 @@ static __always_inline void bitmap_set(unsigned long *map, unsigned int start, IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && __builtin_constant_p(nbits & BITMAP_MEM_MASK) && IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) -memset ((char *)map + start /8 ,0xff , nbits /8 ); +memset ((char *)map +BITS_TO_BYTES (start),0xff ,BITS_TO_BYTES (nbits)); else__bitmap_set (map ,start ,nbits ); }
@@ -470,7 +470,7 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start, IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && __builtin_constant_p(nbits & BITMAP_MEM_MASK) && IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) -memset ((char *)map + start /8 ,0 , nbits /8 ); +memset ((char *)map +BITS_TO_BYTES (start),0x00 ,BITS_TO_BYTES (nbits)); else__bitmap_clear (map ,start ,nbits ); }
Signature · 1 line
2.40.0.1.gaa8946217a0b
Rasmus Villemoes
reviewerRe: [PATCH v1 1/2] bitmap: Use constants and macros from bits.h
Quoted 25 lines · Andy Shevchenko
Use
BITS_PER_LONGandBITS_PER_BYTEforBITMAP_MEM_ALIGNMENT. Calculate bytes from bits formemcmp()andmemset()withBITS_TO_BYTES().Signed-off-by Andy Shevchenko <[email protected]>--- include/linux/bitmap.h | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)include/linux/bitmap.h +2
-2@@ -354,9 +354,9 @@ static inline void bitmap_complement(unsigned long *dst, const unsigned long *sr }#ifdef __LITTLE_ENDIAN -#define BITMAP_MEM_ALIGNMENT 8 +#define BITMAP_MEM_ALIGNMENT BITS_PER_BYTE#else -#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) +#define BITMAP_MEM_ALIGNMENT BITS_PER_LONG#endif #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
include/linux/bitmap.h static inline bool bitmap_equal(const unsigned long *src1, · line 370
Quoted 5 lines
include/linux/bitmap.h +1
-1@@ -367,7 +367,7 @@ static inline bool bitmap_equal(const unsigned long *src1,return !((*src1 ^ *src2) &BITMAP_LAST_WORD_MASK (nbits));if (__builtin_constant_p (nbits &BITMAP_MEM_MASK ) &&IS_ALIGNED (nbits,BITMAP_MEM_ALIGNMENT )) -return !memcmp (src1, src2, nbits /8 ); +return !memcmp (src1, src2,BITS_TO_BYTES (nbits));
Please no. Currently, I can verify the arithmetic directly. Using such a "helper" I'd have to know whether it just does /8 or if it's more like the bitmap_words() thing which rounds up to a whole number of words. And BITS_PER_BYTE (and similarly CHAR_BITS) really is, IMO, much less readable than 8.
Rasmus
Re: [PATCH v1 1/2] bitmap: Use constants and macros from bits.h
Quoted 10 lines · Rasmus Villemoes
include/linux/bitmap.h static inline void bitmap_complement(unsigned long *dst, const unsigned long *sr · line 361
Quoted 8 lines · Andy Shevchenko
#ifdef
__LITTLE_ENDIANinclude/linux/bitmap.h +2
-2-#define BITMAP_MEM_ALIGNMENT 8 +#define BITMAP_MEM_ALIGNMENT BITS_PER_BYTE#else -#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) +#define BITMAP_MEM_ALIGNMENT BITS_PER_LONG#endif #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
What about this chunk? Does it worth to be updated?
...
Quoted 8 lines
include/linux/bitmap.h static inline bool bitmap_equal(const unsigned long *src1, · line 370
Quoted 2 lines
include/linux/bitmap.h +1
-1-return !memcmp (src1, src2, nbits /8 ); +return !memcmp (src1, src2,BITS_TO_BYTES (nbits));Please no. Currently, I can verify the arithmetic directly. Using such a "helper" I'd have to know whether it just does /8 or if it's more like the
bitmap_words()thing which rounds up to a whole number of words. AndBITS_PER_BYTE(and similarlyCHAR_BITS) really is, IMO, much less readable than 8.
Okay, thank you for the comment!
Signature · 2 lines
With Best Regards, Andy Shevchenko
Rasmus Villemoes
reviewerRe: [PATCH v1 1/2] bitmap: Use constants and macros from bits.h
Quoted 13 lines · Andy Shevchenko
Quoted 10 lines · Rasmus Villemoes
include/linux/bitmap.h static inline void bitmap_complement(unsigned long *dst, const unsigned long *sr · line 361
Quoted 8 lines · Andy Shevchenko
#ifdef
__LITTLE_ENDIANinclude/linux/bitmap.h +2
-2-#define BITMAP_MEM_ALIGNMENT 8 +#define BITMAP_MEM_ALIGNMENT BITS_PER_BYTE#else -#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) +#define BITMAP_MEM_ALIGNMENT BITS_PER_LONG#endif #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)What about this chunk? Does it worth to be updated?
IMHO, no, not in this way anyway. But the macros could perhaps use a comment saying that they decide whether certain bitmap operations can be turned into plain memxxx calls, which is why LE vs BE matters, and LE just needs the bitmap to consist of a whole number of bytes while for BE it must be a whole number of longs.
Rasmus
PATCH 2/2 bitmap: Optimize memset() calls
In reply to Andy ShevchenkoIntead of byte memset() calls use 32- or 64-bit version depending on the compile-time BITS_PER_LONG value.
--- include/linux/bitmap.h | 16 ++++++++++++---- lib/bitmap.c | 4 ++-- 2 files changed, 14 insertions(+), 6 deletions(-)
include/linux/bitmap.h +12 -4
@@ -234,22 +234,30 @@ extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,static inline void bitmap_zero (unsigned long *dst,unsigned int nbits) { -unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long ); +unsigned int len =BITS_TO_LONGS (nbits);if (small_const_nbits (nbits)) *dst =0 ; else -memset (dst,0 , len); +#if BITS_PER_LONG ==64 +memset64 ((uint64_t *)dst,0 , len); +#else +memset32 ((uint32_t *)dst,0 , len); +#endif }static inline void bitmap_fill (unsigned long *dst,unsigned int nbits) { -unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long ); +unsigned int len =BITS_TO_LONGS (nbits);if (small_const_nbits (nbits)) *dst = ~0UL ; else -memset (dst,0xff , len); +#if BITS_PER_LONG ==64 +memset64 ((uint64_t *)dst,GENMASK (63 ,0 ), len); +#else +memset32 ((uint32_t *)dst,GENMASK (31 ,0 ), len); +#endif } static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
lib/bitmap.c +2 -2
@@ -128,7 +128,7 @@ void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, dst[k] = lower | upper; }if (off) -memset (&dst[lim - off],0 , off*sizeof (unsigned long )); +bitmap_zero (&dst[lim - off], off); }EXPORT_SYMBOL (__bitmap_shift_right);
@@ -166,7 +166,7 @@ void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, dst[k + off] = lower | upper; }if (off) -memset (dst,0 , off*sizeof (unsigned long )); +bitmap_zero (dst, off); }EXPORT_SYMBOL (__bitmap_shift_left);
Signature · 1 line
2.40.0.1.gaa8946217a0b
Rasmus Villemoes
reviewerRe: [PATCH v1 2/2] bitmap: Optimize memset() calls
Quoted 21 lines · Andy Shevchenko
Intead of byte
memset()calls use 32- or 64-bit version depending on the compile-timeBITS_PER_LONGvalue.Signed-off-by Andy Shevchenko <[email protected]>--- include/linux/bitmap.h | 16 ++++++++++++---- lib/bitmap.c | 4 ++-- 2 files changed, 14 insertions(+), 6 deletions(-)include/linux/bitmap.h +1
-1@@ -234,22 +234,30 @@ extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,static inline void bitmap_zero (unsigned long *dst,unsigned int nbits) { -unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long ); +unsigned int len =BITS_TO_LONGS (nbits);if (small_const_nbits (nbits))
include/linux/bitmap.h extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp, · line 248
Quoted 10 lines
include/linux/bitmap.h +5
-1*dst =0 ; else - memset(dst, 0, len); +#if BITS_PER_LONG ==64 +memset64 ((uint64_t *)dst,0 , len); +#else +memset32 ((uint32_t *)dst,0 , len); +#endif }
So _if_ this is worth it at all, all those new '#if BITS_PER_LONG == 64' suggests that we should instead have a new helper memset_long(), no?
In fact, string.h already has that:
static inline void *memset_l(unsigned long *p, unsigned long v,
__kernel_size_t n)
Quoted 5 lines
include/linux/bitmap.h +1
-1static inline void bitmap_fill (unsigned long *dst,unsigned int nbits) { -unsigned int len =BITS_TO_LONGS (nbits) *sizeof (unsigned long ); +unsigned int len =BITS_TO_LONGS (nbits);
include/linux/bitmap.h extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp, · line 262
Quoted 10 lines
include/linux/bitmap.h +5
-1if (small_const_nbits (nbits)) *dst = ~0UL ; else -memset (dst,0xff , len); +#if BITS_PER_LONG ==64 +memset64 ((uint64_t *)dst,GENMASK (63 ,0 ), len); +#else +memset32 ((uint32_t *)dst,GENMASK (31 ,0 ), len); +#endif> }
Please just spell an all-ones long "~0UL", that also matches the small_const case.
lib/bitmap.c void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, · line 131
Quoted 11 lines
include/linux/bitmap.h +0
-0static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,lib/bitmap.c +1
-1@@ -128,7 +128,7 @@ void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, dst[k] = lower | upper; }if (off) -memset (&dst[lim - off],0 , off*sizeof (unsigned long )); +bitmap_zero (&dst[lim - off], off);
This... can't be right. bitmap_zero() still takes an argument which is the size in bits, while off is the whole number of words to shift. So if called with say shift=128, we'd have off==2, and that bitmap_zero() would, because bitmap_zero() rounds up to a whole number of words, end up clearing just one word.
Perhaps a chance to add some more test cases? Maybe we're not exercising any of the "shift more than BITS_PER_LONG" logic.
But rather than using bitmap_zero() here, forcing you to convert off to a number of bits and then bitmap_zero to divide again, if you do this at all, just change that memset() to memset_l().
lib/bitmap.c void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, · line 170
Quoted 10 lines
lib/bitmap.c +1
-1}EXPORT_SYMBOL (__bitmap_shift_right);@@ -166,7 +166,7 @@ void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, dst[k + off] = lower | upper; }if (off) -memset (dst,0 , off*sizeof (unsigned long )); +bitmap_zero (dst, off); }
Same here. Cannot possibly be correct, but will work by chance for off <= 1, i.e. shift <= BITS_PER_LONG.
Rasmus
Re: [PATCH v1 2/2] bitmap: Optimize memset() calls
Quoted 1 line · Rasmus Villemoes
On 17/08/2023 18.54, Andy Shevchenko wrote:
...
Quoted 8 lines
include/linux/bitmap.h extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp, · line 247
Quoted 6 lines
include/linux/bitmap.h +5
-0+#if BITS_PER_LONG ==64 +memset64 ((uint64_t *)dst,0 , len); +#else +memset32 ((uint32_t *)dst,0 , len); +#endif }So _if_ this is worth it at all,
Yury, I believe you have a set of performance tests for bitmaps, perhaps you can give a try and see if we got a benefit here.
Yet, not all architectures have custom implementation of the optimized memset()/memcpy(). But at least ARM, x86 do.
Quoted 7 lines
all those new '#if
BITS_PER_LONG== 64'
suggests that we should instead have a new helpermemset_long(), no?In fact,
string.halready has that:static inline void *memset_l(unsigned long *p, unsigned long v,
__kernel_size_t n)
My grep skills suddenly degraded, my thoughts were exactly like yours, but I missed the _l instead of _long for which I grepped.
...
Quoted 2 lines
Please just spell an all-ones long "~0UL", that also matches the
small_constcase.
OK!
...
Quoted 4 lines
lib/bitmap.c void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, · line 131
Quoted 2 lines
lib/bitmap.c +1
-1-memset (&dst[lim - off],0 , off*sizeof (unsigned long )); +bitmap_zero (&dst[lim - off], off);This... can't be right.
Indeed, I have in mind memset_long() and on the half-way replaced it with bitmap_zero().
Quoted 6 lines
bitmap_zero()still takes an argument which is
the size in bits, while off is the whole number of words to shift. So if called with say shift=128, we'd have off==2, and thatbitmap_zero()would, becausebitmap_zero()rounds up to a whole number of words, end up clearing just one word.
Quoted 6 lines
Perhaps a chance to add some more test cases? Maybe we're not exercising any of the "shift more than
BITS_PER_LONG" logic.But rather than using
bitmap_zero()here, forcing you to convert off to a number of bits and thenbitmap_zeroto divide again, if you do this at all, just change thatmemset()tomemset_l().
Agree.
Signature · 2 lines
With Best Regards, Andy Shevchenko