Optimize bitmap_weight

PATCH In review Akinobu Mita 2 participants 6 messages May 11, 2012 – May 25, 2012

Subsystems (2)

Library code Bitmap API

lore

Share & tools

lore

Akinobu Mita

author

2012-05-11 14:10 UTC #0 lore raw

PATCH 1/1 Optimize bitmap_weight

The current implementation of bitmap_weight simply evaluates the population count for each long word of the array, and adds.

The subsection "Counting 1-bits in an Array" in the revisions of the book 'Hacker's Delight' explains more superior methods than the naive method.

http://www.hackersdelight.org/revisions.pdf
http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

My benchmark results on Intel Core i3 CPU with 32-bit kernel showed 50% faster for 8192 bits bitmap. However, it is not faster for small bitmap (< BITS_PER_LONG * 8) than the naive method. So if the bitmap size is known to be small at compile time, use the naive method.

/*
* userspace bitmap_weight() benchmark program
*/
extern int __bitmap_weight(const unsigned long *bitmap, int bits); extern int __bitmap_weight_fast(const unsigned long *bitmap, int bits);

int main(int argc, char **argv)

{
	int i;
	struct timeval start[2], stop[2], diff[2];
	unsigned int bits;
	unsigned long bitmap[1024 * 1024];
	int n, m;
	int iterations;

	if (argc != 4) {
		fprintf(stderr, "Usage: %s SEED BITS ITERATIONS\n", argv[0]);
		return -1;
	}

	srand(atoi(argv[1]));
	bits = atoi(argv[2]) % (sizeof(bitmap) * 8);
	iterations = atoi(argv[3]);

	for (i = 0; i < sizeof(bitmap); i++)
		((unsigned char *)bitmap)[i] = rand();

	/* dummy call */
	gettimeofday(&start[0], NULL);
	n = __bitmap_weight(bitmap, bits);
	gettimeofday(&stop[0], NULL);
	gettimeofday(&start[1], NULL);
	m = __bitmap_weight_fast(bitmap, bits);
	gettimeofday(&stop[1], NULL);

	if (n != m) {
		fprintf(stderr, "Oops %d != %d (%d)\n", n, m, atoi(argv[1]));
		return -1;
	}

	gettimeofday(&start[0], NULL);
	for (i = 0; i < iterations; i++)
		n += __bitmap_weight(bitmap, bits);
	gettimeofday(&stop[0], NULL);

	gettimeofday(&start[1], NULL);
	for (i = 0; i < iterations; i++)
		m += __bitmap_weight_fast(bitmap, bits);
	gettimeofday(&stop[1], NULL);

	if (n != m)
		return -1;

	timersub(&stop[0], &start[0], &diff[0]);
	timersub(&stop[1], &start[1], &diff[1]);
	printf("%d %d: %lu.%06lu %lu.%06lu\n", bits, iterations,
		diff[0].tv_sec, diff[0].tv_usec,
		diff[1].tv_sec, diff[1].tv_usec);

	return 0;
}

Signed-off-by Akinobu Mita <[email protected]>

---
 include/linux/bitmap.h |    5 +++-
 lib/bitmap.c           |   49 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+), 1 deletions(-)

include/linux/bitmap.h +4 -1

