fasthash.rs 91.4%

64 of 70 lines run, 21 of 25 functions · run #358 on main · run missed

//! A fast hasher for the in-memory graphs (spec §25): their keys begin with
//! BLAKE3 hashes, so the bytes are already uniform and SipHash's cost buys
//! nothing. A per-process random seed keeps bucket placement unpredictable,
//! so keys chosen by someone else cannot be aimed at one bucket.

use std::hash::{BuildHasher, Hasher};
use std::sync::OnceLock;

fn seed() -> u64 {
    static SEED: OnceLock<u64> = OnceLock::new();
    *SEED.get_or_init(rand::random::<u64>)
}

/// Builds [`FastHasher`]s with the process seed.
#[derive(Clone, Copy, Debug)]
pub struct FastState(u64);

impl Default for FastState {
    fn default() -> FastState {
        FastState(seed())
    }
}

impl BuildHasher for FastState {
    type Hasher = FastHasher;
    fn build_hasher(&self) -> FastHasher {
        FastHasher(self.0)
    }
}

/// Folds each 8-byte word into the state with a multiply and rotate, then
/// finishes with SplitMix64's mixer so every input bit reaches every output bit.
pub struct FastHasher(u64);

impl FastHasher {
    #[inline]
    fn mix(&mut self, word: u64) {
        self.0 = (self.0 ^ word)
            .wrapping_mul(0x9e37_79b9_7f4a_7c15)
            .rotate_left(31);
    }
}

impl Hasher for FastHasher {
    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        let (chunks, rest) = bytes.as_chunks::<8>();
        for c in chunks {
            self.mix(u64::from_le_bytes(*c));
        }
        if !rest.is_empty() {
            let mut b = [0u8; 8];
            b[..rest.len()].copy_from_slice(rest);
            self.mix(u64::from_le_bytes(b) ^ ((rest.len() as u64) << 59));
        }
    }

    #[inline]
    fn write_u8(&mut self, n: u8) {
        self.mix(n as u64 | 0x100);
    }

    #[inline]
    fn write_u32(&mut self, n: u32) {
        self.mix(n as u64 | 0x1_0000_0000);
    }

    #[inline]
    fn write_u64(&mut self, n: u64) {
        self.mix(n);
    }

    #[inline]
    fn write_usize(&mut self, n: usize) {
        self.mix(n as u64);
    }

    #[inline]
    fn finish(&self) -> u64 {
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
        z ^ (z >> 31)
    }
}

pub type FastMap<K, V> = std::collections::HashMap<K, V, FastState>;
pub type FastSet<K> = std::collections::HashSet<K, FastState>;

#[cfg(test)]
mod tests {
    use super::*;
    use std::hash::Hash;

    fn h<T: Hash + ?Sized>(state: &FastState, v: &T) -> u64 {
        state.hash_one(v)
    }

    #[test]
    fn distinct_keys_spread_and_equal_keys_agree() {
        let s = FastState(42);
        let a = ([7u8; 32], 1u32);
        assert_eq!(h(&s, &a), h(&s, &a));
        assert_ne!(h(&s, &a), h(&s, &([7u8; 32], 2u32)), "the index matters");
        assert_ne!(
            h(&s, &[1u8, 2, 3][..]),
            h(&s, &[1u8, 2, 3, 0][..]),
            "length matters"
        );
        // Consecutive indices of one change land in different buckets of a small table.
        let buckets: std::collections::HashSet<u64> =
            (0..64u32).map(|i| h(&s, &([9u8; 32], i)) & 63).collect();
        assert!(buckets.len() > 32, "{} of 64 buckets used", buckets.len());
        assert_ne!(
            h(&FastState(1), &a),
            h(&FastState(2), &a),
            "the seed matters"
        );
    }

