# cache-mod v0.5.0 — TinyLFU, SizedCache, property tests, benchmarks

**The eviction-policy roster is complete.** The public surface that started landing at 0.2.0 now contains all five policies the crate set out to ship: `LruCache`, `LfuCache`, `TtlCache`, `TinyLfuCache`, and `SizedCache`, all behind a single [`Cache`] trait. Property tests and Criterion benchmarks join the suite. Lock-free / arena-backed internals slip to 0.6.0 — a non-API change that can land at any time without breaking call-sites.

## What is cache-mod?

High-performance in-process caching for Rust with five eviction policies all behind one trait. Async-safe (`&self` everywhere, `Send + Sync` cache instances), lock-minimized internals, typed key-value API. No dependency on any external store.

## What's in 0.5.0

### `TinyLfuCache<K, V>` — admission-controlled LRU

The headline policy. A fixed-size **Count-Min Sketch** observes every key the cache encounters (hit or miss), giving the cache a frequency estimate for keys it does not currently store. On capacity overflow, the cache compares the incoming candidate's estimated frequency to the LRU victim's; **admission is granted only if the candidate is warmer**. One-hit-wonders are rejected at the door instead of displacing hot entries.

This is a deliberate semantic deviation from the other four cache types and is surfaced prominently in the type docs: a successful `insert` call on `TinyLfuCache` **does not guarantee** the value is in the cache. If your code path needs strict insertion guarantees, use `LruCache` or `LfuCache` — they always admit.

Reference implementation parameters:

- depth-4 Count-Min Sketch, `u8` saturating counters
- width = `max(64, 2 × capacity)`, rounded to the next power of two
- W-TinyLFU "aging" step: every `10 × capacity` increments, every counter is right-shifted by 1, so the sketch stays responsive to workload shifts
- main cache uses LRU access ordering; the eviction victim is always the least-recently-accessed entry
- single `Mutex<Inner>` for now (consistent with the rest of the family); the lock-strategy upgrade lands in 0.6.0

The SLRU segmentation and doorkeeper Bloom filter from the full W-TinyLFU paper are not part of the 0.5.0 reference impl — they are good candidates for a 1.x quality pass.

### `SizedCache<K, V>` — byte-bound capacity

The first cache type in the crate where the capacity bound is **not** entry count. Each value is weighed at insert time by a user-supplied `fn(&V) -> usize`, and total weight across all entries is kept within `max_weight`. Eviction uses LRU semantics until the new entry fits.

API design notes:

- The weigher is a plain function pointer, not a closure — captured state would force `Box<dyn Fn>` indirection on every weigh call. Hoist state into the value itself if you need it.
- Values whose own weight exceeds `max_weight` are silently rejected (insert returns `None`, value is dropped, cache is unchanged). The alternative — a new error variant — felt heavyweight for a degenerate input.
- [`max_weight()`] and [`total_weight()`] expose the bound and the dynamic in-use weight. [`capacity()`] returns `max_weight` for trait consistency, and the trait rustdoc was updated to cover both interpretations.

Worth highlighting: the weigher's unit is whatever you choose. Common choices include `Vec::len()` for payload bytes, `mem::size_of::<T>() + heap_allocation_estimate` for header-inclusive sizing, or a fixed-cost approximation. The cache does not interpret units — it just sums and compares.

### Internal scaffolding cleanup

Three concrete caches now share a single piece of duplicated machinery: the poison-recovery `lock_inner` helper. Each previously inlined the same six lines; with `TinyLfuCache` and `SizedCache` landing, that would have been five copies. Lifted into a `pub(crate) trait MutexExt::lock_recover` extension in `src/util.rs` and threaded through all five caches. Code reduction is small (~24 lines net) but more importantly there is now one place to change the policy if poison handling ever needs to evolve.

The `find_victim`-style scan helpers stay per-policy because their comparison criteria genuinely differ (LRU = `last_access`, LFU = `count` then `last_access`, TTL = `expires_at`, TinyLFU = LRU on the main, Sized = LRU). A generic-callback abstraction would be more code than it saves.

### Property tests

A new `tests/properties.rs` adds 9 properties via `proptest`, run on every CI invocation:

- Five capacity-invariant tests — one per cache type — drive random sequences of `insert` / `get` / `remove` / `contains_key` and assert `len <= capacity` (or `total_weight <= max_weight` for `SizedCache`) holds after every operation.
- Four insert-then-get round-trip tests confirm that `LruCache`, `LfuCache`, `TtlCache`, and `SizedCache` actually persist a value when inserted into a non-full cache. `TinyLfuCache` is excluded — its admission filter intentionally violates this property.

The smallest property test runs 96 cases per property; the round-trips run 64. Total proptest runtime is under 100 ms on the local machine.

### Criterion benchmarks

A new `benches/cache_ops.rs` ships a five-group Criterion suite (`LruCache` / `LfuCache` / `TtlCache` / `TinyLfuCache` / `SizedCache`), each covering `get_hit` and `insert_existing` at capacity 1024. Gated behind `required-features = ["std"]` so `--no-default-features` builds still pass. Numbers are a regression detector, not a marketing claim — there's no scoreboard against other cache crates yet. Run with `cargo bench`.

