OXYGENHUB
# da652d6392d8 oxygen / crates / oxy-core / src / fasthash.rs
3.6 KiB · Rust · last changed Faster state loading: seeded fast hashing for the file graphs, no unused predecessor map, inline successor sets, lines moved rather than copied; OXY_TIMINGS=1 prints snapshot phase timings. Clean status at 10 000 files 0.96 s to 0.52 s, memory 657 to 239 MB 1 month ago source blame history raw
1 
//! A fast hasher for the in-memory graphs (spec §25): their keys begin with
2 
//! BLAKE3 hashes, so the bytes are already uniform and SipHash's cost buys
3 
//! nothing. A per-process random seed keeps bucket placement unpredictable,
4 
//! so keys chosen by someone else cannot be aimed at one bucket.
5
6 
use std::hash::{BuildHasher, Hasher};
7 
use std::sync::OnceLock;
8
9 
fn seed() -> u64 {
10 
    static SEED: OnceLock<u64> = OnceLock::new();
11 
    *SEED.get_or_init(rand::random::<u64>)
12 
}
13
14 
/// Builds [`FastHasher`]s with the process seed.
15 
#[derive(Clone, Copy, Debug)]
16 
pub struct FastState(u64);
17
18 
impl Default for FastState {
19 
    fn default() -> FastState {
20 
        FastState(seed())
21 
    }
22 
}
23
24 
impl BuildHasher for FastState {
25 
    type Hasher = FastHasher;
26 
    fn build_hasher(&self) -> FastHasher {
27 
        FastHasher(self.0)
28 
    }
29 
}
30
31 
/// Folds each 8-byte word into the state with a multiply and rotate, then
32 
/// finishes with SplitMix64's mixer so every input bit reaches every output bit.
33 
pub struct FastHasher(u64);
34
35 
impl FastHasher {
36 
    #[inline]
37 
    fn mix(&mut self, word: u64) {
38 
        self.0 = (self.0 ^ word)
39 
            .wrapping_mul(0x9e37_79b9_7f4a_7c15)
40 
            .rotate_left(31);
41 
    }
42 
}
43
44 
impl Hasher for FastHasher {
45 
    #[inline]
46 
    fn write(&mut self, bytes: &[u8]) {
47 
        let mut chunks = bytes.chunks_exact(8);
48 
        for c in &mut chunks {
49 
            self.mix(u64::from_le_bytes(c.try_into().unwrap()));
50 
        }
51 
        let rest = chunks.remainder();
52 
        if !rest.is_empty() {
53 
            let mut b = [0u8; 8];
54 
            b[..rest.len()].copy_from_slice(rest);
55 
            self.mix(u64::from_le_bytes(b) ^ ((rest.len() as u64) << 59));
56 
        }
57 
    }
58
59 
    #[inline]
60 
    fn write_u8(&mut self, n: u8) {
61 
        self.mix(n as u64 | 0x100);
62 
    }
63
64 
    #[inline]
65 
    fn write_u32(&mut self, n: u32) {
66 
        self.mix(n as u64 | 0x1_0000_0000);
67 
    }
68
69 
    #[inline]
70 
    fn write_u64(&mut self, n: u64) {
71 
        self.mix(n);
72 
    }
73
74 
    #[inline]
75 
    fn write_usize(&mut self, n: usize) {
76 
        self.mix(n as u64);
77 
    }
78
79 
    #[inline]
80 
    fn finish(&self) -> u64 {
81 
        let mut z = self.0;
82 
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
83 
        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
84 
        z ^ (z >> 31)
85 
    }
86 
}
87
88 
pub type FastMap<K, V> = std::collections::HashMap<K, V, FastState>;
89 
pub type FastSet<K> = std::collections::HashSet<K, FastState>;
90
91 
#[cfg(test)]
92 
mod tests {
93 
    use super::*;
94 
    use std::hash::Hash;
95
96 
    fn h<T: Hash + ?Sized>(state: &FastState, v: &T) -> u64 {
97 
        state.hash_one(v)
98 
    }
99
100 
    #[test]
101 
    fn distinct_keys_spread_and_equal_keys_agree() {
102 
        let s = FastState(42);
103 
        let a = ([7u8; 32], 1u32);
104 
        assert_eq!(h(&s, &a), h(&s, &a));
105 
        assert_ne!(h(&s, &a), h(&s, &([7u8; 32], 2u32)), "the index matters");
106 
        assert_ne!(
107 
            h(&s, &[1u8, 2, 3][..]),
108 
            h(&s, &[1u8, 2, 3, 0][..]),
109 
            "length matters"
110 
        );
111 
        // Consecutive indices of one change land in different buckets of a small table.
112 
        let buckets: std::collections::HashSet<u64> =
113 
            (0..64u32).map(|i| h(&s, &([9u8; 32], i)) & 63).collect();
114 
        assert!(buckets.len() > 32, "{} of 64 buckets used", buckets.len());
115 
        assert_ne!(
116 
            h(&FastState(1), &a),
117 
            h(&FastState(2), &a),
118 
            "the seed matters"
119 
        );
120 
    }
121
122 
    #[test]
123 
    fn maps_work() {
124 
        let mut m: FastMap<([u8; 32], u32), u32> = FastMap::default();
125 
        for i in 0..10_000u32 {
126 
            m.insert(([(i % 251) as u8; 32], i), i);
127 
        }
128 
        assert_eq!(m.len(), 10_000);
129 
        assert_eq!(m[&([77u8; 32], 77)], 77);
130 
    }
131 
}