bitmap: speedup in bitmap_find_free_region when order is 0
Subsystems (2)
PATCH 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 be speed up significantly.
--- lib/bitmap.c | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+)
lib/bitmap.c +34 -0
@@ -1099,6 +1099,37 @@ 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, i; +unsigned long mask = (unsigned long )(~((unsigned long )0 )); +int nlongs_reg =BITS_TO_LONGS (bits); + +for (i =0 ; i < nlongs_reg ; i++) { +if ((bitmap[i] & mask) != mask) { +for (pos =0 ; pos <BITS_PER_LONG ; 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 +1147,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 3 lines · On Mon, 8 Apr 2013 11:23:48 +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.
That seems sensible. I assume-without-checking that single-bit is a common case?
Quoted 16 lines
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 be speed up significantly.
lib/bitmap.c +4
-0@@ -1099,6 +1099,37 @@ 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, i; +unsigned long mask = (unsigned long )(~((unsigned long )0 ));
That seems unnecessarily complicated. "unsigned long mask = -1;" works :)
lib/bitmap.c done: · line 1119
Quoted 4 lines
lib/bitmap.c +4
-0+int nlongs_reg =BITS_TO_LONGS (bits); + +for (i =0 ; i < nlongs_reg ; i++) { +if ((bitmap[i] & mask) != mask) {
But here we could just do "if (bitmap[i] != -1)". Or ~0UL.
lib/bitmap.c done: · line 1130
Quoted 11 lines
lib/bitmap.c +11
-0+for (pos =0 ; pos <BITS_PER_LONG ; 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 ; +}
afacit the code is buggy - if `bits' is not an exact multiple of BITS_PER_LONG, this search will wander off the end of the specified region?
Quoted 14 lines
lib/bitmap.c +4
-0+/** * 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 +1147,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 ;
Quoted 2 lines · Andrew Morton
Quoted 1 line · On Mon, 8 Apr 2013 11:23:48 +0900 Chanho Min <[email protected]> wrote:
---
a/lib/bitmap.c
[]
Quoted 1 line
Quoted 1 line
+static int
__bitmap_find_free_one(unsigned long *bitmap, int bits)
[]
Quoted 3 lines
lib/bitmap.c done: · line 1115
Quoted 1 line
lib/bitmap.c +1
-0+unsigned long mask = (unsigned long )(~((unsigned long )0 ));That seems unnecessarily complicated. "unsigned long mask = -1;" works :)
So would ULONG_MAX or just ~0UL