index 7ad6345..9191c7d 100644
@@ -111,6 +111,7 @@ extern int __bitmap_intersects(const unsigned long *bitmap1,
 extern int __bitmap_subset(const unsigned long *bitmap1,
 			const unsigned long *bitmap2, int bits);
 extern int __bitmap_weight(const unsigned long *bitmap, int bits);
+extern int __bitmap_weight_fast(const unsigned long *bitmap, int bits);
 
 extern void bitmap_set(unsigned long *map, int i, int len);
 extern void bitmap_clear(unsigned long *map, int start, int nr);

@@ -277,7 +278,9 @@ static inline int bitmap_weight(const unsigned long *src, int nbits)
 {
 	if (small_const_nbits(nbits))
 		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
-	return __bitmap_weight(src, nbits);
+	else if (__builtin_constant_p(nbits) && (nbits) < BITS_PER_LONG * 8)
+		return __bitmap_weight(src, nbits);
+	return __bitmap_weight_fast(src, nbits);
 }
 
 static inline void bitmap_shift_right(unsigned long *dst,

lib/bitmap.c +49 -0

55 lines not on this page · raw message

Signature · 1 line

1.7.7.6

Andrew Morton

maintainer

2012-05-11 22:48 UTC #1 lore raw

Quoted 20 lines · On Fri, 11 May 2012 23:10:14 +0900 Akinobu Mita <[email protected]> wrote:

The current implementation of bitmap_weight simply evaluates the population count for each long word of the array, and adds.
The subsection "Counting 1-bits in an Array" in the revisions of the book 'Hacker's Delight' explains more superior methods than the naive method.
http://www.hackersdelight.org/revisions.pdf
http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt
My benchmark results on Intel Core i3 CPU with 32-bit kernel showed 50% faster for 8192 bits bitmap. However, it is not faster for small bitmap (< BITS_PER_LONG * 8) than the naive method. So if the bitmap size is known to be small at compile time, use the naive method.
...
extern void bitmap_clear(unsigned long *map, int start, int nr);

include/linux/bitmap.h static inline int bitmap_weight(const unsigned long *src, int nbits) · line 280

Quoted 3 lines

include/linux/bitmap.h +0 -0

@@ -277,7 +278,9 @@ static inline int bitmap_weight(const unsigned long *src, int nbits)
 {
 	if (small_const_nbits(nbits))
 		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));

Why do we require a constant_p `nbits' for this case?

include/linux/bitmap.h static inline int bitmap_weight(const unsigned long *src, int nbits) · line 284

Quoted 5 lines

include/linux/bitmap.h +3 -1

-	return __bitmap_weight(src, nbits);
+	else if (__builtin_constant_p(nbits) && (nbits) < BITS_PER_LONG * 8)
+		return __bitmap_weight(src, nbits);
+	return __bitmap_weight_fast(src, nbits);
 }

BITS_PER_LONG*8 sounds like a large bitmap: 256 or 512 entries. Will the kernel call __bitmap_weight_fast() sufficiently often to make this extra code worth merging?

Akinobu Mita

author

2012-05-13 21:50 UTC #2 lore raw

2012/5/12 Andrew Morton <[email protected]>:

Quoted 35 lines

Quoted 20 lines · On Fri, 11 May 2012 23:10:14 +0900 Akinobu Mita <[email protected]> wrote:
The current implementation of bitmap_weight simply evaluates the population count for each long word of the array, and adds.
The subsection "Counting 1-bits in an Array" in the revisions of the book 'Hacker's Delight' explains more superior methods than the naive method.
http://www.hackersdelight.org/revisions.pdf
http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt
My benchmark results on Intel Core i3 CPU with 32-bit kernel showed 50% faster for 8192 bits bitmap. However, it is not faster for small bitmap (< BITS_PER_LONG * 8) than the naive method. So if the bitmap size is known to be small at compile time, use the naive method.
...
extern void bitmap_clear(unsigned long *map, int start, int nr);
include/linux/bitmap.h static inline int bitmap_weight(const unsigned long *src, int nbits) · line 280
Quoted 3 lines
include/linux/bitmap.h +0 -0
@@ -277,7 +278,9 @@ static inline int bitmap_weight(const unsigned long *src, int nbits)
  {
       if (small_const_nbits(nbits))
               return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
Why do we require a constant_p `nbits' for this case?
include/linux/bitmap.h static inline int bitmap_weight(const unsigned long *src, int nbits) · line 284
Quoted 5 lines
include/linux/bitmap.h +3 -1
-     return __bitmap_weight(src, nbits);
+     else if (__builtin_constant_p(nbits) && (nbits) < BITS_PER_LONG * 8)
+             return __bitmap_weight(src, nbits);
+     return __bitmap_weight_fast(src, nbits);
  }

Quoted 4 lines

BITS_PER_LONG*8 sounds like a large bitmap: 256 or 512 entries. Will the kernel call __bitmap_weight_fast() sufficiently often to make this extra code worth merging?

