aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2019-11-16 11:37:11 +0100
committerDimitri Sokolyuk <demon@dim13.org>2019-11-16 11:37:11 +0100
commita06dc6db2bfb926bfb8153618e721eafe229fb40 (patch)
treea322d43de867a54dab19444132d29e6e237ae385
parenteda30b4e3010258751c2caf559f72f19b0c3784c (diff)
fast log2
-rw-r--r--internal/hash/log2.go18
-rw-r--r--internal/hash/log2_test.go19
2 files changed, 27 insertions, 10 deletions
diff --git a/internal/hash/log2.go b/internal/hash/log2.go
index 5e30f17..8ba79df 100644
--- a/internal/hash/log2.go
+++ b/internal/hash/log2.go
@@ -1,9 +1,15 @@
package hash
-func log2(num uint32) uint32 {
- var i uint32
- for limit := uint32(1); limit < num; limit <<= 1 {
- i++
- }
- return i
+var tab32 = [32]uint32{
+ 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+ 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31,
+}
+
+func log2(value uint32) uint32 {
+ value |= value >> 1
+ value |= value >> 2
+ value |= value >> 4
+ value |= value >> 8
+ value |= value >> 16
+ return tab32[(value*0x07c4acdd)>>27]
}
diff --git a/internal/hash/log2_test.go b/internal/hash/log2_test.go
index c58e213..d5ff95b 100644
--- a/internal/hash/log2_test.go
+++ b/internal/hash/log2_test.go
@@ -12,12 +12,23 @@ func TestLog2(t *testing.T) {
{0, 0},
{1, 0},
{2, 1},
- {3, 2},
+ {3, 1},
{4, 2},
+ {7, 2},
{8, 3},
- {9, 4},
+ {15, 3},
+ {16, 4},
+ {31, 4},
+ {32, 5},
+ {63, 5},
+ {64, 6},
+ {127, 6},
{128, 7},
- {129, 8},
+ {255, 7},
+ {256, 8},
+ {511, 8},
+ {512, 9},
+ {1023, 9},
{1024, 10},
}
for _, tc := range testCases {
@@ -35,7 +46,7 @@ func BenchmarkLog2(b *testing.B) {
for _, bc := range benchCases {
b.Run(fmt.Sprintf("log(%v)", bc), func(b *testing.B) {
for i := 0; i < b.N; i++ {
- log2(1024)
+ log2(bc)
}
})
}