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.

Start We generate the lookup table by allocating a 256-byte array, and setting each element to the result of get_lookup_value.

Info We use the Instant now() function for benchmarking. We compare the time of a match statement against a lookup table.

Version 1 This version of the code uses the get_lookup_value() function. It adds up all the returned values.

Version 2 Here we use the generated lookup table. It also adds up the values fetched from the lookup table.

Result The lookup table was faster, but this advantage probably would not be as big in a real program due to memory cache contention.

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.

Also It sometimes helps performance if we are looking up byte values to have a 256-byte lookup table, as the compiler can remove bounds checks.

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.

Lookup, u8

Notes, lookup tables

Lookup, `u8`