Struct DynamicCuckooFilter 

pub struct DynamicCuckooFilter { /* private fields */ }

Implementations

impl DynamicCuckooFilter

pub fn new(initial_capacity: usize) -> Self

Build a dynamic cuckoo filter starting sized for initial_capacity entries. Auto-grows at 95% load.

Examples found in repository

examples/perf_features.rs (line 157)

fn main() -> io::Result<()> {
    let canon = SIZES[SIZES.len() - 1];
    let canon_keys = keys(canon);

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

    // ---------- base: the baseline, not a feature ----------
    // Every feature is classified against this. A variant whose lookup lands at
    // or under the base costs nothing on the hot path, and classify_feature says
    // so rather than calling it hot-path by default.
    let base_p50 = {
        let mut f = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            f.insert(k);
        }
        let (p50, _) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        p50
    };

    // ---------- variable-fingerprint: wider tag, lower FPR ----------
    #[cfg(feature = "variable-fingerprint")]
    {
        use subms_cuckoo_filter::{FingerprintWidth, VariableFpCuckooFilter};
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = VariableFpCuckooFilter::new(n, FingerprintWidth::Sixteen);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = VariableFpCuckooFilter::new(canon, FingerprintWidth::Sixteen);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("variable-fingerprint", cat, &p99, &reason);
    }

    // ---------- dynamic: grows rather than refusing at load factor ----------
    #[cfg(feature = "dynamic")]
    {
        use subms_cuckoo_filter::DynamicCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = DynamicCuckooFilter::new(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = DynamicCuckooFilter::new(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("dynamic", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a frozen snapshot readers share ----------
    // Classified on the SNAPSHOT, not the lookup. The snapshot is a whole-table
    // copy whose cost is the thing that scales; the lookups against it are
    // per-op and would classify the same as any other read.
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_cuckoo_filter::CuckooSnapshot;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut src = CuckooFilter::with_capacity(n);
                for k in &ks {
                    src.insert(k);
                }
                // Several samples, not one. A single timed capture at the
                // SMALLEST size absorbs the first-touch allocation cost, which
                // inflates the low end of the sweep and flattens the very ratio
                // the scaling test reads - a whole-table copy then classifies
                // hot-path, which is exactly backwards.
                for _ in 0..SNAPSHOT_WARM {
                    let _ = CuckooSnapshot::capture(&src);
                }
                let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
                {
                    let st = h.stage("op", SNAPSHOT_REPS);
                    for _ in 0..SNAPSHOT_REPS {
                        st.time(|| {
                            let _ = CuckooSnapshot::capture(&src);
                        });
                    }
                }
                let (p50, _) = stage_stats(&h, "op");
                (n, p50)
            })
            .collect();
        // PINNED structural, not measured. `CuckooSnapshot::capture` is a
        // `to_vec()` of the whole bucket array - unambiguously O(N) from the
        // source - but this sweep cannot demonstrate it on a dev box: even with
        // warmup discarded the smallest size measures ~7us against ~3us at 8x
        // the size, a non-monotonic curve whose min/max ratio reads ~2x over a
        // 64x size range, so the scaling test calls it flat and an O(N) memcpy
        // classifies hot-path. Recording that would be a false claim about the
        // one op on this page that genuinely is not per-op, so the category is
        // pinned and `perfReason` says it was overridden rather than measured.
        // Revisit on a fleet capture, where the curve should separate.
        //
        // No base comparison either: a whole-table copy is not the same kind of
        // operation as a per-key lookup, so a delta against it means nothing.
        let (cat, reason) =
            classify_feature(&sweep, None, Some(subms::SubMsFeatureCategory::Structural));

        let mut src = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            src.insert(k);
        }
        for _ in 0..SNAPSHOT_WARM {
            let _ = CuckooSnapshot::capture(&src);
        }
        let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
        let snap = {
            let st = h.stage("op", SNAPSHOT_REPS);
            for _ in 0..SNAPSHOT_REPS - 1 {
                st.time(|| {
                    let _ = CuckooSnapshot::capture(&src);
                });
            }
            st.time(|| CuckooSnapshot::capture(&src))
        };
        let (_, snap99) = stage_stats(&h, "op");
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = snap.contains(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("snapshot".to_string(), snap99);
        p99.insert("lookup_on_snapshot".to_string(), lookup99);
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    // ---------- compressed-buckets: tighter memory per bucket ----------
    #[cfg(feature = "compressed-buckets")]
    {
        use subms_cuckoo_filter::CompressedCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = CompressedCuckooFilter::with_capacity(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = CompressedCuckooFilter::with_capacity(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("compressed-buckets", 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(initial_capacity: usize, grow_threshold: f64) -> Self

Build with a custom grow threshold in (0.0, 1.0). Lower thresholds grow earlier (more layers, lower per-layer pressure); higher thresholds delay growth at the cost of risk-of-rejection.

Examples found in repository

examples/sample_app.rs (line 208)

fn dynamic_dedup_window() {
    use subms_cuckoo_filter::DynamicCuckooFilter;
    println!("\n== dynamic: an intraday dedup window that grows itself ==");
    let mut seen = DynamicCuckooFilter::with_threshold(1_000, 0.5);
    for i in 0..20_000u32 {
        seen.insert(&format!("MSG-{i}"));
    }
    println!(
        "  20k ids -> {} layers, active load {:.2}",
        seen.layer_count(),
        seen.load_factor()
    );
    assert!(
        seen.layer_count() > 1,
        "the window grew past its initial sizing"
    );
    for i in 0..20_000u32 {
        assert!(
            seen.contains(&format!("MSG-{i}")),
            "no id dropped as the window grew"
        );
    }
}

pub fn layer_count(&self) -> usize

Examples found in repository

examples/sample_app.rs (line 214)

fn dynamic_dedup_window() {
    use subms_cuckoo_filter::DynamicCuckooFilter;
    println!("\n== dynamic: an intraday dedup window that grows itself ==");
    let mut seen = DynamicCuckooFilter::with_threshold(1_000, 0.5);
    for i in 0..20_000u32 {
        seen.insert(&format!("MSG-{i}"));
    }
    println!(
        "  20k ids -> {} layers, active load {:.2}",
        seen.layer_count(),
        seen.load_factor()
    );
    assert!(
        seen.layer_count() > 1,
        "the window grew past its initial sizing"
    );
    for i in 0..20_000u32 {
        assert!(
            seen.contains(&format!("MSG-{i}")),
            "no id dropped as the window grew"
        );
    }
}

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

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

Insert a key into the active layer. Grows if the active layer crosses the load threshold OR rejects the insert outright.

Examples found in repository

examples/sample_app.rs (line 210)

fn dynamic_dedup_window() {
    use subms_cuckoo_filter::DynamicCuckooFilter;
    println!("\n== dynamic: an intraday dedup window that grows itself ==");
    let mut seen = DynamicCuckooFilter::with_threshold(1_000, 0.5);
    for i in 0..20_000u32 {
        seen.insert(&format!("MSG-{i}"));
    }
    println!(
        "  20k ids -> {} layers, active load {:.2}",
        seen.layer_count(),
        seen.load_factor()
    );
    assert!(
        seen.layer_count() > 1,
        "the window grew past its initial sizing"
    );
    for i in 0..20_000u32 {
        assert!(
            seen.contains(&format!("MSG-{i}")),
            "no id dropped as the window grew"
        );
    }
}

examples/perf_features.rs (line 159)

fn main() -> io::Result<()> {
    let canon = SIZES[SIZES.len() - 1];
    let canon_keys = keys(canon);

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

    // ---------- base: the baseline, not a feature ----------
    // Every feature is classified against this. A variant whose lookup lands at
    // or under the base costs nothing on the hot path, and classify_feature says
    // so rather than calling it hot-path by default.
    let base_p50 = {
        let mut f = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            f.insert(k);
        }
        let (p50, _) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        p50
    };

    // ---------- variable-fingerprint: wider tag, lower FPR ----------
    #[cfg(feature = "variable-fingerprint")]
    {
        use subms_cuckoo_filter::{FingerprintWidth, VariableFpCuckooFilter};
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = VariableFpCuckooFilter::new(n, FingerprintWidth::Sixteen);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = VariableFpCuckooFilter::new(canon, FingerprintWidth::Sixteen);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("variable-fingerprint", cat, &p99, &reason);
    }

    // ---------- dynamic: grows rather than refusing at load factor ----------
    #[cfg(feature = "dynamic")]
    {
        use subms_cuckoo_filter::DynamicCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = DynamicCuckooFilter::new(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = DynamicCuckooFilter::new(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("dynamic", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a frozen snapshot readers share ----------
    // Classified on the SNAPSHOT, not the lookup. The snapshot is a whole-table
    // copy whose cost is the thing that scales; the lookups against it are
    // per-op and would classify the same as any other read.
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_cuckoo_filter::CuckooSnapshot;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut src = CuckooFilter::with_capacity(n);
                for k in &ks {
                    src.insert(k);
                }
                // Several samples, not one. A single timed capture at the
                // SMALLEST size absorbs the first-touch allocation cost, which
                // inflates the low end of the sweep and flattens the very ratio
                // the scaling test reads - a whole-table copy then classifies
                // hot-path, which is exactly backwards.
                for _ in 0..SNAPSHOT_WARM {
                    let _ = CuckooSnapshot::capture(&src);
                }
                let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
                {
                    let st = h.stage("op", SNAPSHOT_REPS);
                    for _ in 0..SNAPSHOT_REPS {
                        st.time(|| {
                            let _ = CuckooSnapshot::capture(&src);
                        });
                    }
                }
                let (p50, _) = stage_stats(&h, "op");
                (n, p50)
            })
            .collect();
        // PINNED structural, not measured. `CuckooSnapshot::capture` is a
        // `to_vec()` of the whole bucket array - unambiguously O(N) from the
        // source - but this sweep cannot demonstrate it on a dev box: even with
        // warmup discarded the smallest size measures ~7us against ~3us at 8x
        // the size, a non-monotonic curve whose min/max ratio reads ~2x over a
        // 64x size range, so the scaling test calls it flat and an O(N) memcpy
        // classifies hot-path. Recording that would be a false claim about the
        // one op on this page that genuinely is not per-op, so the category is
        // pinned and `perfReason` says it was overridden rather than measured.
        // Revisit on a fleet capture, where the curve should separate.
        //
        // No base comparison either: a whole-table copy is not the same kind of
        // operation as a per-key lookup, so a delta against it means nothing.
        let (cat, reason) =
            classify_feature(&sweep, None, Some(subms::SubMsFeatureCategory::Structural));

        let mut src = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            src.insert(k);
        }
        for _ in 0..SNAPSHOT_WARM {
            let _ = CuckooSnapshot::capture(&src);
        }
        let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
        let snap = {
            let st = h.stage("op", SNAPSHOT_REPS);
            for _ in 0..SNAPSHOT_REPS - 1 {
                st.time(|| {
                    let _ = CuckooSnapshot::capture(&src);
                });
            }
            st.time(|| CuckooSnapshot::capture(&src))
        };
        let (_, snap99) = stage_stats(&h, "op");
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = snap.contains(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("snapshot".to_string(), snap99);
        p99.insert("lookup_on_snapshot".to_string(), lookup99);
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    // ---------- compressed-buckets: tighter memory per bucket ----------
    #[cfg(feature = "compressed-buckets")]
    {
        use subms_cuckoo_filter::CompressedCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = CompressedCuckooFilter::with_capacity(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = CompressedCuckooFilter::with_capacity(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("compressed-buckets", 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 contains(&self, key: &str) -> bool

Membership over every layer. False positives possible (same FPR model as the base; cumulative FPR is bounded by sum across layers but typically dominated by the active layer).

Examples found in repository

examples/sample_app.rs (line 223)

fn dynamic_dedup_window() {
    use subms_cuckoo_filter::DynamicCuckooFilter;
    println!("\n== dynamic: an intraday dedup window that grows itself ==");
    let mut seen = DynamicCuckooFilter::with_threshold(1_000, 0.5);
    for i in 0..20_000u32 {
        seen.insert(&format!("MSG-{i}"));
    }
    println!(
        "  20k ids -> {} layers, active load {:.2}",
        seen.layer_count(),
        seen.load_factor()
    );
    assert!(
        seen.layer_count() > 1,
        "the window grew past its initial sizing"
    );
    for i in 0..20_000u32 {
        assert!(
            seen.contains(&format!("MSG-{i}")),
            "no id dropped as the window grew"
        );
    }
}

examples/perf_features.rs (line 162)

fn main() -> io::Result<()> {
    let canon = SIZES[SIZES.len() - 1];
    let canon_keys = keys(canon);

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

    // ---------- base: the baseline, not a feature ----------
    // Every feature is classified against this. A variant whose lookup lands at
    // or under the base costs nothing on the hot path, and classify_feature says
    // so rather than calling it hot-path by default.
    let base_p50 = {
        let mut f = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            f.insert(k);
        }
        let (p50, _) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        p50
    };

    // ---------- variable-fingerprint: wider tag, lower FPR ----------
    #[cfg(feature = "variable-fingerprint")]
    {
        use subms_cuckoo_filter::{FingerprintWidth, VariableFpCuckooFilter};
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = VariableFpCuckooFilter::new(n, FingerprintWidth::Sixteen);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = VariableFpCuckooFilter::new(canon, FingerprintWidth::Sixteen);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("variable-fingerprint", cat, &p99, &reason);
    }

    // ---------- dynamic: grows rather than refusing at load factor ----------
    #[cfg(feature = "dynamic")]
    {
        use subms_cuckoo_filter::DynamicCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = DynamicCuckooFilter::new(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = DynamicCuckooFilter::new(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("dynamic", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a frozen snapshot readers share ----------
    // Classified on the SNAPSHOT, not the lookup. The snapshot is a whole-table
    // copy whose cost is the thing that scales; the lookups against it are
    // per-op and would classify the same as any other read.
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_cuckoo_filter::CuckooSnapshot;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut src = CuckooFilter::with_capacity(n);
                for k in &ks {
                    src.insert(k);
                }
                // Several samples, not one. A single timed capture at the
                // SMALLEST size absorbs the first-touch allocation cost, which
                // inflates the low end of the sweep and flattens the very ratio
                // the scaling test reads - a whole-table copy then classifies
                // hot-path, which is exactly backwards.
                for _ in 0..SNAPSHOT_WARM {
                    let _ = CuckooSnapshot::capture(&src);
                }
                let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
                {
                    let st = h.stage("op", SNAPSHOT_REPS);
                    for _ in 0..SNAPSHOT_REPS {
                        st.time(|| {
                            let _ = CuckooSnapshot::capture(&src);
                        });
                    }
                }
                let (p50, _) = stage_stats(&h, "op");
                (n, p50)
            })
            .collect();
        // PINNED structural, not measured. `CuckooSnapshot::capture` is a
        // `to_vec()` of the whole bucket array - unambiguously O(N) from the
        // source - but this sweep cannot demonstrate it on a dev box: even with
        // warmup discarded the smallest size measures ~7us against ~3us at 8x
        // the size, a non-monotonic curve whose min/max ratio reads ~2x over a
        // 64x size range, so the scaling test calls it flat and an O(N) memcpy
        // classifies hot-path. Recording that would be a false claim about the
        // one op on this page that genuinely is not per-op, so the category is
        // pinned and `perfReason` says it was overridden rather than measured.
        // Revisit on a fleet capture, where the curve should separate.
        //
        // No base comparison either: a whole-table copy is not the same kind of
        // operation as a per-key lookup, so a delta against it means nothing.
        let (cat, reason) =
            classify_feature(&sweep, None, Some(subms::SubMsFeatureCategory::Structural));

        let mut src = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            src.insert(k);
        }
        for _ in 0..SNAPSHOT_WARM {
            let _ = CuckooSnapshot::capture(&src);
        }
        let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
        let snap = {
            let st = h.stage("op", SNAPSHOT_REPS);
            for _ in 0..SNAPSHOT_REPS - 1 {
                st.time(|| {
                    let _ = CuckooSnapshot::capture(&src);
                });
            }
            st.time(|| CuckooSnapshot::capture(&src))
        };
        let (_, snap99) = stage_stats(&h, "op");
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = snap.contains(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("snapshot".to_string(), snap99);
        p99.insert("lookup_on_snapshot".to_string(), lookup99);
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    // ---------- compressed-buckets: tighter memory per bucket ----------
    #[cfg(feature = "compressed-buckets")]
    {
        use subms_cuckoo_filter::CompressedCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = CompressedCuckooFilter::with_capacity(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = CompressedCuckooFilter::with_capacity(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("compressed-buckets", 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 delete(&mut self, key: &str) -> bool

Delete a single occurrence. Probes newest-first so duplicate keys are removed in reverse insertion order.

Examples found in repository

examples/perf_features.rs (line 177)

fn main() -> io::Result<()> {
    let canon = SIZES[SIZES.len() - 1];
    let canon_keys = keys(canon);

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

    // ---------- base: the baseline, not a feature ----------
    // Every feature is classified against this. A variant whose lookup lands at
    // or under the base costs nothing on the hot path, and classify_feature says
    // so rather than calling it hot-path by default.
    let base_p50 = {
        let mut f = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            f.insert(k);
        }
        let (p50, _) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        p50
    };

    // ---------- variable-fingerprint: wider tag, lower FPR ----------
    #[cfg(feature = "variable-fingerprint")]
    {
        use subms_cuckoo_filter::{FingerprintWidth, VariableFpCuckooFilter};
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = VariableFpCuckooFilter::new(n, FingerprintWidth::Sixteen);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = VariableFpCuckooFilter::new(canon, FingerprintWidth::Sixteen);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("variable-fingerprint", cat, &p99, &reason);
    }

    // ---------- dynamic: grows rather than refusing at load factor ----------
    #[cfg(feature = "dynamic")]
    {
        use subms_cuckoo_filter::DynamicCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = DynamicCuckooFilter::new(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = DynamicCuckooFilter::new(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("dynamic", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a frozen snapshot readers share ----------
    // Classified on the SNAPSHOT, not the lookup. The snapshot is a whole-table
    // copy whose cost is the thing that scales; the lookups against it are
    // per-op and would classify the same as any other read.
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_cuckoo_filter::CuckooSnapshot;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut src = CuckooFilter::with_capacity(n);
                for k in &ks {
                    src.insert(k);
                }
                // Several samples, not one. A single timed capture at the
                // SMALLEST size absorbs the first-touch allocation cost, which
                // inflates the low end of the sweep and flattens the very ratio
                // the scaling test reads - a whole-table copy then classifies
                // hot-path, which is exactly backwards.
                for _ in 0..SNAPSHOT_WARM {
                    let _ = CuckooSnapshot::capture(&src);
                }
                let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
                {
                    let st = h.stage("op", SNAPSHOT_REPS);
                    for _ in 0..SNAPSHOT_REPS {
                        st.time(|| {
                            let _ = CuckooSnapshot::capture(&src);
                        });
                    }
                }
                let (p50, _) = stage_stats(&h, "op");
                (n, p50)
            })
            .collect();
        // PINNED structural, not measured. `CuckooSnapshot::capture` is a
        // `to_vec()` of the whole bucket array - unambiguously O(N) from the
        // source - but this sweep cannot demonstrate it on a dev box: even with
        // warmup discarded the smallest size measures ~7us against ~3us at 8x
        // the size, a non-monotonic curve whose min/max ratio reads ~2x over a
        // 64x size range, so the scaling test calls it flat and an O(N) memcpy
        // classifies hot-path. Recording that would be a false claim about the
        // one op on this page that genuinely is not per-op, so the category is
        // pinned and `perfReason` says it was overridden rather than measured.
        // Revisit on a fleet capture, where the curve should separate.
        //
        // No base comparison either: a whole-table copy is not the same kind of
        // operation as a per-key lookup, so a delta against it means nothing.
        let (cat, reason) =
            classify_feature(&sweep, None, Some(subms::SubMsFeatureCategory::Structural));

        let mut src = CuckooFilter::with_capacity(canon);
        for k in &canon_keys {
            src.insert(k);
        }
        for _ in 0..SNAPSHOT_WARM {
            let _ = CuckooSnapshot::capture(&src);
        }
        let mut h = SubMsPerfHarness::new("cuckoo-feature", "rust");
        let snap = {
            let st = h.stage("op", SNAPSHOT_REPS);
            for _ in 0..SNAPSHOT_REPS - 1 {
                st.time(|| {
                    let _ = CuckooSnapshot::capture(&src);
                });
            }
            st.time(|| CuckooSnapshot::capture(&src))
        };
        let (_, snap99) = stage_stats(&h, "op");
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = snap.contains(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("snapshot".to_string(), snap99);
        p99.insert("lookup_on_snapshot".to_string(), lookup99);
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    // ---------- compressed-buckets: tighter memory per bucket ----------
    #[cfg(feature = "compressed-buckets")]
    {
        use subms_cuckoo_filter::CompressedCuckooFilter;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let ks = keys(n);
                let mut f = CompressedCuckooFilter::with_capacity(n);
                for k in &ks {
                    f.insert(k);
                }
                let (p50, _) = keyed(&ks, |k| {
                    let _ = f.contains(k);
                });
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut f = CompressedCuckooFilter::with_capacity(canon);
        let (_, insert99) = keyed(&canon_keys, |k| {
            f.insert(k);
        });
        let (_, lookup99) = keyed(&canon_keys, |k| {
            let _ = f.contains(k);
        });
        let (_, delete99) = keyed(&canon_keys, |k| {
            f.delete(k);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("insert".to_string(), insert99);
        p99.insert("lookup".to_string(), lookup99);
        p99.insert("delete".to_string(), delete99);
        manifest.set_feature("compressed-buckets", 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 load_factor(&self) -> f64

Examples found in repository

examples/sample_app.rs (line 215)

fn dynamic_dedup_window() {
    use subms_cuckoo_filter::DynamicCuckooFilter;
    println!("\n== dynamic: an intraday dedup window that grows itself ==");
    let mut seen = DynamicCuckooFilter::with_threshold(1_000, 0.5);
    for i in 0..20_000u32 {
        seen.insert(&format!("MSG-{i}"));
    }
    println!(
        "  20k ids -> {} layers, active load {:.2}",
        seen.layer_count(),
        seen.load_factor()
    );
    assert!(
        seen.layer_count() > 1,
        "the window grew past its initial sizing"
    );
    for i in 0..20_000u32 {
        assert!(
            seen.contains(&format!("MSG-{i}")),
            "no id dropped as the window grew"
        );
    }
}