rete_core/
hll.rs

1//! A small HyperLogLog (2^14 registers, 16 KiB, ~0.8 % relative error), shared by `rete estimate`
2//! and the memory-bounded build's early term-count refusal ([`crate::extbuild`]).
3
4/// HyperLogLog cardinality estimator (Flajolet et al.), 2^P registers.
5pub struct Hll {
6    reg: Vec<u8>,
7}
8
9const P: u32 = 14;
10const M: usize = 1 << P;
11
12impl Default for Hll {
13    fn default() -> Self {
14        Self::new()
15    }
16}
17
18impl Hll {
19    /// An empty estimator.
20    pub fn new() -> Self {
21        Hll { reg: vec![0u8; M] }
22    }
23
24    /// Observe one term.
25    pub fn add(&mut self, s: &str) {
26        let h = fxhash64(s.as_bytes());
27        let idx = (h >> (64 - P)) as usize;
28        // rank = position of the first 1 bit in the remaining bits (1-based)
29        let w = (h << P) | (1 << (P - 1));
30        let rank = (w.leading_zeros() + 1) as u8;
31        if rank > self.reg[idx] {
32            self.reg[idx] = rank;
33        }
34    }
35
36    /// The estimated number of distinct terms observed.
37    pub fn count(&self) -> u64 {
38        let m = M as f64;
39        let alpha = 0.7213 / (1.0 + 1.079 / m);
40        let sum: f64 = self.reg.iter().map(|&r| 2f64.powi(-(r as i32))).sum();
41        let raw = alpha * m * m / sum;
42        let zeros = self.reg.iter().filter(|&&r| r == 0).count();
43        // small-range correction: linear counting while registers are sparse
44        if raw <= 2.5 * m && zeros > 0 {
45            (m * (m / zeros as f64).ln()).round() as u64
46        } else {
47            raw.round() as u64
48        }
49    }
50}
51
52/// A fast, allocation-free 64-bit string hash (FxHash-style, good enough for HLL).
53fn fxhash64(bytes: &[u8]) -> u64 {
54    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
55    for &b in bytes {
56        h ^= b as u64;
57        h = h.wrapping_mul(0x1000_0000_01b3);
58    }
59    // final avalanche so the leading bits are well mixed (HLL reads the top P)
60    h ^= h >> 33;
61    h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
62    h ^= h >> 33;
63    h
64}
rete_core/hll.rs

rete_core/
hll.rs
