Hello!
I am trying to write a fast lookup table for 7-cards poker hand evaluation.
The principle is very simple: given a hand, represented as a u64, compute a lookup index (perfect hash function), and fetch the pre-computed hand value stored in a Vec. There are about 133M possible hand combinations.
My problem is that reading values from the Vec is much slower than writing them. I'd like to know wether that's to be expected, and/or if there's anything I can do to speed it up, given that it's actually the performance-critical part of the code.
Here are the timings I get:
- Computing all 133M indices: 180M hands / sec
- Computing all 133M indices + writing lookup table values: 150M hands / sec
- Computing all 133M indices + reading lookup table values: 34M hands / sec
and here is the relevant part of the code
show code
struct LookupTable {
lookup: Vec<u32>,
hash: PerfectHash,
}
impl LookupTable {
fn new() -> Self {
let hash = PerfectHash::new();
let lookup = vec![0; LOOKUP_SIZE];
Self { lookup, hash }
}
// iterate over all possible hands and compute their index (perfect hashing)
fn compute_all_indices(&mut self) -> usize {
let mut k = 0;
for hand in generate_hands() {
k += self.hash.index(hand);
}
k
}
// fill the lookup table with arbitrary value
fn write_values(&mut self) {
for hand in generate_hands() {
let index = self.hash.index(hand);
self.lookup[index] = 1;
}
}
// lookup values for all possible hands
fn read_values(&self) -> u32 {
let mut z = 0;
for hand in generate_hands() {
let index = self.hash.index(hand);
z += self.lookup[index];
}
z
}
}
fn main() {
let mut table = LookupTable::new();
let start = Instant::now();
let result = table.compute_all_indices();
let duration = start.elapsed().as_micros() as usize;
println!(
"Perfect hash computing: {:?} M/s ({})",
LOOKUP_SIZE / duration,
result
);
let start = Instant::now();
table.write_values();
let duration = start.elapsed().as_micros() as usize;
println!("Filling lookup table: {:?} M/s", LOOKUP_SIZE / duration);
let start = Instant::now();
let value = table.read_values();
let duration = start.elapsed().as_micros() as usize;
println!(
"Fetching lookup table: {:?} M/s ({})",
LOOKUP_SIZE / duration,
value
);
}
Thanks