lib: find_*_bit reimplementation
This patchset does rework to find_bit function family to achieve better
performance, and decrease size of text. All rework is done in patch 1.
Patches 2 and 3 are about code moving and renaming.
It was boot-tested on x86_64 and MIPS (big-endian) machines.
Performance tests were ran on userspace with code like this:
/* addr[] is filled from /dev/urandom */
start = clock();
while (ret < nbits)
ret = find_next_bit(addr, nbits, ret + 1);
end = clock();
printf("%ld\t", (unsigned long) end - start);
On Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz measurements are: (for
find_next_bit, nbits is 8M, for find_first_bit - 80K)
find_next_bit: find_first_bit:
new current new current
26932 43151 14777 14925
26947 43182 14521 15423
26507 43824 15053 14705
27329 43759 14473 14777
26895 43367 14847 15023
26990 43693 15103 15163
26775 43299 15067 15232
27282 42752 14544 15121
27504 43088 14644 14858
26761 43856 14699 15193
26692 43075 14781 14681
27137 42969 14451 15061
... ...
find_next_bit performance gain is 35-40%;
find_first_bit - no measurable difference.
On ARM machine, there is arch-specific implementation for find_bit.
Thanks a lot to George Spelvin and Rasmus Villemoes for hints and
helpful discussions.
This patch (of 3):
New implementations takes less space in source file (see diffstat) and in
object. For me it's 710 vs 453 bytes of text. It also shows better
performance.
find_last_bit description fixed due to obvious typo.
[[email protected]: include linux/bitmap.h, per Rasmus]
Signed-off-by: Yury Norov <[email protected]>
Reviewed-by: Rasmus Villemoes <[email protected]>
Reviewed-by: George Spelvin <[email protected]>
Cc: Alexey Klimov <[email protected]>
Cc: David S. Miller <[email protected]>
Cc: Daniel Borkmann <[email protected]>
Cc: Hannes Frederic Sowa <[email protected]>
Cc: Lai Jiangshan <[email protected]>
Cc: Mark Salter <[email protected]>
Cc: AKASHI Takahiro <[email protected]>
Cc: Thomas Graf <[email protected]>
Cc: Valentin Rothberg <[email protected]>
Cc: Chris Wilson <[email protected]>
Signed-off-by: Andrew Morton <[email protected]>
Signed-off-by: Linus Torvalds <[email protected]>
3 files changed
