Lookup Table (byte Array)
This page was last reviewed on Apr 27, 2023.
Dot Net Perls
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.
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. In addition to speeding up programs, this can simplify some kinds of code.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Apr 27, 2023 (edit).
© 2007-2024 Sam Allen.