Struct BlockCache 

pub struct BlockCache<K, V> { /* private fields */ }

Implementations

impl<K: Hash + Eq + Clone, V> BlockCache<K, V>

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository

examples/growth_main.rs (line 103)

fn main() -> ExitCode {
    let mut raw = String::new();
    if io::stdin().read_to_string(&mut raw).is_err() {
        eprintln!("growth_main: failed to read stdin");
        return ExitCode::FAILURE;
    }
    let mut map = BTreeMap::new();
    for line in raw.lines() {
        let line = line.trim();
        if line.is_empty() || line.starts_with('#') {
            continue;
        }
        if let Some((k, v)) = line.split_once('=') {
            map.insert(k.trim().to_string(), v.trim().to_string());
        }
    }
    let rounds = parse_usize(&map, "rounds", 50);
    let capacity = parse_usize(&map, "capacity", 1024);
    let inserts_per_round = parse_usize(&map, "inserts_per_round", 20_000);

    let mut recipe = CacheChurn {
        cache: BlockCache::with_capacity(capacity),
        capacity,
        rounds,
        inserts_per_round,
        value: vec![0u8; VALUE_BYTES],
        next: 0,
    };
    let report = grow(&mut recipe, "rust");

    if growth_to_json(&report, &mut io::stdout().lock()).is_err() {
        eprintln!("growth_main: failed to write json");
        return ExitCode::FAILURE;
    }
    ExitCode::SUCCESS
}

examples/sample_app.rs (line 49)

fn base_page_cache() {
    println!("== base: block cache in front of a cold columnar store ==");
    const CAP: usize = 4;
    let mut cache: BlockCache<u64, String> = BlockCache::with_capacity(CAP);

    let hot = [100u64, 101, 102, 103];
    let mut cold_reads = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_none(), "cold on first touch");
        cache.put(id, read_block(id));
        cold_reads += 1;
    }
    println!("  warmed {} pages, {cold_reads} cold reads", cache.len());
    assert_eq!(cache.len(), CAP);

    let mut served = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_some(), "resident page must never miss");
        served += 1;
    }
    println!("  re-read the hot set: {served} served, 0 cold reads");
    assert_eq!(served, CAP);

    let (victim, _) = cache
        .put(200, read_block(200))
        .expect("full cache must evict to admit a new page");
    println!("  admitted page 200, evicted page {victim}");
    assert_eq!(cache.len(), CAP, "capacity is a hard bound");

    // A compaction rewrote page 200, so the cached copy is stale. Invalidate
    // it rather than waiting for the hand to come round.
    assert!(cache.remove(&200).is_some(), "stale page must be dropped");
    println!("  invalidated page 200, {} pages resident", cache.len());
    cache.clear();
    assert!(cache.is_empty(), "clear drops the whole segment");
    println!("  segment dropped, cache empty, capacity still {CAP}");
}

