[PATCH v2] bitmap: speedup in bitmap_find_free_region when order is 0

[PATCH v2] bitmap: speedup in bitmap_find_free_region when order is 0

[Chanho Min]

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.

Signed-off-by: Chanho Min <chanho.min@lge.com>
---
 lib/bitmap.c |   36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 06f7e4f..663fc28 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -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;
-- 
1.7.9.5

Re: [PATCH v2] bitmap: speedup in bitmap_find_free_region when order is 0

[Andrew Morton]

On Tue,  9 Apr 2013 11:44:46 +0900 Chanho Min <chanho.min@lge.com> 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.
> 
> ...
>
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -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);

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

> +	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.

> +		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;

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:

--- a/lib/bitmap.c~a
+++ a/lib/bitmap.c
@@ -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.

Re: [PATCH v2] bitmap: speedup in bitmap_find_free_region when order is 0

[Joe Perches]

On Mon, 2013-04-08 at 20:10 -0700, Andrew Morton wrote:
> > --- a/lib/bitmap.c
[]
> > +	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);
		}

Re: [PATCH v2] bitmap: speedup in bitmap_find_free_region when order is 0

[Andrew Morton]

On Mon, 08 Apr 2013 20:18:20 -0700 Joe Perches <joe@perches.com> wrote:

> On Mon, 2013-04-08 at 20:10 -0700, Andrew Morton wrote:
> > > --- a/lib/bitmap.c
> []
> > > +	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)

> Adding --strict does bleat though.

And let's make it default please.

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

checkpatch: Warn on space before semicolon

[Joe Perches]

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

Signed-off-by: Joe Perches <joe@perches.com>
---
>> 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(-)

diff --git a/scripts/checkpatch.pl b/scripts/checkpatch.pl
index b28cc38..90eb022 100755
--- a/scripts/checkpatch.pl
+++ b/scripts/checkpatch.pl
@@ -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.

Re: [PATCH v2] bitmap: speedup in bitmap_find_free_region when order is 0

[Andrew Morton]

On Tue, 9 Apr 2013 15:34:44 +0900 "Chanho Min" <chanho.min@lge.com> wrote:

> >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.

> 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.