deed_diagnostics/
hashing.rs

1//! A hash for keys that are already numbers.
2//!
3//! Everything this compiler keys a map by is a small integer or two: a
4//! [`Span`](crate::Span) is a pair of byte offsets, a definition is an index
5//! into a table. The standard library hashes with SipHash, which is chosen to
6//! survive an attacker choosing the keys. Nothing here has that problem: the
7//! keys come out of a file the compiler was handed, and a file that could pick
8//! its own spans could do far worse than make a hash map slow.
9//!
10//! Measured before it was written, because that is the rule. Reading a name
11//! was the most expensive small thing in the language and it is two lookups,
12//! one from the span where the name is written to what it refers to and one
13//! from that to the value. `crates/deed-driver/examples/interpreting.rs` says
14//! what a name costs and what it costs now.
15//!
16//! The mixing is one multiply and one shift, the same shape as the hash used
17//! by every compiler that has had this problem, and it is written out here
18//! rather than depended on because it is nine lines.
19
20use std::hash::{BuildHasherDefault, Hasher};
21
22/// A [`BuildHasher`](std::hash::BuildHasher) for maps keyed by numbers.
23pub type ByNumber = BuildHasherDefault<NumberHasher>;
24
25/// Mixes whatever it is given into one word.
26///
27/// The constant is the 64 bit odd number used for this everywhere: multiplying
28/// by an odd number is reversible, so no two inputs collide before the shift,
29/// and the shift moves the high bits, which the multiply mixed best, down to
30/// where a hash map reads them.
31#[derive(Default)]
32pub struct NumberHasher(u64);
33
34const MIX: u64 = 0x517c_c1b7_2722_0a95;
35
36impl NumberHasher {
37    fn add(&mut self, word: u64) {
38        self.0 = (self.0 ^ word).wrapping_mul(MIX);
39    }
40}
41
42impl Hasher for NumberHasher {
43    fn finish(&self) -> u64 {
44        // The multiply mixes upward, so the answer lives in the high bits.
45        self.0 ^ (self.0 >> 32)
46    }
47
48    /// Bytes, for a key that is not a number after all.
49    ///
50    /// Kept correct rather than fast: `Hasher` is one trait and a map keyed by
51    /// something else would otherwise get a hash that ignores most of it. Slow
52    /// and right beats fast and wrong, and nothing this is used for takes this
53    /// path.
54    fn write(&mut self, bytes: &[u8]) {
55        for chunk in bytes.chunks(8) {
56            let mut word = [0u8; 8];
57            word[..chunk.len()].copy_from_slice(chunk);
58            self.add(u64::from_le_bytes(word));
59        }
60    }
61
62    fn write_u8(&mut self, value: u8) {
63        self.add(u64::from(value));
64    }
65
66    fn write_u16(&mut self, value: u16) {
67        self.add(u64::from(value));
68    }
69
70    fn write_u32(&mut self, value: u32) {
71        self.add(u64::from(value));
72    }
73
74    fn write_u64(&mut self, value: u64) {
75        self.add(value);
76    }
77
78    fn write_usize(&mut self, value: usize) {
79        self.add(value as u64);
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86    use std::collections::HashMap;
87    use std::hash::Hash;
88
89    fn hash_of<T: Hash>(value: &T) -> u64 {
90        let mut hasher = NumberHasher::default();
91        value.hash(&mut hasher);
92        hasher.finish()
93    }
94
95    /// The thing a hash has to do. Two keys that differ in either half have to
96    /// be able to tell each other apart, and a hash that ignored the second
97    /// word would pass every other test in this file.
98    #[test]
99    fn two_keys_that_differ_hash_differently() {
100        assert_ne!(hash_of(&(1u32, 2u32)), hash_of(&(2u32, 1u32)));
101        assert_ne!(hash_of(&(0u32, 1u32)), hash_of(&(0u32, 2u32)));
102        assert_ne!(hash_of(&(1u32, 0u32)), hash_of(&(2u32, 0u32)));
103    }
104
105    /// And the thing a hash map needs on top of that: the same key twice is
106    /// the same entry, whichever map it is in.
107    #[test]
108    fn a_map_keyed_by_it_still_behaves_like_a_map() {
109        let mut map: HashMap<(u32, u32), &str, ByNumber> = HashMap::default();
110        for start in 0..64u32 {
111            map.insert((start, start + 3), "here");
112        }
113
114        assert_eq!(map.len(), 64);
115        assert_eq!(map.get(&(7, 10)), Some(&"here"));
116        assert_eq!(map.get(&(7, 11)), None);
117    }
118
119    /// Bytes go through the slow path, which has to be a hash rather than a
120    /// constant, or a map keyed by a string would put everything in one bucket.
121    #[test]
122    fn a_key_that_is_not_a_number_is_still_hashed() {
123        assert_ne!(hash_of(&"one"), hash_of(&"two"));
124        assert_ne!(hash_of(&"a longer key than eight bytes"), hash_of(&"one"));
125    }
126}
deed_diagnostics/hashing.rs

deed_diagnostics/
hashing.rs
