Struct HyperLogLog 

pub struct HyperLogLog { /* private fields */ }

Implementations

impl HyperLogLog

pub fn to_bytes(&self) -> Vec<u8>

Serialise to the canonical dense form: an 8-byte header then the raw register array. Length is always 8 + 2^p, so a reader can size the allocation from the header alone.

Examples found in repository

examples/sample_app.rs (line 212)

fn collector_fan_in(tape: &[Event]) {
    println!("\n== collector: merge shipped sketches into a firm-wide reach ==");

    let mut per_venue = [HyperLogLog::new(14), HyperLogLog::new(14)];
    for e in tape {
        per_venue[e.venue as usize].add_u64(e.account);
    }
    let shipped: Vec<Vec<u8>> = per_venue.iter().map(|h| h.to_bytes()).collect();
    let on_wire: usize = shipped.iter().map(|b| b.len()).sum();

    let mut firm = HyperLogLog::new(14);
    for bytes in &shipped {
        let decoded = HyperLogLog::from_bytes(bytes).expect("collector reads its own format");
        firm.merge(&decoded).expect("same precision");
    }
    println!(
        "  {} sketches on the wire, {} bytes total",
        shipped.len(),
        on_wire
    );
    println!(
        "  raw ids would have been ~{} bytes",
        tape.len() * core::mem::size_of::<u64>()
    );
    println!("  firm-wide reach: {:.0} (true 50000)", firm.estimate());
    assert!(
        (firm.estimate() - 50_000.0).abs() / 50_000.0 < 0.05,
        "merged reach within 5%"
    );
}

pub fn from_bytes(bytes: &[u8]) -> Result<Self, HllError>

Parse a dense buffer. A sparse buffer is rejected with UnsupportedEncoding rather than silently densified - use SparseHyperLogLog::from_bytes, which reads both.

Examples found in repository

examples/sample_app.rs (line 217)

fn collector_fan_in(tape: &[Event]) {
    println!("\n== collector: merge shipped sketches into a firm-wide reach ==");

    let mut per_venue = [HyperLogLog::new(14), HyperLogLog::new(14)];
    for e in tape {
        per_venue[e.venue as usize].add_u64(e.account);
    }
    let shipped: Vec<Vec<u8>> = per_venue.iter().map(|h| h.to_bytes()).collect();
    let on_wire: usize = shipped.iter().map(|b| b.len()).sum();

    let mut firm = HyperLogLog::new(14);
    for bytes in &shipped {
        let decoded = HyperLogLog::from_bytes(bytes).expect("collector reads its own format");
        firm.merge(&decoded).expect("same precision");
    }
    println!(
        "  {} sketches on the wire, {} bytes total",
        shipped.len(),
        on_wire
    );
    println!(
        "  raw ids would have been ~{} bytes",
        tape.len() * core::mem::size_of::<u64>()
    );
    println!("  firm-wide reach: {:.0} (true 50000)", firm.estimate());
    assert!(
        (firm.estimate() - 50_000.0).abs() / 50_000.0 < 0.05,
        "merged reach within 5%"
    );
}

impl HyperLogLog

pub fn new(precision: u32) -> Self

New empty HLL at the given precision. precision is clamped to [4, 18]; 14 gives ~16k registers / ~16 KB / ~1% std error. Use HyperLogLog::try_new when a caller-supplied precision should be rejected rather than silently pulled into range.

Examples found in repository

examples/sample_app.rs (line 99)

fn gateway_sessions(tape: &[Event]) {
    println!("== gateway: distinct sessions this window ==");
    let mut hll = HyperLogLog::new(14);
    let mut first_sightings = 0u64;
    for e in tape {
        if hll.add_u64(e.session) {
            first_sightings += 1;
        }
    }
    let est = hll.estimate();
    println!("  {} messages -> {:.0} distinct sessions", tape.len(), est);
    println!(
        "  {} registers advanced, {} bytes of state, +/- {:.2}% standard error",
        first_sightings,
        hll.state_bytes(),
        hll.standard_error() * 100.0
    );
    assert!(est > 30_000.0 && est < 50_000.0, "~40k sessions, got {est}");
}

/// Sizing runs the other way round in production: you are handed an error
/// budget, not a precision. `precision_for_standard_error` turns the budget
/// into the cheapest register array that meets it.
fn size_from_an_error_budget() {
    println!("\n== sizing: error budget -> byte budget ==");
    for budget in [0.05, 0.02, 0.01, 0.005] {
        let p = HyperLogLog::precision_for_standard_error(budget);
        let hll = HyperLogLog::new(p);
        println!(
            "  budget {:>5.1}%  ->  p={:<2} {:>6} bytes, actual {:.5}%",
            budget * 100.0,
            p,
            hll.state_bytes(),
            hll.standard_error() * 100.0
        );
    }
}