I roughly checked the call sites of bitmap_weight() and picked up some outstanding usages below.

Some filesystems (udf, omfs, ntfs, and hpfs) use bitmap_weight() to the block size bytes region in statfs() path.

num_online_cpus() and the variants are bitmap_weight() to the NR_CPUS bitmap and num_online_nodes() and the variants are to the MAX_NUMNODES bitmap. So these bitmaps could be large on extremely large system.

bm_count_bits() in drivers/block/drbd/drbd_bitmap.c computes the population count for multiple pages. But it is currently open-coded loops with hweight_long() which can be converted to bitmap_weight().

I consider introducing bitmap_weight_large() which is specialized for the large bitmap instead of optimizing bitmap_weight() and replace the call sites like above.

Andrew Morton

maintainer

2012-05-14 20:36 UTC #3 lore raw

Quoted 29 lines · On Mon, 14 May 2012 06:50:15 +0900 Akinobu Mita <[email protected]> wrote:

2012/5/12 Andrew Morton <[email protected]>:
Quoted 28 lines
Quoted 20 lines · On Fri, 11 May 2012 23:10:14 +0900 Akinobu Mita <[email protected]> wrote:
The current implementation of bitmap_weight simply evaluates the population count for each long word of the array, and adds.
The subsection "Counting 1-bits in an Array" in the revisions of the book 'Hacker's Delight' explains more superior methods than the naive method.
http://www.hackersdelight.org/revisions.pdf
http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt
My benchmark results on Intel Core i3 CPU with 32-bit kernel showed 50% faster for 8192 bits bitmap. However, it is not faster for small bitmap (< BITS_PER_LONG * 8) than the naive method. So if the bitmap size is known to be small at compile time, use the naive method.
...
extern void bitmap_clear(unsigned long *map, int start, int nr);
include/linux/bitmap.h static inline int bitmap_weight(const unsigned long *src, int nbits) · line 280
Quoted 3 lines
include/linux/bitmap.h +0 -0
@@ -277,7 +278,9 @@ static inline int bitmap_weight(const unsigned long *src, int nbits)
 {
      if (small_const_nbits(nbits))
              return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
Why do we require a constant_p `nbits' for this case?

^^ this?

Quoted 21 lines

Quoted 10 lines
Review static inline int bitmap_weight(const unsigned long *src, int nbits) · line 284
Quoted 5 lines
(quoted diff) +3 -1
-     return  bitmap_weight(src, nbits);
+     else if ( builtin_constant_p(nbits) && (nbits) < BITS_PER_LONG * 8)
+             return  bitmap_weight(src, nbits);
+     return  bitmap_weight_fast(src, nbits);
 }
BITS_PER_LONG*8 sounds like a large bitmap: 256 or 512 entries. Will the kernel call bitmap_weight_fast() sufficiently often to make this extra code worth merging?
I roughly checked the call sites of bitmap_weight() and picked up some outstanding usages below.
Some filesystems (udf, omfs, ntfs, and hpfs) use bitmap_weight() to the block size bytes region in statfs() path.
num_online_cpus() and the variants are bitmap_weight() to the NR_CPUS bitmap and num_online_nodes() and the variants are to the MAX_NUMNODES bitmap. So these bitmaps could be large on extremely large system.

Quoted 7 lines

bm_count_bits() in drivers/block/drbd/drbd_bitmap.c computes the population count for multiple pages. But it is currently open-coded loops with hweight_long() which can be converted to bitmap_weight().
I consider introducing bitmap_weight_large() which is specialized for the large bitmap instead of optimizing bitmap_weight() and replace the call sites like above.

I don't see much advantage to that - it would be better if bitmap_weight() Just Works.

Akinobu Mita

author

2012-05-15 11:58 UTC #4 lore raw

2012/5/15 Andrew Morton <[email protected]>:

Quoted 33 lines

Quoted 29 lines · On Mon, 14 May 2012 06:50:15 +0900 Akinobu Mita <[email protected]> wrote:
2012/5/12 Andrew Morton <[email protected]>:
Quoted 28 lines
Quoted 20 lines · On Fri, 11 May 2012 23:10:14 +0900 Akinobu Mita <[email protected]> wrote:
The current implementation of bitmap_weight simply evaluates the population count for each long word of the array, and adds.
The subsection "Counting 1-bits in an Array" in the revisions of the book 'Hacker's Delight' explains more superior methods than the naive method.
http://www.hackersdelight.org/revisions.pdf
http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt
My benchmark results on Intel Core i3 CPU with 32-bit kernel showed 50% faster for 8192 bits bitmap. However, it is not faster for small bitmap (< BITS_PER_LONG * 8) than the naive method. So if the bitmap size is known to be small at compile time, use the naive method.
...
extern void bitmap_clear(unsigned long *map, int start, int nr);
include/linux/bitmap.h static inline int bitmap_weight(const unsigned long *src, int nbits) · line 280
Quoted 3 lines
include/linux/bitmap.h +0 -0
@@ -277,7 +278,9 @@ static inline int bitmap_weight(const unsigned long *src, int nbits)
  {
       if (small_const_nbits(nbits))
               return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
Why do we require a constant_p `nbits' for this case?

Quoted 1 line

^^ this?

The commit 4b0bc0bca83f3fb7cf920e2ec80684c15d2269c0 "bitmap: test for constant as well as small size for inline versions" explains that it's for reducing text size, especially for the variable cpumasks.

Quoted 25 lines

Quoted 25 lines
Quoted 10 lines
Review static inline int bitmap_weight(const unsigned long *src, int nbits) · line 284
Quoted 5 lines
(quoted diff) +3 -1
-     return  bitmap_weight(src, nbits);
+     else if ( builtin_constant_p(nbits) && (nbits) < BITS_PER_LONG * 8)
+             return  bitmap_weight(src, nbits);
+     return  bitmap_weight_fast(src, nbits);
  }
