Optimize hweight32 for x86
Subsystems (2)
PATCH 1/1 Optimize hweight32 for x86
Optimize hweight32 by using the same technique in hweight64. The proof of this technique can be found in the commit log for f9b4192923fa6e38331e88214b1fe5fc21583fcc
The userspece benchmark on x86_32 showed 20% speedup with bitmap_weight() which uses hweight32 to count bits for each unsigned long on 32bit architectures.
int main(void)
{
#define SZ (1024 * 1024 * 512)
static DECLARE_BITMAP(bitmap, SZ) = {
[0 ... 100] = 1,
};
return bitmap_weight(bitmap, SZ);
}--- lib/hweight.c | 7 +++++++ 1 files changed, 7 insertions(+), 0 deletions(-)
lib/hweight.c +7 -0
@@ -11,11 +11,18 @@unsigned int hweight32 (unsigned int w) { +#ifdef ARCH_HAS_FAST_MULTIPLIER + w -= (w >>1 ) &0x55555555 ; + w = (w &0x33333333 ) + ((w >>2 ) &0x33333333 ); + w = (w + (w >>4 )) &0x0f0f0f0f ; +return (w *0x01010101 ) >>24 ; +#else unsigned int res = w - ((w >>1 ) &0x55555555 ); res = (res &0x33333333 ) + ((res >>2 ) &0x33333333 ); res = (res + (res >>4 )) &0x0F0F0F0F ; res = res + (res >>8 );return (res + (res >>16 )) &0x000000FF ; +#endif }EXPORT_SYMBOL (hweight32);
Signature · 1 line
1.6.5.1
[tip:x86/asm] x86, core: Optimize hweight32()
Commit-ID: 39d997b514e12d5aff0dca206eb8996b3957927e Gitweb: http://git.kernel.org/tip/39d997b514e12d5aff0dca206eb8996b3957927e Author: Akinobu Mita <[email protected]> AuthorDate: Mon, 21 Dec 2009 16:20:16 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 28 Dec 2009 10:41:39 +0100
x86, core: Optimize hweight32()
Optimize hweight32 by using the same technique in hweight64.
The proof of this technique can be found in the commit log for f9b4192923fa6e38331e88214b1fe5fc21583fcc ("bitops: hweight() speedup").
The userspace benchmark on x86_32 showed 20% speedup with bitmap_weight() which uses hweight32 to count bits for each unsigned long on 32bit architectures.
int main(void)
{
#define SZ (1024 * 1024 * 512)
static DECLARE_BITMAP(bitmap, SZ) = {
[0 ... 100] = 1,
};
return bitmap_weight(bitmap, SZ);}
LKML-Reference: <[email protected]>
--- lib/hweight.c | 7 +++++++ 1 files changed, 7 insertions(+), 0 deletions(-)
lib/hweight.c +7 -0
@@ -11,11 +11,18 @@unsigned int hweight32 (unsigned int w) { +#ifdef ARCH_HAS_FAST_MULTIPLIER + w -= (w >>1 ) &0x55555555 ; + w = (w &0x33333333 ) + ((w >>2 ) &0x33333333 ); + w = (w + (w >>4 )) &0x0f0f0f0f ; +return (w *0x01010101 ) >>24 ; +#else unsigned int res = w - ((w >>1 ) &0x55555555 ); res = (res &0x33333333 ) + ((res >>2 ) &0x33333333 ); res = (res + (res >>4 )) &0x0F0F0F0F ; res = res + (res >>8 );return (res + (res >>16 )) &0x000000FF ; +#endif }EXPORT_SYMBOL (hweight32);