Lookup, u8

Consider a Rust program that must get a byte (u8) value for an index. It must do this repeatedly, and a lookup table can be precomputed.

With lookup tables, we can reduce branching in program execution. This can speed up programs. A lookup table can be used in Rust programs for optimization.

This program introduces the get_lookup_value function, which returns a u8 value for its argument. A lookup table can return the same exact values as this function.

use std::time::*;

fn get_lookup_value(x: u8) -> u8 {
    return match x {
        b'#' | b'P' => 130,
        b'i' => 70,
        b'p' => 10,
        _ => 0
    };
}

fn main() {
    // Initialize lookup table.
    let mut table = [0u8; 256];
    for i in 0..table.len() {
        table[i] = get_lookup_value(i as u8) as u8;
    }
    let bytes = String::from("abc#Pip123###").bytes().collect::<Vec<u8>>();

    // Version 1: use match.
    let now1 = Instant::now();
    let mut result1: u64 = 0;
    for _ in 0..10000000 {
        for c in &bytes {
  result1 += get_lookup_value(*c as u8) as u64;
        }
    }
    println!("RESULT: {}", result1);
    println!("  TIME: {} ms", now1.elapsed().as_millis());

    // Version 2: use lookup table.
    let now2 = Instant::now();
    let mut result2: u64 = 0;
    for _ in 0..10000000 {
        for c in &bytes {
  result2 += table[*c as usize] as u64;
        }
    }
    println!("RESULT: {}", result2);
    println!("  TIME: {} ms", now2.elapsed().as_millis());
}
RESULT: 7300000000
  TIME: 42 ms
RESULT: 7300000000
  TIME: 3 ms

Notes, lookup tables

We can store function pointers in an array or vector, and then call functions in a lookup table. This allows more complex behavior to be encoded.

A lookup table can be computed and used in Rust programs. But a match statement, or even an if-else chain, may provide better performance—benchmarks are always needed.