BITS_PER_LONG*8 sounds like a large bitmap: 256 or 512 entries. Will the kernel call bitmap_weight_fast() sufficiently often to make this extra code worth merging?
I roughly checked the call sites of bitmap_weight() and picked up some outstanding usages below.
Some filesystems (udf, omfs, ntfs, and hpfs) use bitmap_weight() to the block size bytes region in statfs() path.
num_online_cpus() and the variants are bitmap_weight() to the NR_CPUS bitmap and num_online_nodes() and the variants are to the MAX_NUMNODES bitmap. So these bitmaps could be large on extremely large system.
bm_count_bits() in drivers/block/drbd/drbd_bitmap.c computes the population count for multiple pages. But it is currently open-coded loops with hweight_long() which can be converted to bitmap_weight().

Quoted 6 lines

Quoted 3 lines
I consider introducing bitmap_weight_large() which is specialized for the large bitmap instead of optimizing bitmap_weight() and replace the call sites like above.
I don't see much advantage to that - it would be better if bitmap_weight() Just Works.

OK, I withdraw the idea of bitmap_weight_large(). Do you still have doubts about merging this and want examples counting large bitmap popcount in kernel?

Akinobu Mita

author

2012-05-25 22:57 UTC #5 lore raw

In reply to Akinobu Mita

2012/5/11 Akinobu Mita <[email protected]>:

Quoted 7 lines

The current implementation of bitmap_weight simply evaluates the population count for each long word of the array, and adds.
The subsection "Counting 1-bits in an Array" in the revisions of the book 'Hacker's Delight' explains more superior methods than the naive method.

Quoted 8 lines

http://www.hackersdelight.org/revisions.pdf
http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt
My benchmark results on Intel Core i3 CPU with 32-bit kernel showed 50% faster for 8192 bits bitmap. However, it is not faster for small bitmap (< BITS_PER_LONG * 8) than the naive method. So if the bitmap size is known to be small at compile time, use the naive method.

My benchmark was bogus. I used __sw_hweight32 for hweight_long. It is much slower on x86 with X86_FEATURE_POPCNT.

This patch slows bitmap_weight(). So please drop this patch (bitmap_weight-optimize-for-large-bitmaps.patch) from -mm tree.