lkml.org 
[lkml]   [2009]   [Nov]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH] Optimize hweight32 for x86
Date
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);
}

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
---
lib/hweight.c | 7 +++++++
1 files changed, 7 insertions(+), 0 deletions(-)

diff --git a/lib/hweight.c b/lib/hweight.c
index 389424e..63ee4eb 100644
--- a/lib/hweight.c
+++ b/lib/hweight.c
@@ -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);

--
1.6.5.1


\
 
 \ /
  Last update: 2009-11-19 05:15    [W:0.366 / U:0.008 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site