On Tue, 7 May 2013 17:15:53 +0900 Chanho Min <chanho....@lge.com> wrote:
> In bitmap_find_free_region, If we skip the all-ones words and find bits
> in a not-all-ones word, we can improve performance of it.
>
> For example, If bitmap_find_free_region() is called with order=0, 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, It will be needed additional if-comparison
> of every word and It can take time slightly as 'Test case 3'. But, In many
> cases, It will speed up significantly.
>
> ...
>
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -1114,14 +1114,21 @@ done:
> */
> int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
> {
> - int pos, end; /* scans bitmap by regions of size order */
> -
> - for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
> - if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
> - continue;
> - __reg_op(bitmap, pos, order, REG_OP_ALLOC);
> - return pos;
> - }
> + int pos, end, nbit, i; /* scans bitmap by regions of size order */
> + int nlongs = BITS_TO_LONGS(bits);
> +
> + for (i = 0; i < nlongs; i++)
> + if (bitmap[i] != ~0UL) {
> + pos = i * BITS_PER_LONG;
> + nbit = min(bits, pos + BITS_PER_LONG);
> + for (; (end = pos + (1 << order)) <= nbit; pos = end) {
> + if (!__reg_op(bitmap, pos, order,
> + REG_OP_ISFREE))
> + continue;
> + __reg_op(bitmap, pos, order, REG_OP_ALLOC);
> + return pos;
> + }
> + }
> return -ENOMEM;
It could be improved further by returning to the long-at-a-time search
if we failed to find a suffificiently large free region at `i'. Oh
well, I guess we can do that later if someone cares enough.
We now have a definition of four(!) locals on a single line followed by
a head-scratching comment which doesn't really pertain to any of those
locals anyway. Let's do this:
From: Andrew Morton <a...@linux-foundation.org>
Subject: lib-bitmapc-speed-up-bitmap_find_free_region-fix
reduce scope of locals, remove barely comprehensible comment
Cc: Chanho Min <chanho....@lge.com>
Cc: Jiri Kosina <jkos...@suse.cz>
Cc: Joe Perches <j...@perches.com>
Cc: Nadia Yvette Chambers <n...@holomorphy.com>
Cc: anish singh <anish198519851...@gmail.com>
Signed-off-by: Andrew Morton <a...@linux-foundation.org>
---
lib/bitmap.c | 8 +++++---
1 file changed, 5 insertions(+), 3 deletions(-)
diff -puN lib/bitmap.c~lib-bitmapc-speed-up-bitmap_find_free_region-fix
lib/bitmap.c
--- a/lib/bitmap.c~lib-bitmapc-speed-up-bitmap_find_free_region-fix
+++ a/lib/bitmap.c
@@ -1114,13 +1114,15 @@ done:
*/
int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
{
- int pos, end, nbit, i; /* scans bitmap by regions of size order */
int nlongs = BITS_TO_LONGS(bits);
+ int i;
for (i = 0; i < nlongs; i++)
if (bitmap[i] != ~0UL) {
- pos = i * BITS_PER_LONG;
- nbit = min(bits, pos + BITS_PER_LONG);
+ int pos = i * BITS_PER_LONG;
+ int nbit = min(bits, pos + BITS_PER_LONG);
+ int end;
+
for (; (end = pos + (1 << order)) <= nbit; pos = end) {
if (!__reg_op(bitmap, pos, order,
REG_OP_ISFREE))
_
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