examples/perf_features.rs (line 108)

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

    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 (clock-sweep): the baseline, not a feature ----------
    // Every feature is classified against this. A variant whose lookup lands
    // within a whisker of the base is a capability, not a latency change, and
    // classify_feature says so rather than calling it hot-path by default.
    // The baseline is a p50, because the sweep values are p50s. Handing
    // classify_feature a base p99 against p50 sweep points compares two
    // different statistics: the p50 sits below the p99 almost by construction,
    // so every feature reads as "within 10% of base" and lands auxiliary.
    let base_p50 = {
        use subms_block_cache::BlockCache;
        let mut c: BlockCache<u32, u64> = BlockCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (p50, _) = get_hit(canon, |key| c.get(&key).is_some());
        p50
    };

    // ---------- arc: adaptive replacement, recency + frequency lists ----------
    #[cfg(feature = "arc")]
    {
        use subms_block_cache::ArcCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: ArcCache<u32, u64> = ArcCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: ArcCache<u32, u64> = ArcCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("arc", cat, &p99, &reason);
    }

    // ---------- tinylfu: frequency-sketch admission ----------
    #[cfg(feature = "tinylfu")]
    {
        use subms_block_cache::TinyLfuCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: TinyLfuCache<u32, u64> = TinyLfuCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: TinyLfuCache<u32, u64> = TinyLfuCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("tinylfu", cat, &p99, &reason);
    }

    // ---------- weighted: a byte budget rather than a slot count ----------
    #[cfg(feature = "weighted")]
    {
        use subms_block_cache::WeightedCache;
        // 1 byte per entry so capacity_bytes == slot capacity; eviction behaves
        // like the base cache, which isolates the weight bookkeeping itself.
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: WeightedCache<u32, u64> =
                    WeightedCache::with_capacity_bytes(n, |_v: &u64| 1);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: WeightedCache<u32, u64> =
            WeightedCache::with_capacity_bytes(canon, |_v: &u64| 1);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            let _ = c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("weighted", cat, &p99, &reason);
    }

    // ---------- concurrent-shards: measured single-threaded ----------
    // Uncontended on purpose. This isolates the sharding INDIRECTION from the
    // contention it exists to relieve; a multi-threaded number here would say
    // more about the thread count than about the feature.
    #[cfg(feature = "concurrent-shards")]
    {
        use subms_block_cache::ShardedCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let c: ShardedCache<u32, u64> = ShardedCache::with_capacity(n, 16);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let c: ShardedCache<u32, u64> = ShardedCache::with_capacity(canon, 16);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("concurrent-shards", cat, &p99, &reason);
    }

    // ---------- metrics: hit/miss counters on the lookup path ----------
    #[cfg(feature = "metrics")]
    {
        use subms_block_cache::MetricsCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: MetricsCache<u32, u64> = MetricsCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: MetricsCache<u32, u64> = MetricsCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("metrics", 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 capacity(&self) -> usize

pub fn len(&self) -> usize

Examples found in repository

examples/growth_main.rs (line 56)

    fn memory_bytes(&mut self) -> u64 {
        self.cache.len() as u64 * ENTRY_BYTES
    }
    fn live_bytes(&mut self) -> u64 {
        // A cache holds only live entries, so resident == live: amplification 1x
        // is the healthy shape (every resident byte is one the cache chose to keep).
        self.cache.len() as u64 * ENTRY_BYTES
    }
    fn structures(&mut self) -> Vec<(String, u64)> {
        vec![("entries".to_string(), self.cache.len() as u64)]
    }

examples/sample_app.rs (line 58)

fn base_page_cache() {
    println!("== base: block cache in front of a cold columnar store ==");
    const CAP: usize = 4;
    let mut cache: BlockCache<u64, String> = BlockCache::with_capacity(CAP);

    let hot = [100u64, 101, 102, 103];
    let mut cold_reads = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_none(), "cold on first touch");
        cache.put(id, read_block(id));
        cold_reads += 1;
    }
    println!("  warmed {} pages, {cold_reads} cold reads", cache.len());
    assert_eq!(cache.len(), CAP);

    let mut served = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_some(), "resident page must never miss");
        served += 1;
    }
    println!("  re-read the hot set: {served} served, 0 cold reads");
    assert_eq!(served, CAP);

    let (victim, _) = cache
        .put(200, read_block(200))
        .expect("full cache must evict to admit a new page");
    println!("  admitted page 200, evicted page {victim}");
    assert_eq!(cache.len(), CAP, "capacity is a hard bound");

    // A compaction rewrote page 200, so the cached copy is stale. Invalidate
    // it rather than waiting for the hand to come round.
    assert!(cache.remove(&200).is_some(), "stale page must be dropped");
    println!("  invalidated page 200, {} pages resident", cache.len());
    cache.clear();
    assert!(cache.is_empty(), "clear drops the whole segment");
    println!("  segment dropped, cache empty, capacity still {CAP}");
}

pub fn is_empty(&self) -> bool

Examples found in repository

examples/sample_app.rs (line 80)

fn base_page_cache() {
    println!("== base: block cache in front of a cold columnar store ==");
    const CAP: usize = 4;
    let mut cache: BlockCache<u64, String> = BlockCache::with_capacity(CAP);

    let hot = [100u64, 101, 102, 103];
    let mut cold_reads = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_none(), "cold on first touch");
        cache.put(id, read_block(id));
        cold_reads += 1;
    }
    println!("  warmed {} pages, {cold_reads} cold reads", cache.len());
    assert_eq!(cache.len(), CAP);

    let mut served = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_some(), "resident page must never miss");
        served += 1;
    }
    println!("  re-read the hot set: {served} served, 0 cold reads");
    assert_eq!(served, CAP);

    let (victim, _) = cache
        .put(200, read_block(200))
        .expect("full cache must evict to admit a new page");
    println!("  admitted page 200, evicted page {victim}");
    assert_eq!(cache.len(), CAP, "capacity is a hard bound");

    // A compaction rewrote page 200, so the cached copy is stale. Invalidate
    // it rather than waiting for the hand to come round.
    assert!(cache.remove(&200).is_some(), "stale page must be dropped");
    println!("  invalidated page 200, {} pages resident", cache.len());
    cache.clear();
    assert!(cache.is_empty(), "clear drops the whole segment");
    println!("  segment dropped, cache empty, capacity still {CAP}");
}

