Golang Lookup Table (byte Array)Use a byte array to implement a fast lookup table, and test performance.
Lookup table. Sometimes in Golang programs we have methods that switch on a value, and return another value. We can replace these with lookup tables.
For performance, lookup tables can sometimes help. This can be benchmarked. At the instruction level, branching is reduced with a lookup table.
Example. This program has a func that changes some byte values into other byte values. We can either use a switch to do this, or a generated lookup table.
Version 1 This version of the code calls into a func that uses switch on each iteration.
Version 2 Here we use the result from a generated lookup table instead of a switch. Only an array lookup is needed on each iteration.
Result The lookup table improves performance over the switch in a significant way.
Golang program that uses byte lookup table
package main import ( "fmt" "time" ) var ( lut [128]byte ) func GetLookupValue(x byte) int { switch x { case '#', 'P': return 130 case 'i': return 70 case 'p': return 10 } return 0 } func main() { // Initialize lookup table. for z := 0; z < 128; z += 1 { lut[z] = byte(GetLookupValue(byte(z))) } data := []byte("abc#Pip123###") t0 := time.Now() // Version 1: use switch to get value. result := 0 for i := 0; i < 10000000; i++ { for _, x := range data { result += GetLookupValue(x) } } t1 := time.Now() // Version 2: use lookup table. result2 := 0 for i := 0; i < 10000000; i++ { for _, x := range data { result2 += int(lut[x]) } } t2 := time.Now() // Benchmark results. fmt.Println(result, result2) fmt.Println(t1.Sub(t0)) fmt.Println(t2.Sub(t1)) }
7300000000 7300000000 220.894417ms (Switch) 64.784ms (Lookup)
Table notes. For a Golang func that runs a switch (or other branching construct) in a tight loop, a lookup table can help. This may add some complexity.
But In benchmarks, the lookup table use seems to be a clear improvement over a branching construct.
Warning It is sometimes better not to copy the table into a local variable. Try just accessing the table directly.
Summary. With a lookup table in Go, we can optimize performance over a switch statement. This can simplify some kinds of code.
© 2007-2021 sam allen.
see site info on the changelog.