diff options
author | Alexander van Heukelum <heukelum@mailshack.com> | 2008-04-01 17:42:21 +0200 |
---|---|---|
committer | Ingo Molnar <mingo@elte.hu> | 2008-04-26 19:21:17 +0200 |
commit | 3a48305028aa38afba93fc05066c71a6ee668ad8 (patch) | |
tree | 5fd5b9bd9b4daa7cafb87c2706693fe57bc8af51 | |
parent | 2aba6925fdb96428d1129a61b1233597a03a387b (diff) | |
download | linux-3a48305028aa38afba93fc05066c71a6ee668ad8.tar.gz linux-3a48305028aa38afba93fc05066c71a6ee668ad8.tar.bz2 linux-3a48305028aa38afba93fc05066c71a6ee668ad8.zip |
x86: optimize find_first_bit for small bitmaps
Avoid a call to find_first_bit if the bitmap size is know at
compile time and small enough to fit in a single long integer.
Modeled after an optimization in the original x86_64-specific
code.
Signed-off-by: Alexander van Heukelum <heukelum@fastmail.fm>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
-rw-r--r-- | include/linux/bitops.h | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 355d67ba3bdc..48bde600a2db 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -127,6 +127,20 @@ extern unsigned long __find_first_bit(const unsigned long *addr, static __always_inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size) { + /* Avoid a function call if the bitmap size is a constant */ + /* and not bigger than BITS_PER_LONG. */ + + /* insert a sentinel so that __ffs returns size if there */ + /* are no set bits in the bitmap */ + if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) + return __ffs((*addr) | (1ul << size)); + + /* the result of __ffs(0) is undefined, so it needs to be */ + /* handled separately */ + if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) + return ((*addr) == 0) ? BITS_PER_LONG : __ffs(*addr); + + /* size is not constant or too big */ return __find_first_bit(addr, size); } @@ -143,6 +157,21 @@ extern unsigned long __find_first_zero_bit(const unsigned long *addr, static __always_inline unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) { + /* Avoid a function call if the bitmap size is a constant */ + /* and not bigger than BITS_PER_LONG. */ + + /* insert a sentinel so that __ffs returns size if there */ + /* are no set bits in the bitmap */ + if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) { + return __ffs(~(*addr) | (1ul << size)); + } + + /* the result of __ffs(0) is undefined, so it needs to be */ + /* handled separately */ + if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) + return (~(*addr) == 0) ? BITS_PER_LONG : __ffs(~(*addr)); + + /* size is not constant or too big */ return __find_first_zero_bit(addr, size); } #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ |