Function estimate_intersect 

pub fn estimate_intersect(
    a: &HyperLogLog,
    b: &HyperLogLog,
) -> Result<f64, HllError>

Distinct count of the intersection via inclusion-exclusion. Clamps to >= 0 since a negative estimate is a hard signal of large relative error.

Examples found in repository

examples/sample_app.rs (line 189)

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

examples/perf_features.rs (line 261)

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(())
}