pub fn get(&mut self, key: &K) -> Option<&V>

Get a reference to the value for key, marking the slot referenced for the clock sweep.

Examples found in repository

examples/sample_app.rs (line 54)

fn base_page_cache() {
    println!("== base: block cache in front of a cold columnar store ==");
    const CAP: usize = 4;
    let mut cache: BlockCache<u64, String> = BlockCache::with_capacity(CAP);

    let hot = [100u64, 101, 102, 103];
    let mut cold_reads = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_none(), "cold on first touch");
        cache.put(id, read_block(id));
        cold_reads += 1;
    }
    println!("  warmed {} pages, {cold_reads} cold reads", cache.len());
    assert_eq!(cache.len(), CAP);

    let mut served = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_some(), "resident page must never miss");
        served += 1;
    }
    println!("  re-read the hot set: {served} served, 0 cold reads");
    assert_eq!(served, CAP);

    let (victim, _) = cache
        .put(200, read_block(200))
        .expect("full cache must evict to admit a new page");
    println!("  admitted page 200, evicted page {victim}");
    assert_eq!(cache.len(), CAP, "capacity is a hard bound");

    // A compaction rewrote page 200, so the cached copy is stale. Invalidate
    // it rather than waiting for the hand to come round.
    assert!(cache.remove(&200).is_some(), "stale page must be dropped");
    println!("  invalidated page 200, {} pages resident", cache.len());
    cache.clear();
    assert!(cache.is_empty(), "clear drops the whole segment");
    println!("  segment dropped, cache empty, capacity still {CAP}");
}

examples/perf_features.rs (line 112)

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

    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 (clock-sweep): the baseline, not a feature ----------
    // Every feature is classified against this. A variant whose lookup lands
    // within a whisker of the base is a capability, not a latency change, and
    // classify_feature says so rather than calling it hot-path by default.
    // The baseline is a p50, because the sweep values are p50s. Handing
    // classify_feature a base p99 against p50 sweep points compares two
    // different statistics: the p50 sits below the p99 almost by construction,
    // so every feature reads as "within 10% of base" and lands auxiliary.
    let base_p50 = {
        use subms_block_cache::BlockCache;
        let mut c: BlockCache<u32, u64> = BlockCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (p50, _) = get_hit(canon, |key| c.get(&key).is_some());
        p50
    };

    // ---------- arc: adaptive replacement, recency + frequency lists ----------
    #[cfg(feature = "arc")]
    {
        use subms_block_cache::ArcCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: ArcCache<u32, u64> = ArcCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: ArcCache<u32, u64> = ArcCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("arc", cat, &p99, &reason);
    }

    // ---------- tinylfu: frequency-sketch admission ----------
    #[cfg(feature = "tinylfu")]
    {
        use subms_block_cache::TinyLfuCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: TinyLfuCache<u32, u64> = TinyLfuCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: TinyLfuCache<u32, u64> = TinyLfuCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("tinylfu", cat, &p99, &reason);
    }

    // ---------- weighted: a byte budget rather than a slot count ----------
    #[cfg(feature = "weighted")]
    {
        use subms_block_cache::WeightedCache;
        // 1 byte per entry so capacity_bytes == slot capacity; eviction behaves
        // like the base cache, which isolates the weight bookkeeping itself.
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: WeightedCache<u32, u64> =
                    WeightedCache::with_capacity_bytes(n, |_v: &u64| 1);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: WeightedCache<u32, u64> =
            WeightedCache::with_capacity_bytes(canon, |_v: &u64| 1);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            let _ = c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("weighted", cat, &p99, &reason);
    }

    // ---------- concurrent-shards: measured single-threaded ----------
    // Uncontended on purpose. This isolates the sharding INDIRECTION from the
    // contention it exists to relieve; a multi-threaded number here would say
    // more about the thread count than about the feature.
    #[cfg(feature = "concurrent-shards")]
    {
        use subms_block_cache::ShardedCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let c: ShardedCache<u32, u64> = ShardedCache::with_capacity(n, 16);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let c: ShardedCache<u32, u64> = ShardedCache::with_capacity(canon, 16);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("concurrent-shards", cat, &p99, &reason);
    }

    // ---------- metrics: hit/miss counters on the lookup path ----------
    #[cfg(feature = "metrics")]
    {
        use subms_block_cache::MetricsCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: MetricsCache<u32, u64> = MetricsCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: MetricsCache<u32, u64> = MetricsCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("metrics", 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 put(&mut self, key: K, value: V) -> Option<(K, V)>

Insert or update. Returns the evicted (key, value) pair if eviction happened to make room.

Examples found in repository

examples/growth_main.rs (line 52)

    fn op(&mut self, _round: usize, _i: usize) {
        // A fresh distinct key every op: nothing is ever re-hit, so a naive
        // unbounded map would grow to millions - the LRU must evict to stay flat.
        self.cache.put(self.next, self.value.clone());
        self.next += 1;
    }

examples/sample_app.rs (line 55)

fn base_page_cache() {
    println!("== base: block cache in front of a cold columnar store ==");
    const CAP: usize = 4;
    let mut cache: BlockCache<u64, String> = BlockCache::with_capacity(CAP);

    let hot = [100u64, 101, 102, 103];
    let mut cold_reads = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_none(), "cold on first touch");
        cache.put(id, read_block(id));
        cold_reads += 1;
    }
    println!("  warmed {} pages, {cold_reads} cold reads", cache.len());
    assert_eq!(cache.len(), CAP);

    let mut served = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_some(), "resident page must never miss");
        served += 1;
    }
    println!("  re-read the hot set: {served} served, 0 cold reads");
    assert_eq!(served, CAP);

    let (victim, _) = cache
        .put(200, read_block(200))
        .expect("full cache must evict to admit a new page");
    println!("  admitted page 200, evicted page {victim}");
    assert_eq!(cache.len(), CAP, "capacity is a hard bound");

    // A compaction rewrote page 200, so the cached copy is stale. Invalidate
    // it rather than waiting for the hand to come round.
    assert!(cache.remove(&200).is_some(), "stale page must be dropped");
    println!("  invalidated page 200, {} pages resident", cache.len());
    cache.clear();
    assert!(cache.is_empty(), "clear drops the whole segment");
    println!("  segment dropped, cache empty, capacity still {CAP}");
}

