From a06dc6db2bfb926bfb8153618e721eafe229fb40 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sat, 16 Nov 2019 11:37:11 +0100 Subject: fast log2 --- internal/hash/log2.go | 18 ++++++++++++------ internal/hash/log2_test.go | 19 +++++++++++++++---- 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) } }) } -- cgit v1.2.3