Skip to contentSkip to conversation

bitmap: speedup in bitmap_find_free_region when order is 0

PATCH In review Chanho Min 3 participants 6 messages Apr 9, 2013 1 message not in the archive

Subsystems (3)
lore
Share & tools
lore

Chanho Min

author
#0 lore raw

PATCH v2 1/1 bitmap: speedup in bitmap_find_free_region when order is 0

If bitmap_find_free_region() is called with order=0, We can reduce for-loops to find 1 free bit. First, It scans bitmap array by the increment of long type, then find 1 free bit within 1 long type value.

In 32 bits system and 1024 bits size, in the worst case, We need 1024 for-loops to find 1 free bit. But, If This is applied, it takes 64 for-loops. Instead, if free bit is in the first index of the bitmaps, It will be needed additional 1 for-loop. But from second index, It will speed up significantly.

Changes compared to v1:
- Modified unnecessarily complicated code.
- Fixed the buggy code if `bits' is not an multiple of BITS_PER_LONG.

---
 lib/bitmap.c |   36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
lib/bitmap.c +36 -0
index 06f7e4f..663fc28 100644
@@ -1099,6 +1099,39 @@ done:
 }
 
 /**
+ * bitmap_find_free_one - find a mem region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@bits: number of bits in the bitmap
+ *
+ * Find one of free (zero) bits in a @bitmap of @bits bits and
+ * allocate them (set them to one).
+ *
+ * Return the bit offset in bitmap of the allocated region,
+ * or -errno on failure.
+ */
+static int __bitmap_find_free_one(unsigned long *bitmap, int bits)
+{
+	int pos, end = BITS_PER_LONG, i;
+	int nlongs_reg = BITS_TO_LONGS(bits);
+	int last_bits = bits % BITS_PER_LONG;
+
+	for (i = 0 ; i < nlongs_reg ; i++) {
+		if (bitmap[i] != ~0UL) {
+			if (i == (nlongs_reg - 1) && last_bits)
+				end = last_bits;
+			for (pos = 0 ; pos < end ; pos++) {
+				if (!__reg_op(&bitmap[i], pos, 0,
+					REG_OP_ISFREE))
+					continue;
+				__reg_op(&bitmap[i], pos, 0, REG_OP_ALLOC);
+				return pos;
+			}
+		}
+	}
+	return -ENOMEM;
+}
+
+/**
  * bitmap_find_free_region - find a contiguous aligned mem region
  *	@bitmap: array of unsigned longs corresponding to the bitmap
  *	@bits: number of bits in the bitmap
@@ -1116,6 +1149,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
 	int pos, end;		/* scans bitmap by regions of size order */
 
+	if (order == 0)
+		return __bitmap_find_free_one(bitmap, bits);
+
 	for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
 		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			continue;
Signature · 1 line
1.7.9.5
maintainer
#1 lore raw
Quoted 26 lines · On Tue, 9 Apr 2013 11:44:46 +0900 Chanho Min <[email protected]> wrote:

If bitmap_find_free_region() is called with order=0, We can reduce for-loops to find 1 free bit. First, It scans bitmap array by the increment of long type, then find 1 free bit within 1 long type value.

In 32 bits system and 1024 bits size, in the worst case, We need 1024 for-loops to find 1 free bit. But, If This is applied, it takes 64 for-loops. Instead, if free bit is in the first index of the bitmaps, It will be needed additional 1 for-loop. But from second index, It will speed up significantly.

Changes compared to v1:
- Modified unnecessarily complicated code.
- Fixed the buggy code if `bits' is not an multiple of BITS_PER_LONG.

...

lib/bitmap.c +4 -0
@@ -1099,6 +1099,39 @@ done:
 }
 
 /**
+ * bitmap_find_free_one - find a mem region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@bits: number of bits in the bitmap
+ *

lib/bitmap.c done: · line 1115

Quoted 10 lines
lib/bitmap.c +10 -0
+ * Find one of free (zero) bits in a @bitmap of @bits bits and
+ * allocate them (set them to one).
+ *
+ * Return the bit offset in bitmap of the allocated region,
+ * or -errno on failure.
+ */
+static int __bitmap_find_free_one(unsigned long *bitmap, int bits)
+{
+	int pos, end = BITS_PER_LONG, i;
+	int nlongs_reg = BITS_TO_LONGS(bits);

Still wrong, I think - BITS_TO_LONG() rounds up.

lib/bitmap.c done: · line 1118

Quoted 3 lines
lib/bitmap.c +3 -0
+	int last_bits = bits % BITS_PER_LONG;
+
+	for (i = 0 ; i < nlongs_reg ; i++) {

No space before the semicolon, please. checkpatch should warn about this but it seems to be broken.

Quoted 20 lines
lib/bitmap.c +16 -0
+		if (bitmap[i] != ~0UL) {
+			if (i == (nlongs_reg - 1) && last_bits)
+				end = last_bits;
+			for (pos = 0 ; pos < end ; pos++) {
+				if (!__reg_op(&bitmap[i], pos, 0,
+					REG_OP_ISFREE))
+					continue;
+				__reg_op(&bitmap[i], pos, 0, REG_OP_ALLOC);
+				return pos;
+			}
+		}
+	}
+	return -ENOMEM;
+}
+
+/**
  * bitmap_find_free_region - find a contiguous aligned mem region
  *	@bitmap: array of unsigned longs corresponding to the bitmap
  *	@bits: number of bits in the bitmap

lib/bitmap.c int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) · line 1157

Quoted 9 lines
lib/bitmap.c +3 -0
@@ -1116,6 +1149,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
 	int pos, end;		/* scans bitmap by regions of size order */
 
