Lookup Table, u8 Example
This page was last reviewed on Apr 5, 2023.
Dot Net Perls
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.
const fn
Example program. 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.
Detail We generate the lookup table by allocating a 128-byte array, and setting each element to the result of get_lookup_value.
Detail 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 match statement in Rust was faster, but the lookup table had good performance as well.
use std::time::{Duration, Instant}; 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: [u8; 128] = [0; 128]; for i in 0..128 { table[i] = get_lookup_value(i as u8) as u8; } // Version 1: use match. let now1 = Instant::now(); let mut result1: u64 = 0; for _ in 0..10000000 { for c in "abc#Pip123###".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 "abc#Pip123###".bytes() { result2 += table[c as usize] as u64; } } println!("RESULT: {}", result2); println!(" TIME: {} ms", now2.elapsed().as_millis()); }
RESULT: 7300000000 TIME: 1 ms RESULT: 7300000000 TIME: 42 ms
Function lookup. 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 summary. A lookup table can be computed and used in Rust programs. But a match statement, or even a similar if-else chain, may provide better performance.
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 5, 2023 (simplify).
© 2007-2024 Sam Allen.