/// `sparse`: risk wants distinct counterparties per symbol. Most of the book is
/// thin, so allocating 16 KB per name would cost 128 KB here and gigabytes
/// across a real universe. The sparse encoding pays only for registers actually
/// touched, and promotes the two busy names once they earn it.
#[cfg(feature = "sparse")]
fn per_symbol_counterparties(tape: &[Event]) {
    use subms_hyperloglog::SparseHyperLogLog;
    println!("\n== risk: distinct counterparties per symbol ==");

    let mut books: Vec<SparseHyperLogLog> = (0..SYMBOLS.len())
        .map(|_| SparseHyperLogLog::with_threshold(14, 2_000))
        .collect();
    for e in tape {
        books[e.symbol].add_u64(e.counterparty);
    }

    let mut sparse_bytes = 0usize;
    for (i, b) in books.iter().enumerate() {
        println!(
            "  {:<5} {:>7.0} counterparties  {:>6} bytes  {}",
            SYMBOLS[i],
            b.estimate(),
            b.state_bytes(),
            if b.is_sparse() { "sparse" } else { "dense" }
        );
        sparse_bytes += b.state_bytes();
    }
    let dense_bytes = SYMBOLS.len() * 16_384;
    println!("  total {sparse_bytes} bytes against {dense_bytes} if every name held a dense array");
    assert!(
        sparse_bytes < dense_bytes,
        "sparse must win on the long tail"
    );
}

/// `union-intersect`: how many accounts trade on both venues? Inclusion-
/// exclusion answers it from two sketches. The error bound is printed next to
/// the answer because it scales with |A| + |B| rather than with the overlap,
/// and an overlap smaller than its own bound is not a number to act on.
#[cfg(feature = "union-intersect")]
fn cross_venue_overlap(tape: &[Event]) {
    use subms_hyperloglog::{estimate_intersect, estimate_union, intersect_error_bound};
    println!("\n== venues: account reach and overlap ==");

    let mut a = HyperLogLog::new(14);
    let mut b = HyperLogLog::new(14);
    for e in tape {
        if e.venue == 0 {
            a.add_u64(e.account);
        } else {
            b.add_u64(e.account);
        }
    }
    let union = estimate_union(&a, &b).expect("same precision");
    let inter = estimate_intersect(&a, &b).expect("same precision");
    let bound = intersect_error_bound(&a, &b).expect("same precision");
    println!("  venue 0: {:>7.0} accounts", a.estimate());
    println!("  venue 1: {:>7.0} accounts", b.estimate());
    println!("  reach:   {union:>7.0} (true 50000)");
    println!("  both:    {inter:>7.0} (true 10000) +/- {bound:.0}");
    assert!(
        (union - 50_000.0).abs() / 50_000.0 < 0.05,
        "reach within 5%, got {union}"
    );
    assert!(inter > 0.0, "a 10k overlap must survive the subtraction");
}

/// `serialize`: each venue ships its sketch, not its account list. The
/// collector decodes and merges, and the firm-wide number falls out of 16 KB
/// per venue instead of a million ids on the wire.
fn collector_fan_in(tape: &[Event]) {
    println!("\n== collector: merge shipped sketches into a firm-wide reach ==");

    let mut per_venue = [HyperLogLog::new(14), HyperLogLog::new(14)];
    for e in tape {
        per_venue[e.venue as usize].add_u64(e.account);
    }
    let shipped: Vec<Vec<u8>> = per_venue.iter().map(|h| h.to_bytes()).collect();
    let on_wire: usize = shipped.iter().map(|b| b.len()).sum();

    let mut firm = HyperLogLog::new(14);
    for bytes in &shipped {
        let decoded = HyperLogLog::from_bytes(bytes).expect("collector reads its own format");
        firm.merge(&decoded).expect("same precision");
    }
    println!(
        "  {} sketches on the wire, {} bytes total",
        shipped.len(),
        on_wire
    );
    println!(
        "  raw ids would have been ~{} bytes",
        tape.len() * core::mem::size_of::<u64>()
    );
    println!("  firm-wide reach: {:.0} (true 50000)", firm.estimate());
    assert!(
        (firm.estimate() - 50_000.0).abs() / 50_000.0 < 0.05,
        "merged reach within 5%"
    );
}

examples/perf_features.rs (line 135)

