use assembly_hashmap::{AssemblyHashMap, USING_ASSEMBLY};
use std::collections::HashMap;
use std::hint::black_box;
use std::time::{Duration, Instant};
const GOLDEN: u64 = 0x9e37_79b9_7f4a_7c15;
#[derive(Clone, Copy)]
enum Operation {
Put(u64, u64),
Get(u64),
}
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
let mut value = self.0;
value ^= value << 13;
value ^= value >> 7;
value ^= value << 17;
self.0 = value;
value
}
}
fn key(index: u64) -> u64 {
index.wrapping_mul(GOLDEN)
}
fn workload(count: usize, key_space: usize) -> Vec<Operation> {
let mut rng = Rng(0x6a09_e667_f3bc_c909);
let mut operations = Vec::with_capacity(count);
for _ in 0..count {
let index = rng.next() % key_space as u64;
if rng.next() & 3 == 0 {
operations.push(Operation::Put(key(index), rng.next()));
} else {
let lookup = if rng.next() & 7 == 0 {
index + key_space as u64
} else {
index
};
operations.push(Operation::Get(key(lookup)));
}
}
operations
}
fn fold_option(checksum: &mut u64, value: Option<u64>) {
*checksum = checksum.rotate_left(9)
^ match value {
Some(value) => value.wrapping_mul(GOLDEN) ^ 1,
None => 0xd1b5_4a32_d192_ed03,
};
}
fn seed_assembly(key_space: usize) -> AssemblyHashMap {
let mut assembly = AssemblyHashMap::with_capacity(key_space).unwrap();
for index in 0..key_space / 2 {
let key = key(index as u64);
let value = (index as u64).rotate_left(23);
assert_eq!(assembly.put(key, value), None);
}
assembly
}
fn seed_standard(key_space: usize) -> HashMap<u64, u64> {
let mut standard = HashMap::with_capacity(key_space);
for index in 0..key_space / 2 {
standard.insert(key(index as u64), (index as u64).rotate_left(23));
}
standard
}
fn verify_exact_stream(operations: &[Operation], key_space: usize) {
let mut assembly = seed_assembly(key_space);
let mut standard = seed_standard(key_space);
for (index, operation) in operations.iter().copied().enumerate() {
match operation {
Operation::Put(key, value) => {
let actual = assembly.put(key, value);
let expected = standard.insert(key, value);
assert_eq!(actual, expected, "put mismatch at operation {index}");
}
Operation::Get(key) => {
assert_eq!(
assembly.get(key),
standard.get(&key).copied(),
"get mismatch at operation {index}"
);
}
}
assert_eq!(assembly.len(), standard.len(), "length mismatch at {index}");
}
for index in 0..key_space as u64 * 2 {
let key = key(index);
assert_eq!(assembly.get(key), standard.get(&key).copied());
}
}
fn replay_assembly(map: &mut AssemblyHashMap, operations: &[Operation]) -> u64 {
let mut checksum = 0;
for operation in operations.iter().copied() {
match operation {
Operation::Put(key, value) => fold_option(&mut checksum, map.put(key, value)),
Operation::Get(key) => fold_option(&mut checksum, map.get(key)),
}
}
black_box(checksum)
}
fn replay_standard(map: &mut HashMap<u64, u64>, operations: &[Operation]) -> u64 {
let mut checksum = 0;
for operation in operations.iter().copied() {
match operation {
Operation::Put(key, value) => fold_option(&mut checksum, map.insert(key, value)),
Operation::Get(key) => fold_option(&mut checksum, map.get(&key).copied()),
}
}
black_box(checksum)
}
fn best_of<M>(
rounds: usize,
mut setup: impl FnMut() -> M,
mut run: impl FnMut(&mut M) -> u64,
) -> (Duration, u64) {
let mut best = Duration::MAX;
let mut expected_checksum = None;
for _ in 0..rounds {
let mut map = setup();
let start = Instant::now();
let checksum = run(&mut map);
best = best.min(start.elapsed());
assert!(
expected_checksum.is_none_or(|expected| expected == checksum),
"benchmark replay was not deterministic"
);
expected_checksum = Some(checksum);
}
(best, expected_checksum.unwrap())
}
fn report(name: &str, duration: Duration, operations: usize) {
let ns_per_op = duration.as_secs_f64() * 1e9 / operations as f64;
let million_ops = operations as f64 / duration.as_secs_f64() / 1e6;
println!("{name:>18}: {ns_per_op:8.2} ns/op {million_ops:8.2} Mops/s");
}
fn env_usize(name: &str, default: usize) -> usize {
std::env::var(name)
.ok()
.and_then(|value| value.parse().ok())
.unwrap_or(default)
}
fn main() {
let key_space = env_usize("HM_BENCH_KEYS", 1 << 18);
let operation_count = env_usize("HM_BENCH_OPS", 1 << 21);
let rounds = env_usize("HM_BENCH_ROUNDS", 5);
assert!(key_space >= 2);
assert!(operation_count > 0);
assert!(rounds > 0);
println!(
"backend: {}",
if USING_ASSEMBLY {
"x86-64 hashmap.S"
} else {
"C reference (this is not an assembly benchmark)"
}
);
println!(
"workload: {operation_count} identical operations, {key_space} possible inserted keys"
);
let operations = workload(operation_count, key_space);
verify_exact_stream(&operations, key_space);
println!("functional comparison: passed");
let (assembly_time, assembly_checksum) = best_of(
rounds,
|| seed_assembly(key_space),
|assembly| replay_assembly(assembly, &operations),
);
let (standard_time, standard_checksum) = best_of(
rounds,
|| seed_standard(key_space),
|standard| replay_standard(standard, &operations),
);
assert_eq!(
assembly_checksum, standard_checksum,
"benchmarked implementations produced different results"
);
report("assembly hashmap", assembly_time, operation_count);
report("std HashMap", standard_time, operation_count);
println!(
"{:.2}x assembly/std throughput",
standard_time.as_secs_f64() / assembly_time.as_secs_f64()
);
}