x86: Change x86 to use generic find_next_bit
Subsystems (5)
PATCH 1/1 x86: Change x86 to use generic find_next_bit
x86: Change x86 to use the generic find_next_bit implementation
The versions with inline assembly are in fact slower on the machines I tested them on (in userspace) (Athlon XP 2800+, p4-like Xeon 2.8GHz, AMD Opteron 270). The i386-version needed a fix similar to 06024f21 to avoid crashing the benchmark.
Benchmark using: gcc -fomit-frame-pointer -Os. For each bitmap size 1...512, for each possible bitmap with one bit set, for each possible
offset: find the position of the first bit starting at offset. If you follow ;). Times include setup of the bitmap and checking of the results.
Athlon Xeon Opteron 32/64bit
x86-specific: 0m3.692s 0m2.820s 0m3.196s / 0m2.480s
generic: 0m2.622s 0m1.662s 0m2.100s / 0m1.572s
If the bitmap size is not a multiple of BITS_PER_LONG, and no set (cleared) bit is found, find_next_bit (find_next_zero_bit) returns a value outside of the range [0,size]. The generic version always returns exactly size. The generic version also uses unsigned long everywhere, while the x86 versions use a mishmash of int, unsigned (int), long and unsigned long.
Using the generic version does give a slightly bigger kernel, though.
defconfig: text data bss dec hex filename x86-specific: 4738555 481232 626688 5846475 5935cb vmlinux (32 bit)
generic: 4738621 481232 626688 5846541 59360d vmlinux (32 bit)
x86-specific: 5392395 846568 724424 6963387 6a40bb vmlinux (64 bit)
generic: 5392458 846568 724424 6963450 6a40fa vmlinux (64 bit)
arch/x86/Kconfig | 3 ++ arch/x86/lib/Makefile | 2 +- arch/x86/lib/bitops_32.c | 70 ------------------------------------------- arch/x86/lib/bitops_64.c | 68 ----------------------------------------- include/asm-x86/bitops.h | 6 ++++ include/asm-x86/bitops_32.h | 16 ---------- include/asm-x86/bitops_64.h | 2 - lib/find_next_bit.c | 2 + 8 files changed, 12 insertions(+), 157 deletions(-)
---
Hi,
I think it would be a good idea to use the generic versions of find_next_bit and find_next_zero_bit. The i386 versions have a bug, and the generic ones are faster (in my probably not-so-representative micro-benchmark, that is).
Patch is against -x86#testing. It compiles.
Greetings,
Alexander
arch/x86/Kconfig +3 -0
@@ -83,6 +83,9 @@ config GENERIC_BUG def_bool y depends on BUG +config GENERIC_FIND_NEXT_BIT + def_bool y + config GENERIC_HWEIGHT def_bool y
arch/x86/lib/Makefile +1 -1
@@ -11,7 +11,7 @@ lib-y += memcpy_$(BITS).o ifeq ($(CONFIG_X86_32),y) lib-y += checksum_32.o lib-y += strstr_32.o - lib-y += bitops_32.o semaphore_32.o string_32.o + lib-y += semaphore_32.o string_32.o lib-$(CONFIG_X86_USE_3DNOW) += mmx_32.o else
arch/x86/lib/bitops_32.c deleted +0 -70
70 lines not on this page · raw message
arch/x86/lib/bitops_64.c +0 -68
88 lines not on this page · raw message
include/asm-x86/bitops.h +6 -0
@@ -312,6 +312,12 @@ static int test_bit(int nr, const volatile unsigned long *addr);#undef ADDR +unsigned long find_next_bit (const unsigned long *addr, +unsigned long size,unsigned long offset); +unsigned long find_next_zero_bit (const unsigned long *addr, +unsigned long size,unsigned long offset); + +#ifdef CONFIG_X86_32 # include "bitops_32.h" #else
include/asm-x86/bitops_32.h +0 -16
@@ -38,14 +38,6 @@ static inline int find_first_zero_bit(const unsigned long *addr, unsigned size) }/** -* find_next_zero_bit - find the first zero bit in a memory region -* @addr: The address to base the search on -* @offset: The bit number to start searching at -* @size: The maximum size to search -*/ -int find_next_zero_bit (const unsigned long *addr,int size,int offset); - -/** * __ffs - find first bit in word. * @word: The word to search *
@@ -81,14 +73,6 @@ static inline unsigned find_first_bit(const unsigned long *addr, unsigned size) }/** -* find_next_bit - find the first set bit in a memory region -* @addr: The address to base the search on -* @offset: The bit number to start searching at -* @size: The maximum size to search -*/ -int find_next_bit (const unsigned long *addr,int size,int offset); - -/** * ffz - find first zero in word. * @word: The word to search *
include/asm-x86/bitops_64.h +0 -2
@@ -6,9 +6,7 @@*/ extern long find_first_zero_bit (const unsigned long *addr,unsigned long size); -extern long find_next_zero_bit (const unsigned long *addr,long size,long offset);extern long find_first_bit (const unsigned long *addr,unsigned long size); -extern long find_next_bit (const unsigned long *addr,long size,long offset);/* return index of first bet set in val or max when no bit is set */ static inline long __scanbit (unsigned long val,unsigned long max)
lib/find_next_bit.c +2 -0
@@ -15,6 +15,8 @@#include <asm/byteorder.h> #define BITOP_WORD (nr) ((nr) / BITS_PER_LONG) +#undef find_next_bit +#undef find_next_zero_bit/** * find_next_bit - find the next set bit in a memory region
Quoted 13 lines · Alexander van Heukelum
x86: Change x86 to use the generic
find_next_bitimplementationThe versions with inline assembly are in fact slower on the machines I tested them on (in userspace) (Athlon XP 2800+, p4-like Xeon 2.8GHz, AMD Opteron 270). The i386-version needed a fix similar to
06024f21to avoid crashing the benchmark.Benchmark using: gcc -fomit-frame-pointer -Os. For each bitmap size 1...512, for each possible bitmap with one bit set, for each possible
offset: find the position of the first bit starting at offset. If you follow ;). Times include setup of the bitmap and checking of the results.
Quoted 3 lines
Athlon Xeon Opteron 32/64bitx86-specific: 0m3.692s 0m2.820s 0m3.196s / 0m2.480s
generic: 0m2.622s 0m1.662s 0m2.100s / 0m1.572s
ok, that's rather convincing.
the generic version in lib/find_next_bit.c is open-coded C which gcc can optimize pretty nicely.
the hand-coded assembly versions in arch/x86/lib/bitops_32.c mostly use the special x86 'bit search forward' (BSF) instruction - which i know from the days when the scheduler relied on it has some non-trivial setup costs. So especially when there's _small_ bitmasks involved, it's more expensive.
Quoted 6 lines
If the bitmap size is not a multiple of
BITS_PER_LONG, and no set (cleared) bit is found,find_next_bit(find_next_zero_bit) returns a value outside of the range [0,size]. The generic version always returns exactly size. The generic version also uses unsigned long everywhere, while the x86 versions use a mishmash of int, unsigned (int), long and unsigned long.
i'm not surprised that the hand-coded assembly versions had a bug ...
[ this means we have to test it quite carefully though, as lots of code
only ever gets tested on x86 so code could have built dependency on the buggy behavior. ]
Quoted 7 lines
Using the generic version does give a slightly bigger kernel, though.
defconfig: text data bss dec hex filename x86-specific: 4738555 481232 626688 5846475 5935cb vmlinux (32 bit)generic: 4738621 481232 626688 5846541 59360d vmlinux (32 bit)
x86-specific: 5392395 846568 724424 6963387 6a40bb vmlinux (64 bit)
generic: 5392458 846568 724424 6963450 6a40fa vmlinux (64 bit)
i'd not worry about that too much. Have you tried to build with:
CONFIG_CC_OPTIMIZE_FOR_SIZE=y
CONFIG_OPTIMIZE_INLINING=y
(the latter only available in x86.git)
Quoted 1 line
Patch is against -x86#testing. It compiles.
i've picked it up into x86.git, lets see how it goes in practice.
Ingo
Quoted 7 lines · Ingo Molnar
the generic version in
lib/find_next_bit.cis open-coded C which gcc can optimize pretty nicely.the hand-coded assembly versions in
arch/x86/lib/bitops_32.cmostly use the special x86 'bit search forward' (BSF) instruction - which i know from the days when the scheduler relied on it has some non-trivial setup
~14 cycles on K8 for memory, but if you stay in a register it is 8 cycles
Quoted 2 lines
costs. So especially when there's _small_ bitmasks involved, it's more expensive.
I had a patchkit some time ago to special case the max_bit <= 63 case and always use directly inlined stream lined single instruction assembler for that. There was still some issue and I dropped it then, but doing something like that makes still sense. Even if the BSF is slightly slower than the open coded version just getting rid of the CALL will make it a win and it could be also kept in a register so you get the 8 cycle variant (for which I doubt you can do it faster open coded)
The result would be that a standard for_each_cpu () in a NR_CPUS <= 64 kernel wouldn't have any unnecessary calls.
In general the problem of walking cpu masks is quite different from seaching ext2 bitmaps, so they likely should be special cased and optimized for each.
-Andi
Quoted 2 lines · Andi Kleen
I had a patchkit some time ago to special case the
max_bit<= 63 case
... never mind ... the patchkit is actually included. I had only dropped it at some point, but fixed later.
-Andi
Quoted 6 lines · Ingo Molnar
Quoted 3 lines
Athlon Xeon Opteron 32/64bitx86-specific: 0m3.692s 0m2.820s 0m3.196s / 0m2.480s
generic: 0m2.622s 0m1.662s 0m2.100s / 0m1.572sok, that's rather convincing.
Quoted 8 lines
the generic version in
lib/find_next_bit.cis open-coded C which gcc can optimize pretty nicely.the hand-coded assembly versions in
arch/x86/lib/bitops_32.cmostly use the special x86 'bit search forward' (BSF) instruction - which i know from the days when the scheduler relied on it has some non-trivial setup costs. So especially when there's _small_ bitmasks involved, it's more expensive.
Hi,
BSF is fine, it doesn't need any special setup. The problem is probably that the old versions use find_first_bit and find_first_zero_bit, which are also hand optimized versions... and they use "repe scasl/q". That's another little project ;).
Quoted 8 lines
Quoted 6 lines
If the bitmap size is not a multiple of
BITS_PER_LONG, and no set (cleared) bit is found,find_next_bit(find_next_zero_bit) returns a value outside of the range [0,size]. The generic version always returns exactly size. The generic version also uses unsigned long everywhere, while the x86 versions use a mishmash of int, unsigned (int), long and unsigned long.i'm not surprised that the hand-coded assembly versions had a bug ...
Not surprised about the bug, but it was in fact noticed, and fixed in x86_64!
Quoted 3 lines
[ this means we have to test it quite carefully though, as lots of code
only ever gets tested on x86 so code could have built dependency on the buggy behavior. ]
Agreed.
Quoted 9 lines
Quoted 7 lines
Using the generic version does give a slightly bigger kernel, though.
defconfig: text data bss dec hex filename x86-specific: 4738555 481232 626688 5846475 5935cb vmlinux (32 bit)generic: 4738621 481232 626688 5846541 59360d vmlinux (32 bit)
x86-specific: 5392395 846568 724424 6963387 6a40bb vmlinux (64 bit)
generic: 5392458 846568 724424 6963450 6a40fa vmlinux (64 bit)i'd not worry about that too much. Have you tried to build with:
I don't but I needed to compile something to test the build anyhow ;)
Quoted 2 lines
CONFIG_CC_OPTIMIZE_FOR_SIZE=y
CONFIG_OPTIMIZE_INLINING=y
This was defconfig in -x86#testing, they were both already enabled. Here is what you get with those options turned off ;).
text data bss dec hex filename
x86-specific: 5543996 481232 626688 6651916 65800c vmlinux (32 bit) generic: 5543880 481232 626688 6651800 657f98 vmlinux (32 bit) x86-specific: 6111834 846568 724424 7682826 753b0a vmlinux (64 bit) generic: 6111882 846568 724424 7682874 753b3a vmlinux (64 bit)
(and I double-checked the i386 results)
Quoted 5 lines
(the latter only available in x86.git)
Quoted 1 line
Patch is against -x86#testing. It compiles.
i've picked it up into x86.git, lets see how it goes in practice.
Thanks,
Alexander
Quoted 1 line
Ingo
Signature · 5 lines
Alexander van Heukelum [email protected] -- http://www.fastmail.fm - And now for something completely different…
Quoted 11 lines · Alexander van Heukelum
Quoted 10 lines
ok, that's rather convincing.
the generic version in
lib/find_next_bit.cis open-coded C which gcc can optimize pretty nicely.the hand-coded assembly versions in
arch/x86/lib/bitops_32.cmostly use the special x86 'bit search forward' (BSF) instruction - which i know from the days when the scheduler relied on it has some non-trivial setup costs. So especially when there's _small_ bitmasks involved, it's more expensive.
Quoted 3 lines
Hi,
BSF is fine, it doesn't need any special setup. [...]
under "setup costs" i mean cycles spent by the CPU itself - the instruction itself is simple (of course) and needs no setup. If you look at BSF performance you'll see that it has nontrivial overhead.
Ingo
lib/find_next_bit.c line 19
Quoted 8 lines · Alexander van Heukelum
lib/find_next_bit.c +2
-0@@ -15,6 +15,8 @@#include <asm/byteorder.h> #define BITOP_WORD (nr) ((nr) / BITS_PER_LONG) +#undef find_next_bit +#undef find_next_zero_bit
this bit looks weird - did you need it for testing?
Ingo
Quoted 11 lines · Ingo Molnar
lib/find_next_bit.c line 19
Quoted 8 lines · Alexander van Heukelum
lib/find_next_bit.c +2
-0@@ -15,6 +15,8 @@#include <asm/byteorder.h> #define BITOP_WORD (nr) ((nr) / BITS_PER_LONG) +#undef find_next_bit +#undef find_next_zero_bitthis bit looks weird - did you need it for testing?
Worse, it's needed to get x86_64 to compile.
They are defined in include/asm-x86/bitops_64.h (which gets included). They are used to optimize the case where the bitmap size is known at compile time and not larger than BITS_PER_LONG. Undeffing them here is the easiest way to get things to compile, here.
Greetings,
Alexander
Signature · 1 line
http://www.fastmail.fm - The way an email service should be
Quoted 6 lines · Alexander van Heukelum
Quoted 5 lines
lib/find_next_bit.c line 19
Quoted 3 lines
#define
BITOP_WORD(nr)((nr) /BITS_PER_LONG)lib/find_next_bit.c +2
-0+#undef find_next_bit +#undef find_next_zero_bitthis bit looks weird - did you need it for testing?
Quoted 6 lines
Worse, it's needed to get
x86_64to compile.They are defined in
include/asm-x86/bitops_64.h(which gets included). They are used to optimize the case where the bitmap size is known at compile time and not larger thanBITS_PER_LONG. Undeffing them here is the easiest way to get things to compile, here.
ok - but this needs to be solved in a cleaner way. That build-time optimization needs to be pushed into generic code so that 32-bit x86 and other architectures can make use of it as well. The lib/find_next_bit.c functions should be named __find_next_bit() or so.
Ingo
Quoted 3 lines · Ingo Molnar
ok - but this needs to be solved in a cleaner way. That build-time optimization needs to be pushed into generic code so that 32-bit x86 and
It probably doesn't make sense in generic code because it will be too large open coded.
-Andi
[RFC/PATCH] x86: Optimize find_next_(zero_)bit for small constant-size bitmaps
In reply to Ingo Molnarx86: Optimize find_next_(zero_)bit for small constant-size bitmaps
NOTE: This is not well tested. I'm also quite unsure if this makes the pre-processor situation any better.
On an i386 defconfig (the x86#testing one), the size of vmlinux hardly changes with this applied. I have observed only four places where this optimization avoids a call into find_next_bit:
In the functions return_unused_surplus_pages, alloc_fresh_huge_page, and adjust_pool_surplus, this patch avoids a call for a 1-bit bitmap. In __next_cpu a call is avoided for a 32-bit bitmap. That's it.
On x86_64 I observed the following (I did not look closely yet, though).
Current #testing defconfig:
146 x bsf, 27 x find_next_*bit text data bss dec hex filename 5392637 846592 724424 6963653 6a41c5 vmlinux
After removing the x86_64 specific optimization for find_next_*bit:
94 x bsf, 79 x find_next_*bit text data bss dec hex filename 5392358 846592 724424 6963374 6a40ae vmlinux
After this patch (making the optimization generic):
146 x bsf, 27 x find_next_*bit text data bss dec hex filename 5392396 846592 724424 6963412 6a40d4 vmlinux
---
Quoted 6 lines
ok - but this needs to be solved in a cleaner way. That build-time optimization needs to be pushed into generic code so that 32-bit x86 and other architectures can make use of it as well. The
lib/find_next_bit.cfunctions should be named__find_next_bit()or so.Ingo
I think this is what you had in mind? It seems to work.
Alternative implementation ideas? Comments? In particular: does this break non-x86?
Greetings,
Alexander
include/asm-x86/bitops.h | 4 +- include/asm-x86/bitops_64.h | 10 ------- include/linux/bitops.h | 60 +++++++++++++++++++++++++++++++++++++++++++ lib/find_next_bit.c | 10 +++---- 4 files changed, 66 insertions(+), 18 deletions(-)
include/asm-x86/bitops.h +2 -2
@@ -312,9 +312,9 @@ static int test_bit(int nr, const volatile unsigned long *addr);#undef ADDR -unsigned long find_next_bit (const unsigned long *addr, +unsigned long __find_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset); -unsigned long find_next_zero_bit (const unsigned long *addr, +unsigned long __find_next_zero_bit (const unsigned long *addr,unsigned long size,unsigned long offset);
include/asm-x86/bitops_64.h +0 -10
@@ -20,21 +20,11 @@ static inline long __scanbit(unsigned long val, unsigned long max) (__scanbit(*(unsigned long *)addr,(size))) : \ find_first_bit(addr,size))) -#define find_next_bit (addr,size,off) \ -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \ - ((off) + (__scanbit((*(unsigned long *)addr) >> (off),(size)-(off)))) : \ - find_next_bit(addr,size,off))) -#define find_first_zero_bit (addr,size) \ ((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \ (__scanbit(~*(unsigned long *)addr,(size))) : \ find_first_zero_bit(addr,size))) -#define find_next_zero_bit (addr,size,off) \ -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \ - ((off)+(__scanbit(~(((*(unsigned long *)addr)) >> (off)),(size)-(off)))) : \ - find_next_zero_bit(addr,size,off))) -static inline void set_bit_string (unsigned long *bitmap,unsigned long i,int len) {
include/linux/bitops.h +60 -0
64 lines not on this page · raw message
lib/find_next_bit.c +4 -6
@@ -15,8 +15,6 @@#include <asm/byteorder.h> #define BITOP_WORD (nr) ((nr) / BITS_PER_LONG) -#undef find_next_bit -#undef find_next_zero_bit/** * find_next_bit - find the next set bit in a memory region
@@ -24,8 +22,8 @@* @offset: The bitnumber to start searching at * @size: The maximum size to search */ -unsigned long find_next_bit (const unsigned long *addr,unsigned long size, -unsigned long offset) +unsigned long __find_next_bit (const unsigned long *addr, +unsigned long size,unsigned long offset) {const unsigned long *p = addr +BITOP_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );
@@ -69,8 +67,8 @@ EXPORT_SYMBOL(find_next_bit);* This implementation of find_{first,next}_zero_bit was stolen from * Linus' asm-alpha/bitops.h. */ -unsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size, -unsigned long offset) +unsigned long __find_next_zero_bit (const unsigned long *addr, +unsigned long size,unsigned long offset) {const unsigned long *p = addr +BITOP_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );
Re: [RFC/PATCH] x86: Optimize find_next_(zero_)bit for small constant-size bitmaps
Quoted 1 line · Alexander van Heukelum
x86: Optimize find_next_(zero_)bit for small constant-size bitmaps
thanks, looks nice, except for a small detail:
include/linux/bitops.h static inline unsigned fls_long(unsigned long l) · line 133
Quoted 9 lines
include/linux/bitops.h +8
-0+#ifdef CONFIG_GENERIC_FIND_NEXT_BIT +unsigned long __find_next_bit (const unsigned long *addr, +unsigned long size,unsigned long offset); + +static __always_inline unsigned long +find_next_bit (const unsigned long *addr,unsigned long size, + unsigned long offset) +#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
there should be an #else here i think, which maps find_next_bit to __find_next_bit / etc.
small syntactic nit:
Review
Quoted 2 lines
(quoted diff) +2
-0+unsigned long __find_next_bit(const unsigned long *addr, + unsigned long size, unsigned long offset);
should be explicitly "extern", so that we see that it's a prototype declaration.
Ingo
PATCH 1/1 x86: Optimize find_next_(zero_)bit for small constant-size bitmaps
x86: Optimize find_next_(zero_)bit for small constant-size bitmaps.
This moves an optimization for searching constant-sized small bitmaps form x86_64-specific to generic code.
On an i386 defconfig (the x86#testing one), the size of vmlinux hardly changes with this applied. I have observed only four places where this optimization avoids a call into find_next_bit:
In the functions return_unused_surplus_pages, alloc_fresh_huge_page, and adjust_pool_surplus, this patch avoids a call for a 1-bit bitmap. In __next_cpu a call is avoided for a 32-bit bitmap. That's it.
On x86_64, 52 locations are optimized with a minimal increase in code size:
Current #testing defconfig:
146 x bsf, 27 x find_next_*bit text data bss dec hex filename 5392637 846592 724424 6963653 6a41c5 vmlinux
After removing the x86_64 specific optimization for find_next_*bit:
94 x bsf, 79 x find_next_*bit text data bss dec hex filename 5392358 846592 724424 6963374 6a40ae vmlinux
After this patch (making the optimization generic):
146 x bsf, 27 x find_next_*bit text data bss dec hex filename 5392396 846592 724424 6963412 6a40d4 vmlinux
---
Hi Ingo,
I have now tested (in user-space) the one-long-versions of the find_next_(zero_)bit in the patch. They give the expected results.
Quoted 8 lines
Quoted 7 lines
(quoted diff) +7
-0+#ifdef CONFIG_GENERIC_FIND_NEXT_BIT +unsigned long __find_next_bit(const unsigned long *addr, + unsigned long size, unsigned long offset); + +static __always_inline unsigned long +find_next_bit(const unsigned long *addr, unsigned long size, + unsigned long offset)
Quoted 4 lines
Quoted 1 line
+#endif /*
CONFIG_GENERIC_FIND_NEXT_BIT*/there should be an #else here i think, which maps
find_next_bitto__find_next_bit/ etc.
No, that is intentional: architectures are expected to either set CONFIG_GENERIC_FIND_NEXT_BIT, or provide their own implementation of find_next_bit.
An alternative would be to have all architectures providing __find_next_bit/__find_next_zero_bit and do the optimization unconditionally.
Quoted 5 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+unsigned long __find_next_bit(const unsigned long *addr, + unsigned long size, unsigned long offset);should be explicitly "extern", so that we see that it's a prototype declaration.
ok.
This version runs fine on qemu.
Greetings,
Alexander
include/asm-x86/bitops.h +0 -6
@@ -312,12 +312,6 @@ static int test_bit(int nr, const volatile unsigned long *addr);#undef ADDR -unsigned long find_next_bit (const unsigned long *addr, -unsigned long size,unsigned long offset); -unsigned long find_next_zero_bit (const unsigned long *addr, -unsigned long size,unsigned long offset); - -#ifdef CONFIG_X86_32 # include "bitops_32.h" #else
include/asm-x86/bitops_64.h +0 -10
@@ -20,21 +20,11 @@ static inline long __scanbit(unsigned long val, unsigned long max) (__scanbit(*(unsigned long *)addr,(size))) : \ find_first_bit(addr,size))) -#define find_next_bit (addr,size,off) \ -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \ - ((off) + (__scanbit((*(unsigned long *)addr) >> (off),(size)-(off)))) : \ - find_next_bit(addr,size,off))) -#define find_first_zero_bit (addr,size) \ ((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \ (__scanbit(~*(unsigned long *)addr,(size))) : \ find_first_zero_bit(addr,size))) -#define find_next_zero_bit (addr,size,off) \ -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \ - ((off)+(__scanbit(~(((*(unsigned long *)addr)) >> (off)),(size)-(off)))) : \ - find_next_zero_bit(addr,size,off))) -static inline void set_bit_string (unsigned long *bitmap,unsigned long i,int len) {
include/linux/bitops.h +77 -0
81 lines not on this page · raw message
lib/find_next_bit.c +9 -16
@@ -15,17 +15,12 @@#include <asm/byteorder.h> #define BITOP_WORD (nr) ((nr) / BITS_PER_LONG) -#undef find_next_bit -#undef find_next_zero_bit - -/** -* find_next_bit - find the next set bit in a memory region -* @addr: The address to base the search on -* @offset: The bitnumber to start searching at -* @size: The maximum size to search + +/* +* Find the next set bit in a memory region. */ -unsigned long find_next_bit (const unsigned long *addr,unsigned long size, -unsigned long offset) +unsigned long __find_next_bit (const unsigned long *addr, +unsigned long size,unsigned long offset) {const unsigned long *p = addr +BITOP_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );
@@ -62,15 +57,14 @@ found_first: found_middle:return result +__ffs (tmp); } - -EXPORT_SYMBOL (find_next_bit); +EXPORT_SYMBOL (__find_next_bit);/* * This implementation of find_{first,next}_zero_bit was stolen from * Linus' asm-alpha/bitops.h. */ -unsigned long find_next_zero_bit (const unsigned long *addr,unsigned long size, -unsigned long offset) +unsigned long __find_next_zero_bit (const unsigned long *addr, +unsigned long size,unsigned long offset) {const unsigned long *p = addr +BITOP_WORD (offset);unsigned long result = offset & ~(BITS_PER_LONG -1 );
@@ -107,8 +101,7 @@ found_first: found_middle:return result +ffz (tmp); } - -EXPORT_SYMBOL (find_next_zero_bit); +EXPORT_SYMBOL (__find_next_zero_bit);#ifdef __BIG_ENDIAN
RFC 1/1 non-x86: Optimize find_next_(zero_)bit for small constant-size bitmaps
non-x86: Optimize small bitmap searches for the other archs.
Concerns archs that have their own implementation of find_next_bit and find_next_zero_bit.
For archs that define CONFIG_GENERIC_FIND_NEXT_BIT, a patch is submitted to be included in Ingo's x86-testing tree. It moves an optimization for searching small, constant-sized bitmaps from x86_64-specific to generic code. It works by creating a new __always_inline-marked function in linux/bitops.h, and renaming find_next_(zero_)bit to __find_next_(zero_)bit in the generic code. The new code is currently guarded by CONFIG_GENERIC_FIND_NEXT_BIT, so other archs are expected to work as before.
To enable the optimization globally, all other archs need to implement __find_next_bit and __find_next_zero_bit either by exporting these symbols, or by implementing them as inline functions in their asm/bitops.h.
It would also be nice if every implementation would have the same declaration:
unsigned long __find_next_(zero_)bit(unsigned long *, unsigned long, unsigned long);
I added a totally untested patch for reference.
Did I mis an arch?
Does the assembly still match the (changed) prototype? Can we get concensus on doing the optimization in generic code?
Greetings,
Alexander
arch/arm/lib/findbit.S | 6 ++++-- arch/avr32/kernel/avr32_ksyms.c | 4 ++-- arch/avr32/lib/findbit.S | 4 ++-- include/asm-arm/bitops.h | 20 ++++++++++++-------- include/asm-m68k/bitops.h | 8 ++++---- include/asm-powerpc/bitops.h | 4 ---- include/asm-s390/bitops.h | 12 ++++++------ include/linux/bitops.h | 2 -- 8 files changed, 30 insertions(+), 30 deletions(-)
arch/arm/lib/findbit.S +4 -2
@@ -36,7 +36,8 @@ ENTRY(_find_first_zero_bit_le) /* * Purpose : Find next 'zero' bit - * Prototype: int find_next_zero_bit(void *addr, unsigned int maxbit, int offset) + * Prototype: unsigned long find_next_zero_bit(unsigned long *addr, + * unsigned long maxbit, unsigned long offset); */ ENTRY(_find_next_zero_bit_le) teq r1, #0
@@ -70,7 +71,8 @@ ENTRY(_find_first_bit_le) /* * Purpose : Find next 'one' bit - * Prototype: int find_next_zero_bit(void *addr, unsigned int maxbit, int offset) + * Prototype: unsigned long find_next_zero_bit(unsigned long *addr, + * unsigned long maxbit, unsigned long offset); */ ENTRY(_find_next_bit_le) teq r1, #0
arch/avr32/kernel/avr32_ksyms.c +2 -2
@@ -51,9 +51,9 @@ EXPORT_SYMBOL(__const_udelay);/* Bit operations (lib/findbit.S) */ EXPORT_SYMBOL (find_first_zero_bit); -EXPORT_SYMBOL (find_next_zero_bit); +EXPORT_SYMBOL (__find_next_zero_bit);EXPORT_SYMBOL (find_first_bit); -EXPORT_SYMBOL (find_next_bit); +EXPORT_SYMBOL (__find_next_bit);EXPORT_SYMBOL (generic_find_next_zero_le_bit);/* I/O primitives (lib/io-*.S) */
arch/avr32/lib/findbit.S +2 -2
@@ -29,7 +29,7 @@ ENTRY(find_first_zero_bit) * unsigned long size, * unsigned long offset) */ -ENTRY(find_next_zero_bit) +ENTRY(__find_next_zero_bit) lsr r8, r10, 5 sub r9, r11, r10 retle r11
@@ -93,7 +93,7 @@ ENTRY(find_first_bit) * unsigned long size, * unsigned long offset) */ -ENTRY(find_next_bit) +ENTRY(__find_next_bit) lsr r8, r10, 5 sub r9, r11, r10 retle r11
include/asm-arm/bitops.h +12 -8
@@ -158,9 +158,11 @@ extern int _test_and_set_bit_le(int nr, volatile unsigned long * p);extern int _test_and_clear_bit_le (int nr,volatile unsigned long * p);extern int _test_and_change_bit_le (int nr,volatile unsigned long * p);extern int _find_first_zero_bit_le (const void * p,unsigned size); -extern int _find_next_zero_bit_le (const void * p,int size,int offset); +extern unsigned long _find_next_zero_bit_le (const unsigned long * p, +unsigned long size,unsigned long offset);extern int _find_first_bit_le (const unsigned long *p,unsigned size); -extern int _find_next_bit_le (const unsigned long *p,int size,int offset); +extern unsigned long _find_next_bit_le (const unsigned long *p, +unsigned long size,unsigned long offset);/* * Big endian assembly bitops. nr = 0 -> byte 3 bit 0.
@@ -172,9 +174,11 @@ extern int _test_and_set_bit_be(int nr, volatile unsigned long * p);extern int _test_and_clear_bit_be (int nr,volatile unsigned long * p);extern int _test_and_change_bit_be (int nr,volatile unsigned long * p);extern int _find_first_zero_bit_be (const void * p,unsigned size); -extern int _find_next_zero_bit_be (const void * p,int size,int offset); +extern unsigned long _find_next_zero_bit_be (const unsigned long * p, +unsigned long size,unsigned long offset);extern int _find_first_bit_be (const unsigned long *p,unsigned size); -extern int _find_next_bit_be (const unsigned long *p,int size,int offset); +extern unsigned long _find_next_bit_be (const unsigned long *p, +unsigned long size,unsigned long offset);#ifndef CONFIG_SMP /*
@@ -208,9 +212,9 @@ extern int _find_next_bit_be(const unsigned long *p, int size, int offset);#define test_and_clear_bit (nr,p) ATOMIC_BITOP_LE(test_and_clear_bit,nr,p)#define test_and_change_bit (nr,p) ATOMIC_BITOP_LE(test_and_change_bit,nr,p)#define find_first_zero_bit (p,sz) _find_first_zero_bit_le(p,sz) -#define find_next_zero_bit (p,sz,off) _find_next_zero_bit_le(p,sz,off) +#define __find_next_zero_bit (p,sz,off) _find_next_zero_bit_le(p,sz,off)#define find_first_bit (p,sz) _find_first_bit_le(p,sz) -#define find_next_bit (p,sz,off) _find_next_bit_le(p,sz,off) +#define __find_next_bit (p,sz,off) _find_next_bit_le(p,sz,off)#define WORD_BITOFF_TO_LE (x) ((x))
@@ -226,9 +230,9 @@ extern int _find_next_bit_be(const unsigned long *p, int size, int offset);#define test_and_clear_bit (nr,p) ATOMIC_BITOP_BE(test_and_clear_bit,nr,p)#define test_and_change_bit (nr,p) ATOMIC_BITOP_BE(test_and_change_bit,nr,p)#define find_first_zero_bit (p,sz) _find_first_zero_bit_be(p,sz) -#define find_next_zero_bit (p,sz,off) _find_next_zero_bit_be(p,sz,off) +#define __find_next_zero_bit (p,sz,off) _find_next_zero_bit_be(p,sz,off)#define find_first_bit (p,sz) _find_first_bit_be(p,sz) -#define find_next_bit (p,sz,off) _find_next_bit_be(p,sz,off) +#define __find_next_bit (p,sz,off) _find_next_bit_be(p,sz,off)#define WORD_BITOFF_TO_LE (x) ((x) ^ 0x18)
include/asm-m68k/bitops.h +4 -4
@@ -199,8 +199,8 @@ out:return ((long )p - (long )vaddr -4 ) *8 + res; } -static inline int find_next_zero_bit (const unsigned long *vaddr,int size, -int offset) +static inline unsigned long __find_next_zero_bit (const unsigned long *vaddr, +unsigned long size,unsigned long offset) {const unsigned long *p = vaddr + (offset >>5 );int bit = offset &31UL , res;
@@ -246,8 +246,8 @@ out:return ((long )p - (long )vaddr -4 ) *8 + res; } -static inline int find_next_bit (const unsigned long *vaddr,int size, -int offset) +static inline unsigned long __find_next_bit (const unsigned long *vaddr, +unsigned long size,unsigned long offset) {const unsigned long *p = vaddr + (offset >>5 );int bit = offset &31UL , res;
include/asm-powerpc/bitops.h +0 -4
@@ -317,8 +317,6 @@ static __inline__ int fls(unsigned int x)#include <asm-generic/bitops/hweight.h> #define find_first_zero_bit (addr, size) find_next_zero_bit((addr), (size), 0) -unsigned long find_next_zero_bit (const unsigned long *addr, -unsigned long size,unsigned long offset);/** * find_first_bit - find the first set bit in a memory region * @addr: The address to start the search at
@@ -328,8 +326,6 @@ unsigned long find_next_zero_bit(const unsigned long *addr,* containing a bit. */ #define find_first_bit (addr, size) find_next_bit((addr), (size), 0) -unsigned long find_next_bit (const unsigned long *addr, -unsigned long size,unsigned long offset);/* Little-endian versions */
include/asm-s390/bitops.h +6 -6
@@ -691,9 +691,9 @@ static inline unsigned long find_first_bit(const unsigned long * addr,* @offset: The bitnumber to start searching at * @size: The maximum size to search */ -static inline int find_next_zero_bit (const unsigned long * addr, -unsigned long size, -unsigned long offset) +static inline unsigned long __find_next_zero_bit (const unsigned long * addr, +unsigned long size, +unsigned long offset) {const unsigned long *p;unsigned long bit, set;
@@ -727,9 +727,9 @@ static inline int find_next_zero_bit (const unsigned long * addr,* @offset: The bitnumber to start searching at * @size: The maximum size to search */ -static inline int find_next_bit (const unsigned long * addr, -unsigned long size, -unsigned long offset) +static inline unsigned long __find_next_bit (const unsigned long * addr, +unsigned long size, +unsigned long offset) {const unsigned long *p;unsigned long bit, set;
include/linux/bitops.h +0 -2
@@ -73,7 +73,6 @@ static inline unsigned fls_long(unsigned long l) }#ifdef __KERNEL__ -#ifdef CONFIG_GENERIC_FIND_NEXT_BIT extern unsigned long __find_next_bit (const unsigned long *addr,unsigned long size,unsigned long offset);
@@ -147,6 +146,5 @@ find_next_zero_bit(const unsigned long *addr, unsigned long size,/* size is not constant or too big */ return __find_next_zero_bit (addr, size, offset); } -#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */ #endif /* __KERNEL__ */ #endif
Re: [PATCH] x86: Optimize find_next_(zero_)bit for small constant-size bitmaps
In reply to Alexander van HeukelumQuoted 8 lines · Alexander van Heukelum
Quoted 4 lines
Quoted 1 line
+#endif /*
CONFIG_GENERIC_FIND_NEXT_BIT*/there should be an #else here i think, which maps
find_next_bitto__find_next_bit/ etc.No, that is intentional: architectures are expected to either set
CONFIG_GENERIC_FIND_NEXT_BIT, or provide their own implementation offind_next_bit.
indeed, you are right.
Quoted 1 line
This version runs fine on qemu.
great - i've queued it up into x86.git.
Ingo
Quoted 5 lines · Alexander van Heukelum
If the bitmap size is not a multiple of
BITS_PER_LONG, and no set (cleared) bit is found,find_next_bit(find_next_zero_bit) returns a value outside of the range [0,size]. The generic version always returns exactly size.
With that change it is likely possible to remove the min(NR_CPUS in lib/cpumask.c __first/__next_cpu. iirc it was just a workaround for the x86 quirk. I suspect with such a change it would be possible to inline those again, possibly speeding up some loops who do cpumask walking (iirc the scheduler used to do that frequently)
-Andi
Quoted 6 lines · Alexander van Heukelum
Benchmark using: gcc -fomit-frame-pointer -Os. For each bitmap size 1...512, for each possible bitmap with one bit set, for each possible
offset: find the position of the first bit starting at offset. If you follow ;). Times include setup of the bitmap and checking of the results.
BTW another comment: it would be far more sense if you did some profiling on what bitmap sizes a real kernel uses (should be easy enough with some systemtap) and benchmarked only that.
I doubt 1 bit bitmap searches are common for example ...
-Andi
Quoted 17 lines · Alexander van Heukelum
x86: Change x86 to use the generic
find_next_bitimplementationThe versions with inline assembly are in fact slower on the machines I tested them on (in userspace) (Athlon XP 2800+, p4-like Xeon 2.8GHz, AMD Opteron 270). The i386-version needed a fix similar to
06024f21to avoid crashing the benchmark.Benchmark using: gcc -fomit-frame-pointer -Os. For each bitmap size 1...512, for each possible bitmap with one bit set, for each possible
offset: find the position of the first bit starting at offset. If you follow ;). Times include setup of the bitmap and checking of the results.Athlon Xeon Opteron 32/64bitx86-specific: 0m3.692s 0m2.820s 0m3.196s / 0m2.480s
generic: 0m2.622s 0m1.662s 0m2.100s / 0m1.572s
Quoted 7 lines
If the bitmap size is not a multiple of
BITS_PER_LONG, and no set (cleared) bit is found,find_next_bit(find_next_zero_bit) returns a value outside of the range [0,size]. The generic version always returns exactly size. The generic version also uses unsigned long everywhere, while the x86 versions use a mishmash of int, unsigned (int), long and unsigned long.
This problem is observed on x86_64 and powerpc also. We need a long aligned address for test_bit, set_bit find_bit etc. In ext4 we have to make sure we align the address passed to
ext4_test_bitext4_set_bitext4_find_next_zero_bitext4_find_next_bit
fs/ext4/mballoc.c have some examples.
-aneesh
Quoted 18 lines · Aneesh Kumar K.V
Quoted 17 lines · Alexander van Heukelum
x86: Change x86 to use the generic
find_next_bitimplementationThe versions with inline assembly are in fact slower on the machines I tested them on (in userspace) (Athlon XP 2800+, p4-like Xeon 2.8GHz, AMD Opteron 270). The i386-version needed a fix similar to
06024f21to avoid crashing the benchmark.Benchmark using: gcc -fomit-frame-pointer -Os. For each bitmap size 1...512, for each possible bitmap with one bit set, for each possible
offset: find the position of the first bit starting at offset. If you follow ;). Times include setup of the bitmap and checking of the results.Athlon Xeon Opteron 32/64bitx86-specific: 0m3.692s 0m2.820s 0m3.196s / 0m2.480s
generic: 0m2.622s 0m1.662s 0m2.100s / 0m1.572s
Quoted 8 lines
Quoted 6 lines
If the bitmap size is not a multiple of
BITS_PER_LONG, and no set (cleared) bit is found,find_next_bit(find_next_zero_bit) returns a value outside of the range [0,size]. The generic version always returns exactly size. The generic version also uses unsigned long everywhere, while the x86 versions use a mishmash of int, unsigned (int), long and unsigned long.This problem is observed on
x86_64and powerpc also.
I'm not entirely sure if it is a problem. In some cases it certainly is an inconvenience, though ;). I mentioned the difference between the old and generic versions, because of the possibility of dependence of this behaviour.
Indeed I see for example (in fs/ext4/mballoc.c).
bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
if (bit >= end)
break;
next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
if (next > end)
next = end;
free += next - bit;So here it needed to adjust the value.
Quoted 10 lines
We need a long
aligned address fortest_bit,set_bitfind_bitetc. In ext4 we have to make sure we align the address passed to
ext4_test_bitext4_set_bitext4_find_next_zero_bitext4_find_next_bit
fs/ext4/mballoc.chave some examples.
This is a different 'problem'. find_next_bit works on arrays of long, while the bitmaps in ext4_find_next_bit are of type void * and seem not to have any alignment restrictions. ext4 implements wrappers around find_next_bit to solve that 'problem'.
The question that arises is: do we want find_first_bit, find_next_bit. etc. to always return a value in the range [0, size], or do we want to allow implementations that return [0, size-1] if there is a bit found and something else (roundup(size,bitsperlong) or ulongmax, for example if, none were found?
The current x86_64 versions of find_first_bit and find_next_bit return roundup(size,bitsperlong) if no bits were found, but on the other hand I guess most bitmaps are a multiple of bitsperlong bits in size, which hides the difference.
Greetings,
Alexander
Quoted 1 line
-aneesh
Signature · 6 lines
Alexander van Heukelum [email protected] -- http://www.fastmail.fm - Or how I learned to stop worrying and love email again