fn main() -> io::Result<()> {
    let ks = keys();

    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
        .join("..")
        .join(".subms")
        .join("features")
        .join("rust.json");
    let existing = std::fs::read_to_string(&path).unwrap_or_default();
    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
    // Stamp the box these numbers came from. The bench runs wherever it is
    // invoked, so an unstamped manifest is indistinguishable from a fleet
    // capture; the renderer will not publish one it cannot attribute.
    let (source, instance) = SubMsP99Source::from_env();
    manifest.set_p99_source(source, instance.as_deref());

    // The baseline is base `add`, the per-op path. NOT base `estimate`: that
    // folds all 2^p registers, so classifying a per-key feature against it would
    // let anything look free.
    let mut base = HyperLogLog::new(CANON_P);
    let base_p50 = keyed_p50(&mut base, &ks[..OPS], |h, k| {
        h.add(k);
    });
    eprintln!("base add p50: {base_p50}ns");

    // ---------- sparse: a linear entry list until it earns the dense array ----------
    #[cfg(feature = "sparse")]
    {
        use subms_hyperloglog::SparseHyperLogLog;
        // Swept over SPARSE LIST LENGTH, not over precision. `add` linear-probes
        // the list, so length is the cost driver; precision only sets it
        // indirectly through the `m/4` promotion threshold, and swept that way
        // the curve is a step rather than a slope. At p=12 and p=15 the
        // structure promotes early, so BOTH low points measure the dense floor
        // (100ns) rather than a small sparse probe, and at p=18 the list is
        // capped by the key count instead of by the threshold. The resulting
        // ratio landed either side of the classifier's guard - 40x in Rust,
        // 23x in Java - which is a measurement artefact, not a real disagreement.
        //
        // `with_threshold` exists for exactly this: pin promotion out of reach
        // and add n keys, and the swept axis IS the list length.
        //
        // The list is built to length n OUTSIDE the timed region, and the timed
        // ops are re-adds of keys already in it - a fixed OPS of them at every
        // size, so the op count is constant and the scan length is the only
        // thing varying. Re-adding rather than adding fresh keys keeps the list
        // from growing under measurement.
        let sw = sweep_sizes("sparse/add(list-len)", &LIST_LENS, |n| {
            let mut s = SparseHyperLogLog::with_threshold(CANON_P, n + 1);
            for k in &ks[..n] {
                s.add(k);
            }
            let mut h = SubMsPerfHarness::new("hll-feature", "rust");
            let st = h.stage("op", OPS);
            for i in 0..OPS {
                let k = &ks[(i * 7919) % n];
                st.time(|| s.add(k));
            }
            stat(&h, true)
        });
        // PINNED structural when the ratio test cannot carry it. `add`
        // linear-probes the sparse list, so it is O(entries) from the source and
        // the sweep above is monotonic and strongly rising. What it is not is
        // 32x: a long scan runs ~0.34 ns/element against ~0.93 for a short one,
        // so a true O(n) op measures ~23x over a 64x span and falls under the
        // classifier's 0.5 guard. Publishing that as hot-path would tell a
        // reader the probe is free at high precision. It is not, and the pin
        // says a human decided rather than dressing the decision as measured.
        let (cat, reason) = classify_feature(
            &sw,
            Some(base_p50),
            Some(subms::SubMsFeatureCategory::Structural),
        );

        let mut s = SparseHyperLogLog::new(CANON_P);
        let mut p99 = BTreeMap::new();
        p99.insert(
            "add".to_string(),
            keyed_p99(&mut s, &ks[..OPS], |x, k| {
                x.add(k);
            }),
        );
        p99.insert(
            "estimate".to_string(),
            bulk(
                || {
                    let mut x = SparseHyperLogLog::new(CANON_P);
                    for k in &ks[..OPS] {
                        x.add(k);
                    }
                    x
                },
                |x| _ = x.estimate(),
                false,
            ),
        );
        manifest.set_feature("sparse", cat, &p99, &reason);
    }

    // ---------- union-intersect: pairwise folds over both register arrays ----------
    #[cfg(feature = "union-intersect")]
    {
        use subms_hyperloglog::{estimate_intersect, estimate_union};
        // Both HLLs are built by `setup`, outside the timed region. A union is a
        // pure read of two register arrays, so repeating it does identical work.
        // Filled with `m` keys, not a fixed count. OCCUPANCY has to be held
        // constant or it, not size, is what the sweep measures: `estimate` costs
        // `2f64.powi(-r)` per register and `powi(0)` takes a fast path, so a
        // fixed key set against a growing array leaves 92% of registers zero at
        // p=18 against 0% at p=12. That reads as a per-register cost falling
        // with size, and it compressed a triple-O(m) op to 26x over 64x.
        let build = |p: u32| {
            let n = regs(p);
            let mut a = HyperLogLog::new(p);
            let mut b = HyperLogLog::new(p);
            for (i, k) in ks[..n].iter().enumerate() {
                a.add(k);
                if i % 2 == 0 {
                    b.add(k);
                }
            }
            (a, b)
        };
        let sw = sweep("union-intersect/estimate_union", |p| {
            bulk(
                || build(p),
                |(a, b)| _ = estimate_union(a, b).expect("same precision"),
                true,
            )
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p99 = BTreeMap::new();
        p99.insert(
            "union".to_string(),
            bulk(
                || build(CANON_P),
                |(a, b)| _ = estimate_union(a, b).expect("same precision"),
                false,
            ),
        );
        p99.insert(
            "intersect".to_string(),
            bulk(
                || build(CANON_P),
                |(a, b)| _ = estimate_intersect(a, b).expect("same precision"),
                false,
            ),
        );
        manifest.set_feature("union-intersect", cat, &p99, &reason);
    }

    std::fs::create_dir_all(path.parent().unwrap())?;
    std::fs::write(&path, manifest.to_json())?;
    io::stdout().write_all(manifest.to_json().as_bytes())?;
    Ok(())
}

pub fn try_new(precision: u32) -> Result<Self, HllError>

New empty HLL, rejecting a precision outside [4, 18] instead of clamping it. Reach for this when the precision comes from config or a wire message and a typo should fail loudly.

pub fn precision(&self) -> u32

pub fn register_count(&self) -> u32

pub fn standard_error(&self) -> f64

Analytic relative standard error, 1.04 / sqrt(m). This is the error the structure carries by construction, not a measurement of the current contents: at p=14 it is 0.813%, so a 1,000,000 estimate is one standard deviation away from anything in [992k, 1008k].

Examples found in repository

examples/sample_app.rs (line 112)

fn gateway_sessions(tape: &[Event]) {
    println!("== gateway: distinct sessions this window ==");
    let mut hll = HyperLogLog::new(14);
    let mut first_sightings = 0u64;
    for e in tape {
        if hll.add_u64(e.session) {
            first_sightings += 1;
        }
    }
    let est = hll.estimate();
    println!("  {} messages -> {:.0} distinct sessions", tape.len(), est);
    println!(
        "  {} registers advanced, {} bytes of state, +/- {:.2}% standard error",
        first_sightings,
        hll.state_bytes(),
        hll.standard_error() * 100.0
    );
    assert!(est > 30_000.0 && est < 50_000.0, "~40k sessions, got {est}");
}

/// Sizing runs the other way round in production: you are handed an error
/// budget, not a precision. `precision_for_standard_error` turns the budget
/// into the cheapest register array that meets it.
fn size_from_an_error_budget() {
    println!("\n== sizing: error budget -> byte budget ==");
    for budget in [0.05, 0.02, 0.01, 0.005] {
        let p = HyperLogLog::precision_for_standard_error(budget);
        let hll = HyperLogLog::new(p);
        println!(
            "  budget {:>5.1}%  ->  p={:<2} {:>6} bytes, actual {:.5}%",
            budget * 100.0,
            p,
            hll.state_bytes(),
            hll.standard_error() * 100.0
        );
    }
}

pub fn precision_for_standard_error(target: f64) -> u32

Smallest precision whose standard error is at or below target (expressed as a fraction, so 0.01 for 1%). Clamped to [4, 18], so a target finer than 0.26% returns 18 and the caller gets the best this recipe allocates for rather than an error.

Examples found in repository

examples/sample_app.rs (line 123)

fn size_from_an_error_budget() {
    println!("\n== sizing: error budget -> byte budget ==");
    for budget in [0.05, 0.02, 0.01, 0.005] {
        let p = HyperLogLog::precision_for_standard_error(budget);
        let hll = HyperLogLog::new(p);
        println!(
            "  budget {:>5.1}%  ->  p={:<2} {:>6} bytes, actual {:.5}%",
            budget * 100.0,
            p,
            hll.state_bytes(),
            hll.standard_error() * 100.0
        );
    }
}

pub fn state_bytes(&self) -> usize

Bytes of register state this sketch holds. Fixed at construction and independent of how many items it has seen.

Examples found in repository

examples/sample_app.rs (line 111)

fn gateway_sessions(tape: &[Event]) {
    println!("== gateway: distinct sessions this window ==");
    let mut hll = HyperLogLog::new(14);
    let mut first_sightings = 0u64;
    for e in tape {
        if hll.add_u64(e.session) {
            first_sightings += 1;
        }
    }
    let est = hll.estimate();
    println!("  {} messages -> {:.0} distinct sessions", tape.len(), est);
    println!(
        "  {} registers advanced, {} bytes of state, +/- {:.2}% standard error",
        first_sightings,
        hll.state_bytes(),
        hll.standard_error() * 100.0
    );
    assert!(est > 30_000.0 && est < 50_000.0, "~40k sessions, got {est}");
}

/// Sizing runs the other way round in production: you are handed an error
/// budget, not a precision. `precision_for_standard_error` turns the budget
/// into the cheapest register array that meets it.
fn size_from_an_error_budget() {
    println!("\n== sizing: error budget -> byte budget ==");
    for budget in [0.05, 0.02, 0.01, 0.005] {
        let p = HyperLogLog::precision_for_standard_error(budget);
        let hll = HyperLogLog::new(p);
        println!(
            "  budget {:>5.1}%  ->  p={:<2} {:>6} bytes, actual {:.5}%",
            budget * 100.0,
            p,
            hll.state_bytes(),
            hll.standard_error() * 100.0
        );
    }
}

pub fn is_empty(&self) -> bool

True while every register is still zero.

pub fn clear(&mut self)

Zero every register, keeping the allocation. Reuse across windows without re-allocating the array.

pub fn add(&mut self, key: &str) -> bool

Record a key. Returns true when the sketch changed - a register moved up, so this key was the first of its kind to land that deep. Matching PFADD’s return, and cheap enough to ignore when you do not want it.

Examples found in repository

examples/perf_features.rs (line 137)

fn main() -> io::Result<()> {
    let ks = keys();

    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
        .join("..")
        .join(".subms")
        .join("features")
        .join("rust.json");
    let existing = std::fs::read_to_string(&path).unwrap_or_default();
    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
    // Stamp the box these numbers came from. The bench runs wherever it is
    // invoked, so an unstamped manifest is indistinguishable from a fleet
    // capture; the renderer will not publish one it cannot attribute.
    let (source, instance) = SubMsP99Source::from_env();
    manifest.set_p99_source(source, instance.as_deref());

    // The baseline is base `add`, the per-op path. NOT base `estimate`: that
    // folds all 2^p registers, so classifying a per-key feature against it would
    // let anything look free.
    let mut base = HyperLogLog::new(CANON_P);
    let base_p50 = keyed_p50(&mut base, &ks[..OPS], |h, k| {
        h.add(k);
    });
    eprintln!("base add p50: {base_p50}ns");

    // ---------- sparse: a linear entry list until it earns the dense array ----------
    #[cfg(feature = "sparse")]
    {
        use subms_hyperloglog::SparseHyperLogLog;
        // Swept over SPARSE LIST LENGTH, not over precision. `add` linear-probes
        // the list, so length is the cost driver; precision only sets it
        // indirectly through the `m/4` promotion threshold, and swept that way
        // the curve is a step rather than a slope. At p=12 and p=15 the
        // structure promotes early, so BOTH low points measure the dense floor
        // (100ns) rather than a small sparse probe, and at p=18 the list is
        // capped by the key count instead of by the threshold. The resulting
        // ratio landed either side of the classifier's guard - 40x in Rust,
        // 23x in Java - which is a measurement artefact, not a real disagreement.
        //
        // `with_threshold` exists for exactly this: pin promotion out of reach
        // and add n keys, and the swept axis IS the list length.
        //
        // The list is built to length n OUTSIDE the timed region, and the timed
        // ops are re-adds of keys already in it - a fixed OPS of them at every
        // size, so the op count is constant and the scan length is the only
        // thing varying. Re-adding rather than adding fresh keys keeps the list
        // from growing under measurement.
        let sw = sweep_sizes("sparse/add(list-len)", &LIST_LENS, |n| {
            let mut s = SparseHyperLogLog::with_threshold(CANON_P, n + 1);
            for k in &ks[..n] {
                s.add(k);
            }
            let mut h = SubMsPerfHarness::new("hll-feature", "rust");
            let st = h.stage("op", OPS);
            for i in 0..OPS {
                let k = &ks[(i * 7919) % n];
                st.time(|| s.add(k));
            }
            stat(&h, true)
        });
        // PINNED structural when the ratio test cannot carry it. `add`
        // linear-probes the sparse list, so it is O(entries) from the source and
        // the sweep above is monotonic and strongly rising. What it is not is
        // 32x: a long scan runs ~0.34 ns/element against ~0.93 for a short one,
        // so a true O(n) op measures ~23x over a 64x span and falls under the
        // classifier's 0.5 guard. Publishing that as hot-path would tell a
        // reader the probe is free at high precision. It is not, and the pin
        // says a human decided rather than dressing the decision as measured.
        let (cat, reason) = classify_feature(
            &sw,
            Some(base_p50),
            Some(subms::SubMsFeatureCategory::Structural),
        );

        let mut s = SparseHyperLogLog::new(CANON_P);
        let mut p99 = BTreeMap::new();
        p99.insert(
            "add".to_string(),
            keyed_p99(&mut s, &ks[..OPS], |x, k| {
                x.add(k);
            }),
        );
        p99.insert(
            "estimate".to_string(),
            bulk(
                || {
                    let mut x = SparseHyperLogLog::new(CANON_P);
                    for k in &ks[..OPS] {
                        x.add(k);
                    }
                    x
                },
                |x| _ = x.estimate(),
                false,
            ),
        );
        manifest.set_feature("sparse", cat, &p99, &reason);
    }

    // ---------- union-intersect: pairwise folds over both register arrays ----------
    #[cfg(feature = "union-intersect")]
    {
        use subms_hyperloglog::{estimate_intersect, estimate_union};
        // Both HLLs are built by `setup`, outside the timed region. A union is a
        // pure read of two register arrays, so repeating it does identical work.
        // Filled with `m` keys, not a fixed count. OCCUPANCY has to be held
        // constant or it, not size, is what the sweep measures: `estimate` costs
        // `2f64.powi(-r)` per register and `powi(0)` takes a fast path, so a
        // fixed key set against a growing array leaves 92% of registers zero at
        // p=18 against 0% at p=12. That reads as a per-register cost falling
        // with size, and it compressed a triple-O(m) op to 26x over 64x.
        let build = |p: u32| {
            let n = regs(p);
            let mut a = HyperLogLog::new(p);
            let mut b = HyperLogLog::new(p);
            for (i, k) in ks[..n].iter().enumerate() {
                a.add(k);
                if i % 2 == 0 {
                    b.add(k);
                }
            }
            (a, b)
        };
        let sw = sweep("union-intersect/estimate_union", |p| {
            bulk(
                || build(p),
                |(a, b)| _ = estimate_union(a, b).expect("same precision"),
                true,
            )
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p99 = BTreeMap::new();
        p99.insert(
            "union".to_string(),
            bulk(
                || build(CANON_P),
                |(a, b)| _ = estimate_union(a, b).expect("same precision"),
                false,
            ),
        );
        p99.insert(
            "intersect".to_string(),
            bulk(
                || build(CANON_P),
                |(a, b)| _ = estimate_intersect(a, b).expect("same precision"),
                false,
            ),
        );
        manifest.set_feature("union-intersect", cat, &p99, &reason);
    }

    std::fs::create_dir_all(path.parent().unwrap())?;
    std::fs::write(&path, manifest.to_json())?;
    io::stdout().write_all(manifest.to_json().as_bytes())?;
    Ok(())
}

pub fn add_bytes(&mut self, key: &[u8]) -> bool

Record raw bytes. The string path funnels through here, so add("AAPL") and add_bytes(b"AAPL") land in the same register.

pub fn add_u64(&mut self, key: u64) -> bool

Record a 64-bit id without rendering it to a string first. Hashes the big-endian bytes, so the Rust and Java ports agree register for register on the same id.

Examples found in repository

examples/sample_app.rs (line 102)

fn gateway_sessions(tape: &[Event]) {
    println!("== gateway: distinct sessions this window ==");
    let mut hll = HyperLogLog::new(14);
    let mut first_sightings = 0u64;
    for e in tape {
        if hll.add_u64(e.session) {
            first_sightings += 1;
        }
    }
    let est = hll.estimate();
    println!("  {} messages -> {:.0} distinct sessions", tape.len(), est);
    println!(
        "  {} registers advanced, {} bytes of state, +/- {:.2}% standard error",
        first_sightings,
        hll.state_bytes(),
        hll.standard_error() * 100.0
    );
    assert!(est > 30_000.0 && est < 50_000.0, "~40k sessions, got {est}");
}

/// Sizing runs the other way round in production: you are handed an error
/// budget, not a precision. `precision_for_standard_error` turns the budget
/// into the cheapest register array that meets it.
fn size_from_an_error_budget() {
    println!("\n== sizing: error budget -> byte budget ==");
    for budget in [0.05, 0.02, 0.01, 0.005] {
        let p = HyperLogLog::precision_for_standard_error(budget);
        let hll = HyperLogLog::new(p);
        println!(
            "  budget {:>5.1}%  ->  p={:<2} {:>6} bytes, actual {:.5}%",
            budget * 100.0,
            p,
            hll.state_bytes(),
            hll.standard_error() * 100.0
        );
    }
}

/// `sparse`: risk wants distinct counterparties per symbol. Most of the book is
/// thin, so allocating 16 KB per name would cost 128 KB here and gigabytes
/// across a real universe. The sparse encoding pays only for registers actually
/// touched, and promotes the two busy names once they earn it.
#[cfg(feature = "sparse")]
fn per_symbol_counterparties(tape: &[Event]) {
    use subms_hyperloglog::SparseHyperLogLog;
    println!("\n== risk: distinct counterparties per symbol ==");

    let mut books: Vec<SparseHyperLogLog> = (0..SYMBOLS.len())
        .map(|_| SparseHyperLogLog::with_threshold(14, 2_000))
        .collect();
    for e in tape {
        books[e.symbol].add_u64(e.counterparty);
    }

    let mut sparse_bytes = 0usize;
    for (i, b) in books.iter().enumerate() {
        println!(
            "  {:<5} {:>7.0} counterparties  {:>6} bytes  {}",
            SYMBOLS[i],
            b.estimate(),
            b.state_bytes(),
            if b.is_sparse() { "sparse" } else { "dense" }
        );
        sparse_bytes += b.state_bytes();
    }
    let dense_bytes = SYMBOLS.len() * 16_384;
    println!("  total {sparse_bytes} bytes against {dense_bytes} if every name held a dense array");
    assert!(
        sparse_bytes < dense_bytes,
        "sparse must win on the long tail"
    );
}

/// `union-intersect`: how many accounts trade on both venues? Inclusion-
/// exclusion answers it from two sketches. The error bound is printed next to
/// the answer because it scales with |A| + |B| rather than with the overlap,
/// and an overlap smaller than its own bound is not a number to act on.
#[cfg(feature = "union-intersect")]
fn cross_venue_overlap(tape: &[Event]) {
    use subms_hyperloglog::{estimate_intersect, estimate_union, intersect_error_bound};
    println!("\n== venues: account reach and overlap ==");

    let mut a = HyperLogLog::new(14);
    let mut b = HyperLogLog::new(14);
    for e in tape {
        if e.venue == 0 {
            a.add_u64(e.account);
        } else {
            b.add_u64(e.account);
        }
    }
    let union = estimate_union(&a, &b).expect("same precision");
    let inter = estimate_intersect(&a, &b).expect("same precision");
    let bound = intersect_error_bound(&a, &b).expect("same precision");
    println!("  venue 0: {:>7.0} accounts", a.estimate());
    println!("  venue 1: {:>7.0} accounts", b.estimate());
    println!("  reach:   {union:>7.0} (true 50000)");
    println!("  both:    {inter:>7.0} (true 10000) +/- {bound:.0}");
    assert!(
        (union - 50_000.0).abs() / 50_000.0 < 0.05,
        "reach within 5%, got {union}"
    );
    assert!(inter > 0.0, "a 10k overlap must survive the subtraction");
}

/// `serialize`: each venue ships its sketch, not its account list. The
/// collector decodes and merges, and the firm-wide number falls out of 16 KB
/// per venue instead of a million ids on the wire.
fn collector_fan_in(tape: &[Event]) {
    println!("\n== collector: merge shipped sketches into a firm-wide reach ==");

    let mut per_venue = [HyperLogLog::new(14), HyperLogLog::new(14)];
    for e in tape {
        per_venue[e.venue as usize].add_u64(e.account);
    }
    let shipped: Vec<Vec<u8>> = per_venue.iter().map(|h| h.to_bytes()).collect();
    let on_wire: usize = shipped.iter().map(|b| b.len()).sum();

    let mut firm = HyperLogLog::new(14);
    for bytes in &shipped {
        let decoded = HyperLogLog::from_bytes(bytes).expect("collector reads its own format");
        firm.merge(&decoded).expect("same precision");
    }
    println!(
        "  {} sketches on the wire, {} bytes total",
        shipped.len(),
        on_wire
    );
    println!(
        "  raw ids would have been ~{} bytes",
        tape.len() * core::mem::size_of::<u64>()
    );
    println!("  firm-wide reach: {:.0} (true 50000)", firm.estimate());
    assert!(
        (firm.estimate() - 50_000.0).abs() / 50_000.0 < 0.05,
        "merged reach within 5%"
    );
}

pub fn estimate(&self) -> f64

Estimate distinct count.

Examples found in repository

examples/sample_app.rs (line 106)

fn gateway_sessions(tape: &[Event]) {
    println!("== gateway: distinct sessions this window ==");
    let mut hll = HyperLogLog::new(14);
    let mut first_sightings = 0u64;
    for e in tape {
        if hll.add_u64(e.session) {
            first_sightings += 1;
        }
    }
    let est = hll.estimate();
    println!("  {} messages -> {:.0} distinct sessions", tape.len(), est);
    println!(
        "  {} registers advanced, {} bytes of state, +/- {:.2}% standard error",
        first_sightings,
        hll.state_bytes(),
        hll.standard_error() * 100.0
    );
    assert!(est > 30_000.0 && est < 50_000.0, "~40k sessions, got {est}");
}

/// Sizing runs the other way round in production: you are handed an error
/// budget, not a precision. `precision_for_standard_error` turns the budget
/// into the cheapest register array that meets it.
fn size_from_an_error_budget() {
    println!("\n== sizing: error budget -> byte budget ==");
    for budget in [0.05, 0.02, 0.01, 0.005] {
        let p = HyperLogLog::precision_for_standard_error(budget);
        let hll = HyperLogLog::new(p);
        println!(
            "  budget {:>5.1}%  ->  p={:<2} {:>6} bytes, actual {:.5}%",
            budget * 100.0,
            p,
            hll.state_bytes(),
            hll.standard_error() * 100.0
        );
    }
}

/// `sparse`: risk wants distinct counterparties per symbol. Most of the book is
/// thin, so allocating 16 KB per name would cost 128 KB here and gigabytes
/// across a real universe. The sparse encoding pays only for registers actually
/// touched, and promotes the two busy names once they earn it.
#[cfg(feature = "sparse")]
fn per_symbol_counterparties(tape: &[Event]) {
    use subms_hyperloglog::SparseHyperLogLog;
    println!("\n== risk: distinct counterparties per symbol ==");

    let mut books: Vec<SparseHyperLogLog> = (0..SYMBOLS.len())
        .map(|_| SparseHyperLogLog::with_threshold(14, 2_000))
        .collect();
    for e in tape {
        books[e.symbol].add_u64(e.counterparty);
    }

    let mut sparse_bytes = 0usize;
    for (i, b) in books.iter().enumerate() {
        println!(
            "  {:<5} {:>7.0} counterparties  {:>6} bytes  {}",
            SYMBOLS[i],
            b.estimate(),
            b.state_bytes(),
            if b.is_sparse() { "sparse" } else { "dense" }
        );
        sparse_bytes += b.state_bytes();
    }
    let dense_bytes = SYMBOLS.len() * 16_384;
    println!("  total {sparse_bytes} bytes against {dense_bytes} if every name held a dense array");
    assert!(
        sparse_bytes < dense_bytes,
        "sparse must win on the long tail"
    );
}

/// `union-intersect`: how many accounts trade on both venues? Inclusion-
/// exclusion answers it from two sketches. The error bound is printed next to
/// the answer because it scales with |A| + |B| rather than with the overlap,
/// and an overlap smaller than its own bound is not a number to act on.
#[cfg(feature = "union-intersect")]
fn cross_venue_overlap(tape: &[Event]) {
    use subms_hyperloglog::{estimate_intersect, estimate_union, intersect_error_bound};
    println!("\n== venues: account reach and overlap ==");

    let mut a = HyperLogLog::new(14);
    let mut b = HyperLogLog::new(14);
    for e in tape {
        if e.venue == 0 {
            a.add_u64(e.account);
        } else {
            b.add_u64(e.account);
        }
    }
    let union = estimate_union(&a, &b).expect("same precision");
    let inter = estimate_intersect(&a, &b).expect("same precision");
    let bound = intersect_error_bound(&a, &b).expect("same precision");
    println!("  venue 0: {:>7.0} accounts", a.estimate());
    println!("  venue 1: {:>7.0} accounts", b.estimate());
    println!("  reach:   {union:>7.0} (true 50000)");
    println!("  both:    {inter:>7.0} (true 10000) +/- {bound:.0}");
    assert!(
        (union - 50_000.0).abs() / 50_000.0 < 0.05,
        "reach within 5%, got {union}"
    );
    assert!(inter > 0.0, "a 10k overlap must survive the subtraction");
}

/// `serialize`: each venue ships its sketch, not its account list. The
/// collector decodes and merges, and the firm-wide number falls out of 16 KB
/// per venue instead of a million ids on the wire.
fn collector_fan_in(tape: &[Event]) {
    println!("\n== collector: merge shipped sketches into a firm-wide reach ==");

    let mut per_venue = [HyperLogLog::new(14), HyperLogLog::new(14)];
    for e in tape {
        per_venue[e.venue as usize].add_u64(e.account);
    }
    let shipped: Vec<Vec<u8>> = per_venue.iter().map(|h| h.to_bytes()).collect();
    let on_wire: usize = shipped.iter().map(|b| b.len()).sum();

    let mut firm = HyperLogLog::new(14);
    for bytes in &shipped {
        let decoded = HyperLogLog::from_bytes(bytes).expect("collector reads its own format");
        firm.merge(&decoded).expect("same precision");
    }
    println!(
        "  {} sketches on the wire, {} bytes total",
        shipped.len(),
        on_wire
    );
    println!(
        "  raw ids would have been ~{} bytes",
        tape.len() * core::mem::size_of::<u64>()
    );
    println!("  firm-wide reach: {:.0} (true 50000)", firm.estimate());
    assert!(
        (firm.estimate() - 50_000.0).abs() / 50_000.0 < 0.05,
        "merged reach within 5%"
    );
}

pub fn merge(&mut self, other: &Self) -> Result<(), HllError>

Merge another HLL of the same precision. Element-wise max over registers.

Examples found in repository

examples/sample_app.rs (line 218)

fn collector_fan_in(tape: &[Event]) {
    println!("\n== collector: merge shipped sketches into a firm-wide reach ==");

    let mut per_venue = [HyperLogLog::new(14), HyperLogLog::new(14)];
    for e in tape {
        per_venue[e.venue as usize].add_u64(e.account);
    }
    let shipped: Vec<Vec<u8>> = per_venue.iter().map(|h| h.to_bytes()).collect();
    let on_wire: usize = shipped.iter().map(|b| b.len()).sum();

    let mut firm = HyperLogLog::new(14);
    for bytes in &shipped {
        let decoded = HyperLogLog::from_bytes(bytes).expect("collector reads its own format");
        firm.merge(&decoded).expect("same precision");
    }
    println!(
        "  {} sketches on the wire, {} bytes total",
        shipped.len(),
        on_wire
    );
    println!(
        "  raw ids would have been ~{} bytes",
        tape.len() * core::mem::size_of::<u64>()
    );
    println!("  firm-wide reach: {:.0} (true 50000)", firm.estimate());
    assert!(
        (firm.estimate() - 50_000.0).abs() / 50_000.0 < 0.05,
        "merged reach within 5%"
    );
}

Trait Implementations

impl Clone for HyperLogLog

fn clone(&self) -> HyperLogLog

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for HyperLogLog

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Deliberately does not dump the register array - at p=14 that is 16384 bytes into whatever log caught the assertion.

impl<'de> Deserialize<'de> for HyperLogLog

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for HyperLogLog

fn eq(&self, other: &HyperLogLog) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl Serialize for HyperLogLog

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl StructuralPartialEq for HyperLogLog