examples/perf_features.rs (line 110)

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

    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 (clock-sweep): the baseline, not a feature ----------
    // Every feature is classified against this. A variant whose lookup lands
    // within a whisker of the base is a capability, not a latency change, and
    // classify_feature says so rather than calling it hot-path by default.
    // The baseline is a p50, because the sweep values are p50s. Handing
    // classify_feature a base p99 against p50 sweep points compares two
    // different statistics: the p50 sits below the p99 almost by construction,
    // so every feature reads as "within 10% of base" and lands auxiliary.
    let base_p50 = {
        use subms_block_cache::BlockCache;
        let mut c: BlockCache<u32, u64> = BlockCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (p50, _) = get_hit(canon, |key| c.get(&key).is_some());
        p50
    };

    // ---------- arc: adaptive replacement, recency + frequency lists ----------
    #[cfg(feature = "arc")]
    {
        use subms_block_cache::ArcCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: ArcCache<u32, u64> = ArcCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: ArcCache<u32, u64> = ArcCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("arc", cat, &p99, &reason);
    }

    // ---------- tinylfu: frequency-sketch admission ----------
    #[cfg(feature = "tinylfu")]
    {
        use subms_block_cache::TinyLfuCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: TinyLfuCache<u32, u64> = TinyLfuCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: TinyLfuCache<u32, u64> = TinyLfuCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("tinylfu", cat, &p99, &reason);
    }

    // ---------- weighted: a byte budget rather than a slot count ----------
    #[cfg(feature = "weighted")]
    {
        use subms_block_cache::WeightedCache;
        // 1 byte per entry so capacity_bytes == slot capacity; eviction behaves
        // like the base cache, which isolates the weight bookkeeping itself.
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: WeightedCache<u32, u64> =
                    WeightedCache::with_capacity_bytes(n, |_v: &u64| 1);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: WeightedCache<u32, u64> =
            WeightedCache::with_capacity_bytes(canon, |_v: &u64| 1);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            let _ = c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("weighted", cat, &p99, &reason);
    }

    // ---------- concurrent-shards: measured single-threaded ----------
    // Uncontended on purpose. This isolates the sharding INDIRECTION from the
    // contention it exists to relieve; a multi-threaded number here would say
    // more about the thread count than about the feature.
    #[cfg(feature = "concurrent-shards")]
    {
        use subms_block_cache::ShardedCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let c: ShardedCache<u32, u64> = ShardedCache::with_capacity(n, 16);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let c: ShardedCache<u32, u64> = ShardedCache::with_capacity(canon, 16);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("concurrent-shards", cat, &p99, &reason);
    }

    // ---------- metrics: hit/miss counters on the lookup path ----------
    #[cfg(feature = "metrics")]
    {
        use subms_block_cache::MetricsCache;
        let sweep: Vec<(usize, u64)> = SIZES
            .iter()
            .map(|&n| {
                let mut c: MetricsCache<u32, u64> = MetricsCache::with_capacity(n);
                for k in 0..n as u32 {
                    c.put(k, k as u64);
                }
                let (p50, _) = get_hit(n, |key| c.get(&key).is_some());
                (n, p50)
            })
            .collect();
        let (cat, reason) = classify_feature(&sweep, Some(base_p50), None);

        let mut c: MetricsCache<u32, u64> = MetricsCache::with_capacity(canon);
        for k in 0..canon as u32 {
            c.put(k, k as u64);
        }
        let (_, get99) = get_hit(canon, |key| c.get(&key).is_some());
        let (_, put99) = put_evicting(canon, |key| {
            c.put(key, key as u64);
        });
        let mut p99 = BTreeMap::new();
        p99.insert("get_hit".to_string(), get99);
        p99.insert("put".to_string(), put99);
        manifest.set_feature("metrics", 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 remove(&mut self, key: &K) -> Option<V>

Invalidate key, returning its value. The vacated slot is refilled by the next insert; the hand does not move, so removal costs one map lookup and one slot store.

Examples found in repository

examples/sample_app.rs (line 77)

fn base_page_cache() {
    println!("== base: block cache in front of a cold columnar store ==");
    const CAP: usize = 4;
    let mut cache: BlockCache<u64, String> = BlockCache::with_capacity(CAP);

    let hot = [100u64, 101, 102, 103];
    let mut cold_reads = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_none(), "cold on first touch");
        cache.put(id, read_block(id));
        cold_reads += 1;
    }
    println!("  warmed {} pages, {cold_reads} cold reads", cache.len());
    assert_eq!(cache.len(), CAP);

    let mut served = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_some(), "resident page must never miss");
        served += 1;
    }
    println!("  re-read the hot set: {served} served, 0 cold reads");
    assert_eq!(served, CAP);

    let (victim, _) = cache
        .put(200, read_block(200))
        .expect("full cache must evict to admit a new page");
    println!("  admitted page 200, evicted page {victim}");
    assert_eq!(cache.len(), CAP, "capacity is a hard bound");

    // A compaction rewrote page 200, so the cached copy is stale. Invalidate
    // it rather than waiting for the hand to come round.
    assert!(cache.remove(&200).is_some(), "stale page must be dropped");
    println!("  invalidated page 200, {} pages resident", cache.len());
    cache.clear();
    assert!(cache.is_empty(), "clear drops the whole segment");
    println!("  segment dropped, cache empty, capacity still {CAP}");
}

