assembly-hashmap 0.1.0

A single-threaded u64→u64 hashmap with x86-64 assembly operations and Rust-side growth.
Documentation
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 {
            // Include deterministic misses above the insertion key space.
            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}");
    }

    // An exhaustive final comparison catches mutations that a later operation
    // in the stream did not happen to read.
    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");

    // Recreate and identically seed each mutable map outside the timed region.
    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()
    );
}