login
Header Space

 
 

[PATCH] x86: optimize find_first_bit for small bitmaps

Score:
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]
To: Ingo Molnar <mingo@...>
Cc: Andi Kleen <andi@...>, LKML <linux-kernel@...>, Alexander van Heukelum <heukelum@...>
Date: Tuesday, April 1, 2008 - 11:42 am

[PATCH] 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>

---
 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 355d67b..48bde60 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 */
-- 
1.5.2.5


--
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]

Messages in current thread:
[PATCH] x86: generic versions of find_first_(zero_)bit, conv..., Alexander van Heukelum, (Mon Mar 31, 1:15 pm)
Re: [PATCH] x86: generic versions of find_first_(zero_)bit, ..., Alexander van Heukelum, (Tue Apr 1, 5:46 am)
Re: [PATCH] x86: generic versions of find_first_(zero_)bit, ..., Alexander van Heukelum, (Sun Apr 6, 2:51 pm)
Re: [PATCH] x86: generic versions of find_first_(zero_)bit, ..., Alexander van Heukelum, (Mon Apr 7, 6:25 am)
Alternative implementation of the generic __ffs, Alexander van Heukelum, (Fri Apr 18, 4:18 pm)
Re: Alternative implementation of the generic __ffs, dean gaudet, (Fri Apr 18, 7:46 pm)
Re: Alternative implementation of the generic __ffs, Harvey Harrison, (Fri Apr 18, 8:09 pm)
Re: Alternative implementation of the generic __ffs, dean gaudet, (Fri Apr 18, 8:20 pm)
Re: Alternative implementation of the generic __ffs, Joe Perches, (Fri Apr 18, 8:58 pm)
Re: Alternative implementation of the generic __ffs, Harvey Harrison, (Fri Apr 18, 9:04 pm)
Re: Alternative implementation of the generic __ffs, dean gaudet, (Fri Apr 18, 9:11 pm)
Re: Alternative implementation of the generic __ffs, Joe Perches, (Fri Apr 18, 10:55 pm)
Re: Alternative implementation of the generic __ffs, Matti Aarnio, (Sat Apr 19, 6:29 pm)
Re: Alternative implementation of the generic __ffs, Joe Perches, (Sat Apr 19, 11:06 pm)
Re: Alternative implementation of the generic __ffs, Alexander van Heukelum, (Sun Apr 20, 4:42 am)
Re: Alternative implementation of the generic __ffs, Matti Aarnio, (Sun Apr 20, 8:31 am)
Re: Alternative implementation of the generic __ffs, Alexander van Heukelum, (Mon Apr 21, 7:43 am)
Re: Alternative implementation of the generic __ffs, dean gaudet, (Sat Apr 19, 12:13 am)
Re: Alternative implementation of the generic __ffs, Alexander van Heukelum, (Sat Apr 19, 8:10 am)
Re: Alternative implementation of the generic __ffs, Joe Perches, (Sat Apr 19, 2:17 pm)
Re: Alternative implementation of the generic __ffs, Alexander van Heukelum, (Sat Apr 19, 4:26 pm)
Re: Alternative implementation of the generic __ffs, Mikael Pettersson, (Sat Apr 19, 6:05 am)
[PATCH] x86: switch x86_64 to generic find_first_bit, Alexander van Heukelum, (Tue Apr 1, 11:41 am)
[PATCH] x86: optimize find_first_bit for small bitmaps, Alexander van Heukelum, (Tue Apr 1, 11:42 am)
[PATCH] x86: remove x86-specific implementations of find_fir..., Alexander van Heukelum, (Tue Apr 1, 11:47 am)
Re: [PATCH] x86: remove x86-specific implementations of find..., Alexander van Heukelum, (Thu Apr 3, 5:34 am)
Re: [PATCH] x86: generic versions of find_first_(zero_)bit, ..., Stephen Hemminger, (Mon Mar 31, 1:22 pm)
Re: [PATCH] x86: generic versions of find_first_(zero_)bit, ..., Alexander van Heukelum, (Mon Mar 31, 3:38 pm)
speck-geostationary