+	if (order == 0)
+		return __bitmap_find_free_one(bitmap, bits);
+
 	for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
 		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			continue;

It seems excessively complicated to me. Why not change bitmap_find_free_region() to skip the leading all-ones words and when it finds a not-all-ones word, adjust `pos' then fall into the existing bit-at-a-time search?

In fact we could use the 64-bits-at-a-time search for allocations other than order-zero:

lib/bitmap.c renamed from lib/bitmap.c~a +6 -0
@@ -1117,6 +1117,12 @@ int bitmap_find_free_region(unsigned lon
 	int pos, end;		/* scans bitmap by regions of size order */
 
 	for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
+		if (pos & (BITS_PER_LONG - 1) == 0) {
+			if (bitmap[pos / BITS_PER_LONG] == ~0UL) {
+				pos += BITS_PER_LONG;
+				continue;
+			}
+		}
 		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			continue;
 		__reg_op(bitmap, pos, order, REG_OP_ALLOC);

(that's presumably slow and buggy, but you get the idea ;))

Another obvious inefficiency in bitmap_find_free_region() is that when it inspects a region at `pos' for 1<<order zero bits and fails to find them, it resumes the search at pos+1. Dumb - it should resume searching at the next-one-bit, rounded up to the next 1<<order.

Obviously nobody tried very hard here - is any poor soul using this code for large bitmaps? I guess "yes", as 1024-CPU machines exist.

maintainer
#2 lore raw
Quoted 1 line · Andrew Morton
Quoted 1 line

--- a/lib/bitmap.c

[]

Quoted 4 lines

Review

Quoted 1 line
(quoted diff) +1 -0
+	for (i = 0 ; i < nlongs_reg ; i++) {

No space before the semicolon, please. checkpatch should warn about this but it seems to be broken.

There's no specific CodingStyle violation here
Adding --strict does bleat though.

# check for whitespace before a non-naked semicolon
		if ($line =~ /^\+.*\S\s+;/) {
			CHK("SPACING",
			    "space prohibited before semicolon\n" . $herecurr);
		}
maintainer
#3 lore raw
Quoted 9 lines · On Mon, 08 Apr 2013 20:18:20 -0700 Joe Perches <[email protected]> wrote:
Quoted 1 line · Andrew Morton
Quoted 1 line

--- a/lib/bitmap.c

[]

Quoted 4 lines

Review

Quoted 1 line
(quoted diff) +1 -0
+	for (i = 0 ; i < nlongs_reg ; i++) {

No space before the semicolon, please. checkpatch should warn about this but it seems to be broken.

There's no specific CodingStyle violation here

Let's fix CodingStyle then? Nobody puts spaces before semis - perish the thought! (I count 4,254,057 versus 8,416 in .c)

Quoted 1 line

Adding --strict does bleat though.

And let's make it default please.

Quoted 6 lines
# check for whitespace before a non-naked semicolon
		if ($line =~ /^\+.*\S\s+;/) {
			CHK("SPACING",
			    "space prohibited before semicolon\n" . $herecurr);
		}
maintainer
#4 lore raw

checkpatch: Warn on space before semicolon

Make space before semicolon a warning instead
of a --strict CHK test.

---

Quoted 2 lines
Quoted 1 line

There's no specific CodingStyle violation here

Let's fix CodingStyle then?

I'll leave that bit for you...

 scripts/checkpatch.pl | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
scripts/checkpatch.pl +2 -2
index b28cc38..90eb022 100755
@@ -2514,8 +2514,8 @@ sub process {
 
 # check for whitespace before a non-naked semicolon
 		if ($line =~ /^\+.*\S\s+;/) {
-			CHK("SPACING",
-			    "space prohibited before semicolon\n" . $herecurr);
+			WARN("SPACING",
+			     "space prohibited before semicolon\n" . $herecurr);
 		}
 
 # Check operator spacing.

A message that is not in the archive (sent off-list or not yet received): [email protected]

maintainer
#6 lore raw
Quoted 6 lines · On Tue, 9 Apr 2013 15:34:44 +0900 "Chanho Min" <[email protected]> wrote:
Quoted 4 lines

It seems excessively complicated to me. Why not change bitmap_find_free_region() to skip the leading all-ones words and when it finds a not-all-ones word, adjust `pos' then fall into the existing bit-at-a-time search?

Do we need the additional 'if' inside the for loop for implementing it?

It was just a concept - there are various ways of optimizing a real implementation. Move the code into userspace then run some microbenchmarks.

Quoted 2 lines

I thought the separation of the routine for order=0 is the way to avoid the impact on the existing codes and its performance.

The existing code doesn't have any performance ;) It's so darn slow that even a minor effort here will yield large (ie order-of-magnitude) performance improvements.