zsh/extensions/
fast_hash.rs

1//! Fast, dependency-free hasher for the shell's internal name→node tables.
2//!
3//! # Why
4//!
5//! zsh's hash tables (parameters, functions, aliases, …) are keyed by short
6//! identifier strings and looked up constantly — every variable read/write,
7//! every command dispatch. zshrs backs them with `std::collections::HashMap`,
8//! whose default hasher is SipHash-1-3: cryptographically DoS-resistant, but
9//! ~2–3× slower than necessary for short internal keys that never come from
10//! an adversary choosing collisions. Profiling a string/param workload showed
11//! HashMap hashing/probing as the single largest cost (dwarfing everything
12//! else). C's `hashtable.c` uses a trivial multiply-hash; this restores that
13//! choice.
14//!
15//! [`FxBuildHasher`] is the FxHash algorithm (as used by rustc and Firefox):
16//! a rotate + XOR + multiply per machine word. Not DoS-resistant, which is
17//! irrelevant for process-internal symbol tables. Use via [`FastMap`], a drop-in
18//! `HashMap` type alias.
19
20use std::hash::{BuildHasherDefault, Hasher};
21
22/// FxHash constant (golden-ratio-derived odd multiplier), matching rustc_hash.
23const K: u64 = 0x51_7c_c1_b7_27_22_0a_95;
24
25/// FxHash hasher — rotate/xor/multiply per word. Fast for short keys.
26#[derive(Default)]
27pub struct FxHasher {
28    hash: u64,
29}
30
31impl FxHasher {
32    #[inline]
33    fn add(&mut self, i: u64) {
34        self.hash = (self.hash.rotate_left(5) ^ i).wrapping_mul(K);
35    }
36}
37
38impl Hasher for FxHasher {
39    #[inline]
40    fn write(&mut self, mut bytes: &[u8]) {
41        // Consume 8 bytes at a time, then the tail. Byte order doesn't matter
42        // for an internal table as long as it's consistent within a run.
43        while bytes.len() >= 8 {
44            let mut buf = [0u8; 8];
45            buf.copy_from_slice(&bytes[..8]);
46            self.add(u64::from_ne_bytes(buf));
47            bytes = &bytes[8..];
48        }
49        if !bytes.is_empty() {
50            let mut buf = [0u8; 8];
51            buf[..bytes.len()].copy_from_slice(bytes);
52            self.add(u64::from_ne_bytes(buf));
53        }
54    }
55
56    #[inline]
57    fn write_u8(&mut self, i: u8) {
58        self.add(i as u64);
59    }
60
61    #[inline]
62    fn write_usize(&mut self, i: usize) {
63        self.add(i as u64);
64    }
65
66    #[inline]
67    fn finish(&self) -> u64 {
68        // Final avalanche so the low bits (used for bucket selection) mix.
69        self.hash.wrapping_mul(K).rotate_left(26)
70    }
71}
72
73/// `BuildHasher` producing [`FxHasher`]s.
74pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
75
76/// Drop-in `HashMap` alias using the fast hasher. Same API as
77/// `std::collections::HashMap`; construct with `FastMap::default()`.
78pub type FastMap<K, V> = std::collections::HashMap<K, V, FxBuildHasher>;
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use std::hash::BuildHasher;
84
85    #[test]
86    fn distinct_keys_hash_distinctly_enough() {
87        let bh = FxBuildHasher::default();
88        let names = ["PATH", "IFS", "HOME", "x", "_p9k__x", "PWD", "a", "bb"];
89        let hashes: Vec<u64> = names
90            .iter()
91            .map(|n| {
92                let mut h = bh.build_hasher();
93                h.write(n.as_bytes());
94                h.finish()
95            })
96            .collect();
97        // No accidental all-equal collisions across a typical name set.
98        for i in 0..hashes.len() {
99            for j in i + 1..hashes.len() {
100                assert_ne!(hashes[i], hashes[j], "{} vs {}", names[i], names[j]);
101            }
102        }
103    }
104
105    #[test]
106    fn fastmap_roundtrips() {
107        let mut m: FastMap<String, i32> = FastMap::default();
108        m.insert("PATH".into(), 1);
109        m.insert("HOME".into(), 2);
110        assert_eq!(m.get("PATH"), Some(&1));
111        assert_eq!(m.get("HOME"), Some(&2));
112        assert_eq!(m.get("nope"), None);
113        assert_eq!(m.len(), 2);
114    }
115}
zsh/extensions/fast_hash.rs

zsh/extensions/
fast_hash.rs