    #[test]
    fn maps_work() {
        let mut m: FastMap<([u8; 32], u32), u32> = FastMap::default();
        for i in 0..10_000u32 {
            m.insert(([(i % 251) as u8; 32], i), i);
        }
        assert_eq!(m.len(), 10_000);
        assert_eq!(m[&([77u8; 32], 77)], 77);
    }
}

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	224793×	fn seed() -> u64 {
10		static SEED: OnceLock<u64> = OnceLock::new();
11	224793×	*SEED.get_or_init(rand::random::<u64>)
12	224793×	}
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	224793×	fn default() -> FastState {
20	224793×	FastState(seed())
21	224793×	}
22		}
23
24		impl BuildHasher for FastState {
25		type Hasher = FastHasher;
26	63185690×	fn build_hasher(&self) -> FastHasher {
27	63185690×	FastHasher(self.0)
28	63185690×	}
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	306150357×	fn mix(&mut self, word: u64) {
38	306150357×	self.0 = (self.0 ^ word)
39	306150357×	.wrapping_mul(0x9e37_79b9_7f4a_7c15)
40	306150357×	.rotate_left(31);
41	306150357×	}
42		}
43
44		impl Hasher for FastHasher {
45		#[inline]
46	62930116×	fn write(&mut self, bytes: &[u8]) {
47	62930116×	let (chunks, rest) = bytes.as_chunks::<8>();
48	208501894×	for c in chunks {
49	208501894×	self.mix(u64::from_le_bytes(*c));
50	208501894×	}
51	62930116×	if !rest.is_empty() {
52	2×	let mut b = [0u8; 8];
53	2×	b[..rest.len()].copy_from_slice(rest);
54	2×	self.mix(u64::from_le_bytes(b) ^ ((rest.len() as u64) << 59));
55	62930114×	}
56	62930116×	}
57
58		#[inline]
59	0×	fn write_u8(&mut self, n: u8) {
60	0×	self.mix(n as u64 \| 0x100);
61	0×	}
62
63		#[inline]
64	31457524×	fn write_u32(&mut self, n: u32) {
65	31457524×	self.mix(n as u64 \| 0x1_0000_0000);
66	31457524×	}
67
68		#[inline]
69	0×	fn write_u64(&mut self, n: u64) {
70	0×	self.mix(n);
71	0×	}
72
73		#[inline]
74	66190937×	fn write_usize(&mut self, n: usize) {
75	66190937×	self.mix(n as u64);
76	66190937×	}
77
78		#[inline]
79	63185690×	fn finish(&self) -> u64 {
80	63185690×	let mut z = self.0;
81	63185690×	z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
82	63185690×	z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
83	63185690×	z ^ (z >> 31)
84	63185690×	}
85		}
86
87		pub type FastMap<K, V> = std::collections::HashMap<K, V, FastState>;
88		pub type FastSet<K> = std::collections::HashSet<K, FastState>;
89
90		#[cfg(test)]
91		mod tests {
92		use super::*;
93		use std::hash::Hash;
94
95	72×	fn h<T: Hash + ?Sized>(state: &FastState, v: &T) -> u64 {
96	72×	state.hash_one(v)
97	72×	}
98
99		#[test]
100	1×	fn distinct_keys_spread_and_equal_keys_agree() {
101	1×	let s = FastState(42);
102	1×	let a = ([7u8; 32], 1u32);
103	1×	assert_eq!(h(&s, &a), h(&s, &a));
104	1×	assert_ne!(h(&s, &a), h(&s, &([7u8; 32], 2u32)), "the index matters");
105	1×	assert_ne!(
106	1×	h(&s, &[1u8, 2, 3][..]),
107	1×	h(&s, &[1u8, 2, 3, 0][..]),
108		"length matters"
109		);
110		// Consecutive indices of one change land in different buckets of a small table.
111	1×	let buckets: std::collections::HashSet<u64> =
112	64×	(0..64u32).map(\|i\| h(&s, &([9u8; 32], i)) & 63).collect();
113	1×	assert!(buckets.len() > 32, "{} of 64 buckets used", buckets.len());
114	1×	assert_ne!(
115	1×	h(&FastState(1), &a),
116	1×	h(&FastState(2), &a),
117		"the seed matters"
118		);
119	1×	}
120
121		#[test]
122	1×	fn maps_work() {
123	1×	let mut m: FastMap<([u8; 32], u32), u32> = FastMap::default();
124	10000×	for i in 0..10_000u32 {
125	10000×	m.insert(([(i % 251) as u8; 32], i), i);
126	10000×	}
127	1×	assert_eq!(m.len(), 10_000);
128	1×	assert_eq!(m[&([77u8; 32], 77)], 77);
129	1×	}
130		}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

Coverage / crates/oxy-core/src/fasthash.rs 91.4%

Keyboard