Lookup table

Sometimes in Go 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 Go 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.

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.