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.
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.
Dot Net Perls is a collection of pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.