Skip to contentSkip to conversation

Optimize hweight32 for x86

PATCH In review Akinobu Mita 1 participant 2 messages Nov 19, 2009 – Dec 28, 2009

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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
index 389424e..63ee4eb 100644
@@ -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
#1 lore raw

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

[ only x86 sets ARCH_HAS_FAST_MULTIPLIER so we do this via the x86 tree]
---
 lib/hweight.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)
lib/hweight.c +7 -0
index 389424e..63ee4eb 100644
@@ -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);