bitmap: speedup in bitmap_find_free_region when order is 0
Subsystems (3)
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
@@ -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
Andrew Morton
maintainerQuoted 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 ofBITS_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 lonint 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.
Joe Perches
maintainerQuoted 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);
}Andrew Morton
maintainerQuoted 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);
}Joe Perches
maintainercheckpatch: 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
@@ -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]
Andrew Morton
maintainerQuoted 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.