pub fn clear(&mut self)

Drop every entry and reset the hand. Capacity is unchanged.

Examples found in repository

examples/sample_app.rs (line 79)

fn base_page_cache() {
    println!("== base: block cache in front of a cold columnar store ==");
    const CAP: usize = 4;
    let mut cache: BlockCache<u64, String> = BlockCache::with_capacity(CAP);

    let hot = [100u64, 101, 102, 103];
    let mut cold_reads = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_none(), "cold on first touch");
        cache.put(id, read_block(id));
        cold_reads += 1;
    }
    println!("  warmed {} pages, {cold_reads} cold reads", cache.len());
    assert_eq!(cache.len(), CAP);

    let mut served = 0;
    for &id in &hot {
        assert!(cache.get(&id).is_some(), "resident page must never miss");
        served += 1;
    }
    println!("  re-read the hot set: {served} served, 0 cold reads");
    assert_eq!(served, CAP);

    let (victim, _) = cache
        .put(200, read_block(200))
        .expect("full cache must evict to admit a new page");
    println!("  admitted page 200, evicted page {victim}");
    assert_eq!(cache.len(), CAP, "capacity is a hard bound");

    // A compaction rewrote page 200, so the cached copy is stale. Invalidate
    // it rather than waiting for the hand to come round.
    assert!(cache.remove(&200).is_some(), "stale page must be dropped");
    println!("  invalidated page 200, {} pages resident", cache.len());
    cache.clear();
    assert!(cache.is_empty(), "clear drops the whole segment");
    println!("  segment dropped, cache empty, capacity still {CAP}");
}