Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Impetus for switching from generation of [256]uint8 to [256]int for math/bits Len*
package main
import "testing"
var len8tab = [256]uint8{
0x00, 0x01, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
}
var len8tabInt = [256]int{
0x00, 0x01, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
}
var queries = []uint64{
0, 1, 1 << 10, 1 << 20, 1 << 30, 17, 1 << 40, 1 << 50, 1 << 60, 1<<64 - 1,
}
func BenchmarkPlainLookup(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, q := range queries {
if v := len64Int(q); v <= 0 {
}
}
}
b.ReportAllocs()
}
func BenchmarkIntCastLookup(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, q := range queries {
if v := len64Cast(q); v <= 0 {
}
}
}
b.ReportAllocs()
}
func len64Cast(x uint64) (n int) {
if x >= 1<<32 {
x >>= 32
n = 32
}
if x >= 1<<16 {
x >>= 16
n += 16
}
if x >= 1<<8 {
x >>= 8
n += 8
}
return n + int(len8tab[x])
}
func len64Int(x uint64) (n int) {
if x >= 1<<32 {
x >>= 32
n = 32
}
if x >= 1<<16 {
x >>= 16
n += 16
}
if x >= 1<<8 {
x >>= 8
n += 8
}
return n + len8tabInt[x]
}
BenchmarkLookup-4 100000000 22.4 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.1 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.4 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.4 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.1 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.3 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.9 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 20.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.2 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.6 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.4 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 20.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 20.4 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 20.5 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.1 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 50000000 22.0 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.4 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 24.3 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.6 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 23.5 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.7 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 23.1 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.3 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 24.3 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 23.2 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 23.6 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 23.0 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 50000000 24.3 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 50000000 24.7 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.5 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.7 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.8 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 22.0 ns/op 0 B/op 0 allocs/op
BenchmarkLookup-4 100000000 21.5 ns/op 0 B/op 0 allocs/op
$ benchstat old.txt new.txt 
name      old time/op    new time/op    delta
Lookup-4    22.9ns ± 8%    21.7ns ± 6%  -5.30%        (p=0.000 n=20+20)

name      old alloc/op   new alloc/op   delta
Lookup-4    0.00B ±NaN%    0.00B ±NaN%    ~     (all samples are equal)

name      old allocs/op  new allocs/op  delta
Lookup-4     0.00 ±NaN%     0.00 ±NaN%    ~     (all samples are equal)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment