ptr_hash 2.0.1

A high-throughput minimal perfect hash function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

use epserde::prelude::*;
use ptr_hash::{PtrHash, PtrHashParams};

/// XXH3 version since the default FxHash does not implement the epserde traits.
type PtrHashXxh3 =
    PtrHash<u64, ptr_hash::bucket_fn::Linear, Vec<u32>, ptr_hash::hash::Xxh3Int, Vec<u8>>;

fn main() {
    env_logger::init();

    // Generate some random keys.
    let n = 10_000_000;
    eprintln!("Generating keys..");
    let keys = ptr_hash::util::generate_keys(n);

    // Build the datastructure.
    eprintln!("Building mphf..");
    let start = std::time::Instant::now();
    let mphf = PtrHashXxh3::new(&keys, PtrHashParams::default());
    eprintln!("construction took: {:?}", start.elapsed());

    let path = "/tmp/test.mphf";
    let mut file = std::fs::File::create(path).unwrap();
    eprintln!("\nSerializing to {path}..");
    unsafe { mphf.serialize(&mut file).unwrap() };
    let len = file.metadata().unwrap().len();
    eprintln!("Size: {len}, bits/key: {}\n", len as f32 * 8. / n as f32);

    // Deserialize full PtrHash
    eprintln!("load full, without epserde..");
    let _mphf2 =
        unsafe { PtrHashXxh3::deserialize_full(&mut std::fs::File::open(path).unwrap()).unwrap() };

    // Ep-serde from memory.
    eprintln!("Load into memory, with epserde..");
    let _mphf2 = unsafe { PtrHashXxh3::load_mem(path).unwrap().uncase() };

    // Ep-serde from mmap.
    eprintln!("Load into mmap, with epserde..");
    let mem_case = unsafe {
        PtrHashXxh3::load_mmap(path, Flags::RANDOM_ACCESS | Flags::TRANSPARENT_HUGE_PAGES).unwrap()
    };
    let mphf2 = mem_case.uncase();

    // Ep-serde from manually read memory.
    // May fail because we require 64-byte alignment, and `fs::read` is not guaranteed to give that.
    let b = std::fs::read(path).unwrap();
    let _mphf2 = unsafe { PtrHashXxh3::deserialize_eps(b.as_ref()).unwrap() };

    eprintln!("Testing..");
    // Get the minimal index of a key.
    let key = 0;
    let idx = mphf2.index(&key);
    assert!(idx < n);

    // Get the non-minimal index of a key. Slightly faster.
    let _idx = mphf2.index_no_remap(&key);

    // An iterator over the indices of the keys.
    // 32: number of iterations ahead to prefetch.
    // true: remap to a minimal key in [0, n).
    eprintln!("Check sum..");
    let indices = mphf2.index_stream_maybe_remap::<32, true, _>(&keys);
    assert_eq!(indices.sum::<usize>(), (n * (n - 1)) / 2);

    // Test that all items map to different indices
    eprintln!("Check taken..");
    let mut taken = vec![false; n];
    for key in keys {
        let idx = mphf2.index(&key);
        assert!(!taken[idx]);
        taken[idx] = true;
    }

    eprintln!("\n\nDO NOT FORGET TO CLEAN UP {path} !!!\n\n");
}