Designing and implementing v0.1.0 of tiny-lru

A small-then-spill LRU cache, as fast as stack-based LRUs but scaling like heap-backed ones

Background

LRU caches are a fundamental data structure. Rust has a few LRU crates, but they make you pick a side: either stack storage, which is great for small caches, or heap storage, which is what you want for large ones. Nobody really did both.

The tinyvec crate already solved this well for vectors. It starts with an inline array and "spills" to the heap when needed, so small collections, the common case, are fast and large ones, the edge case, still work.

tiny-lru reuses that tried-and-tested trick for an LRU cache. For small caches it never allocates, and lookups are just a linear search with good cache locality. Once it goes past capacity it moves to heap-backed storage with O(1) operations, without the caller noticing.

Design philosophy (small first, scale second)

The idea behind tiny-lru is pretty simple: make the common case fast first, then deal with the edge cases.

For very small working sets, entries live inline on the stack in a fixed-capacity array, so lookups and updates are fast, never touch the allocator, and keep really good cache locality. Once the inline capacity is exceeded, it spills into a heap-backed LRU (hash map + linked list), which keeps operations O(1) at larger sizes.

I didn't want to give up any speed on small caches, or have it suddenly get much slower on bigger workloads. It's a tinyvec-style hybrid LRU, built for tiny hot paths (embedded, HFT, real-time) but also for unbounded growth when you need it.

The two-tier architecture

Stack-first performance (before the spill)

While the cache is small (≤ N entries), everything happens on the stack:

struct TinyLru<K, V, const N: usize> {
    // Unified node storage; starts inline, spills to heap as capacity grows
    store: tinyvec::TinyVec<[Entry<K, V>; N]>,
    
    // Current number of live items
    size: u16,
    
    // LRU linkage heads (indices into `store`)
    head: u16, // LRU index
    tail: u16, // MRU index
    
    // Key → index map. Lazily allocated ONLY on first spill
    index: Option<hashbrown::HashMap<K, u16>>,
    
    capacity: u16,
}

What that gets you:

• No allocations, since everything fits in the stack-allocated TinyVec.
• Linear search, which for small N is faster than hash lookups.
• It's cache-friendly, because all the data is contiguous in memory.

Heap-backed scalability (after the spill)

Once it goes past the inline capacity, the cache spills on its own:

1. TinyVec does its automatic spill and all entries move to heap storage.
2. The hash map index gets allocated, so lookups are O(1).
3. The linked list stays as it is and keeps the LRU ordering.
4. The API stays the same, so the user doesn't have to change anything.

Basic v0.1.0 API

The API is meant to be a drop-in replacement for the usual LRU caches:

// Core operations
push(key, value)                    // Insert or update; promotes on hit
pop() -> Option<(K, V)>             // Remove and return the LRU entry
get(&mut self, key: &K) -> Option<&V>        // Lookup with promotion
get_mut(&mut self, key: &K) -> Option<&mut V> // Mutable lookup with promotion
peek(&self, key: &K) -> Option<&V>  // Lookup without promotion
remove(&mut self, key: &K) -> Option<(K, V)> // Remove by key

// Capacity management
set_capacity(&mut self, new_cap: u16) // Adjust total capacity
capacity() -> u16
len() -> u16
is_empty() -> bool

// Spill management
is_spilled() -> bool    // Check if using heap storage
can_unspill() -> bool   // Check if unspill is possible
unspill() -> bool       // Move back to inline storage

The AoS vs SoA experiment (and why I abandoned it)

Initially, I considered a Struct of Arrays (SoA) approach so I could use SIMD:

struct TinyLruSoA<K, V, const N: usize> {
    hashes: TinyVec<[u64; N]>,        // Pre-computed hashes for SIMD
    keys: TinyVec<[K; N]>,            // Actual keys
    values: TinyVec<[V; N]>,          // Values
    next: TinyVec<[u16; N]>,          // DLL next pointers
    prev: TinyVec<[u16; N]>,          // DLL prev pointers
    // ...
}

The theory was that separate arrays would let me do SIMD hash comparisons and use the cache better.

In practice it was actually slower. The overhead of maintaining separate arrays, plus the complexity of the SIMD code, outweighed the benefits it had on paper. Sometimes the simple solution really is the best one.

Performance results

I benchmarked tiny-lru against the major Rust LRU implementations across different cache sizes.

Pre-spill performance (small cache sizes)

Performance comparison showing relative speed (higher numbers = slower). tiny-lru is the baseline (1.00).

Push

Pop

Peek

Get

The results are great-ish. tiny-lru is consistently faster across small sizes. Although as N increases traditional lru's start catching up.

Post-spill performance (large cache sizes)

For larger caches, tiny-lru stays competitive:

Peek

Get

Put

Keeping it simple paid off

The numbers back up the "simple is better" idea:

1. For small N (typically N ≤ 32), a linear search beats a hash table.
2. Stack allocation is faster than heap allocation when the workload is predictable.
3. Contiguous memory keeps the cache happy, and chasing pointers around doesn't.
4. Having two tiers works better for mixed workloads than a one-size-fits-all design.

Future work

v0.1.0 is good enough for now, but there's still stuff I want to do:

• Support larger sizes
• Optimise pop() and find_key_index() further()
• Have optinal stronger guards against spill.