Struct SparseHyperLogLog 

pub struct SparseHyperLogLog { /* private fields */ }

HyperLogLog variant that holds a compact (idx, rho) pair list at low cardinality and promotes to a dense register array once the list grows past a threshold.

Single-writer, same as the base type: add, merge, clear and promote take &mut self.

Implementations

impl SparseHyperLogLog

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

Serialise in whichever representation the sketch currently holds. A thin sketch stays thin on the wire; a promoted one writes the same dense buffer HyperLogLog::to_bytes would.

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

Parse either encoding. A dense buffer comes back as an already-promoted sketch, which is the honest reading: the writer had crossed the threshold and the reader inherits that.

impl SparseHyperLogLog

pub fn new(precision: u32) -> Self

New empty sparse-mode HLL at precision p (clamped to [4, 18]) and default threshold m / 4.

m/4 is a round heuristic and it overshoots: at five bytes an entry the pair list reaches the dense array’s byte cost at m/5, so between m/5 and m/4 a sparse sketch is both bigger and slower to probe. Pass with_threshold(p, m / 5) when bytes are what you are buying.

Examples found in repository

examples/perf_features.rs (line 190)

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 with_threshold(precision: u32, threshold: usize) -> Self

Explicit promotion threshold (in distinct register entries). Use this when you know the workload’s cardinality envelope and want to delay or hasten the dense crossover.

Examples found in repository

examples/sample_app.rs (line 145)

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"
    );
}

examples/perf_features.rs (line 164)

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 precision(&self) -> u32

pub fn register_count(&self) -> u32

pub fn is_sparse(&self) -> bool

Examples found in repository

examples/sample_app.rs (line 158)

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"
    );
}

pub fn threshold(&self) -> usize

Entry count at which this sketch promotes to dense.

pub fn standard_error(&self) -> f64

Analytic relative standard error once dense, 1.04 / sqrt(m). Sparse mode is tighter than this because linear counting over a mostly-empty register space is the accurate estimator down there; the number is the envelope the sketch converges to, not a bound on its current state.

pub fn state_bytes(&self) -> usize

Payload cost of the representation, register array or pair list. This is the number the feature exists to move: at p=14 an untouched sparse sketch is a fraction of the dense 16384 bytes.

Five bytes per entry, matching the wire encoding rather than the allocator - a Vec<(u32, u8)> pads each pair to eight and Java’s two parallel arrays do not, so a layout-exact number would disagree across the ports for no useful reason.

Examples found in repository

examples/sample_app.rs (line 157)

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"
    );
}

pub fn is_empty(&self) -> bool

True while nothing has been recorded.

pub fn clear(&mut self)

Reset to an empty sparse sketch, dropping the dense array if we had promoted. The threshold survives; a reused sketch keeps its sizing.

pub fn entry_count(&self) -> usize

Distinct register entries currently held. Once promoted to dense the answer is the count of non-zero registers.

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

Record a key. Returns true when the sketch changed. If we’re sparse and the new entry pushes us past the threshold, promote to dense before returning.

Examples found in repository

examples/perf_features.rs (line 166)

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_u64(&mut self, key: u64) -> bool

Record a 64-bit id without rendering it to a string.

Examples found in repository

examples/sample_app.rs (line 148)

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"
    );
}

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

Record raw bytes.

pub fn estimate(&self) -> f64

Estimate distinct count. In sparse mode the registers we don’t hold are zero, so linear counting is exact under the HLL assumption that absent registers contribute log term -m * ln(1) = 0. We use the base HLL formula uniformly for consistency.

Examples found in repository

examples/sample_app.rs (line 156)

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"
    );
}

examples/perf_features.rs (line 208)

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 merge(&mut self, other: &Self) -> Result<(), HllError>

Merge another sparse sketch of the same precision. Two sparse lists combine entry-wise and may cross the threshold on the way, in which case the result promotes. Once either side is dense the merge runs on dense registers, which is where a fan-in of many shards ends up.

pub fn promote(&mut self)

Force promotion to dense even if below the threshold. Useful for benchmarking or for handing the inner dense HLL to a peer that does not understand sparse mode.

pub fn as_dense(&self) -> Option<&HyperLogLog>

View into the dense HLL after promotion. None while sparse.

pub fn to_dense(&self) -> HyperLogLog

Materialise a dense copy without mutating this sketch. The bridge to estimate_union / estimate_intersect, which only take base sketches.

Trait Implementations

impl Clone for SparseHyperLogLog

fn clone(&self) -> SparseHyperLogLog

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseHyperLogLog

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SparseHyperLogLog

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Serialize for SparseHyperLogLog

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

where __S: Serializer,

Serialize this value into the given Serde serializer.