math/bits: faster OnesCount using table lookups for sizes 8,16,32

For uint64, the existing algorithm is faster.

benchmark                  old ns/op     new ns/op     delta
BenchmarkOnesCount8-8      1.95          0.97          -50.26%
BenchmarkOnesCount16-8     2.54          1.39          -45.28%
BenchmarkOnesCount32-8     2.61          1.96          -24.90%

Measured on 2.3 GHz Intel Core i7 running macOS 10.12.3.

Change-Id: I6cc42882fef3d24694720464039161e339a9ae99
Reviewed-on: https://go-review.googlesource.com/37580
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

1 files changed, 3 insertions, 18 deletions

diff --git a/src/math/bits/bits.go b/src/math/bits/bits.go
index 03bcb1c354..24aa7c5f3f 100644
--- a/src/math/bits/bits.go
+++ b/src/math/bits/bits.go
@@ -63,32 +63,17 @@ func OnesCount(x uint) int {
 
 // OnesCount8 returns the number of one bits ("population count") in x.
 func OnesCount8(x uint8) int {
-	const m = 1<<8 - 1
-	x = x>>1&(m0&m) + x&(m0&m)
-	x = x>>2&(m1&m) + x&(m1&m)
-	x += x >> 4
-	return int(x) & (1<<4 - 1)
+	return int(pop8tab[x])
 }
 
 // OnesCount16 returns the number of one bits ("population count") in x.
 func OnesCount16(x uint16) int {
-	const m = 1<<16 - 1
-	x = x>>1&(m0&m) + x&(m0&m)
-	x = x>>2&(m1&m) + x&(m1&m)
-	x = (x>>4 + x) & (m2 & m)
-	x += x >> 8
-	return int(x) & (1<<5 - 1)
+	return int(pop8tab[x>>8] + pop8tab[x&0xff])
 }
 
 // OnesCount32 returns the number of one bits ("population count") in x.
 func OnesCount32(x uint32) int {
-	const m = 1<<32 - 1
-	x = x>>1&(m0&m) + x&(m0&m)
-	x = x>>2&(m1&m) + x&(m1&m)
-	x = (x>>4 + x) & (m2 & m)
-	x += x >> 8
-	x += x >> 16
-	return int(x) & (1<<6 - 1)
+	return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
 }
 
 // OnesCount64 returns the number of one bits ("population count") in x.