## What's not in 0.5.0

Deferred to 0.6.0:

- **Lock-free / arena-backed internals.** The reference `Mutex<{ HashMap, VecDeque }>` machinery is correct but does a lot of redundant work (`VecDeque::iter().position()` scans, full HashMap scans for eviction). Replacing this with a stable-index doubly-linked list arena gives O(1) LRU updates and O(1) LFU bucket selection, without changing the public surface. A sharded-Mutex or `crossbeam-epoch` decision lands as part of that work.
- **W-TinyLFU SLRU + doorkeeper.** The 0.5.0 `TinyLfuCache` ships the admission filter (which is most of the value) on top of a flat LRU main cache. The full W-TinyLFU paper adds an SLRU-segmented main cache and a Bloom doorkeeper to further reduce sketch pollution. Both are candidates for a 1.x quality pass and do not affect the public API.

## Breaking changes

**None.** Three new public types (`TinyLfuCache`, `SizedCache`, and `MutexExt` — `pub(crate)`, not exposed) and one rustdoc-text change to `Cache::capacity`. Every 0.4.0 call-site compiles and behaves identically against 0.5.0.

The crate remains pre-1.0; minor versions may break in the future. Pin exact versions.

## Verification

Local run on Windows x86_64, Rust stable. Identical commands pass via the configured CI matrix (Linux / macOS / Windows on stable + MSRV 1.75):

```bash
cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo clippy --all-targets --no-default-features -- -D warnings
cargo test --all-features
cargo doc --no-deps --all-features
```

Optional:

```bash
cargo bench                                # the new Criterion suite
```

All green. Test totals:

- Integration tests: **47 passed** (11 LRU + 8 LFU + 13 TTL + 6 TinyLFU + 9 Sized).
- Property tests (proptest, in `tests/properties.rs`): **9 passed**, each running 64–96 random op sequences.
- Doctests: **18 passed**.

REPS lint surface declared in `src/lib.rs` is honored: every `deny(...)` clippy/rustc lint from 0.2.0 still holds. The single `#[allow(clippy::ptr_arg)]` in `tests/smoke.rs` is justified inline — the `SizedCache` weigher signature requires `&Vec<u8>` to match the function-pointer type. No `unsafe` is introduced in this release.

## What's next

`0.6.0` is the implementation-quality milestone. The reference `Mutex`-guarded internals of `LruCache`, `LfuCache`, and `TtlCache` are replaced by arena-backed, O(1)-update versions. Either sharded `Mutex` (DashMap-style) or `crossbeam-epoch`-based lock-free reclamation is layered on top, with Criterion regression numbers vs the 0.5.0 baselines. Public surface stays byte-identical.

`0.9.0` is the hardening + audit pass; `1.0.0` is the API freeze.

## Installation

```toml
[dependencies]
cache-mod = "0.5"
```

MSRV: Rust 1.75. Edition 2021. `default-features = ["std"]`.

```rust
use cache_mod::{Cache, TinyLfuCache};

let cache: TinyLfuCache<&'static str, u32> = TinyLfuCache::new(256).expect("capacity > 0");

// Build up frequency signal for keys that should stay hot.
for _ in 0..32 {
    let _ = cache.get(&"hot");
    let _ = cache.insert("hot", 1);
}

// A cold candidate is rejected unless its sketch frequency outranks the LRU.
assert_eq!(cache.get(&"hot"), Some(1));
```

```rust
use cache_mod::{Cache, SizedCache};

fn byte_weight(v: &Vec<u8>) -> usize { v.len() }

let cache: SizedCache<&'static str, Vec<u8>> =
    SizedCache::new(4 * 1024, byte_weight).expect("max_weight > 0");

cache.insert("hero-image", vec![0u8; 512]);
assert_eq!(cache.total_weight(), 512);
assert_eq!(cache.max_weight(), 4096);
```

## Documentation

- [README](https://github.com/jamesgober/cache-mod/blob/main/README.md)
- [CHANGELOG](https://github.com/jamesgober/cache-mod/blob/main/CHANGELOG.md)
- [REPS standards](https://github.com/jamesgober/cache-mod/blob/main/REPS.md)
- [API reference](https://docs.rs/cache-mod/0.5.0)

---

**Full diff:** [`v0.4.0...v0.5.0`](https://github.com/jamesgober/cache-mod/compare/v0.4.0...v0.5.0).
**Changelog:** [`CHANGELOG.md`](https://github.com/jamesgober/cache-mod/blob/main/CHANGELOG.md#050---2026-05-20).

[`Cache`]: https://docs.rs/cache-mod/0.5.0/cache_mod/trait.Cache.html
[`max_weight()`]: https://docs.rs/cache-mod/0.5.0/cache_mod/struct.SizedCache.html#method.max_weight
[`total_weight()`]: https://docs.rs/cache-mod/0.5.0/cache_mod/struct.SizedCache.html#method.total_weight
[`capacity()`]: https://docs.rs/cache-mod/0.5.0/cache_mod/trait.Cache.html#tymethod.capacity
