MemoCache

A small, fixed-size cache with retention management, e.g. for use with memoization.

This library does not use the standard library so it is compatible with #[no_std] crates.

Introduction

Sometimes it can be beneficial to speedup pure function calls by using memoization.

The cache storage required for implementing such a speedup often is an associative container (i.e. a key/value store). Programming language standard libraries provide such containers, often implemented as a hash table or a red-black tree. These implementations are fine for performance, but do not actually cover all use cases because of the lack of retention management

Suppose your input data covers the whole space that can be represented by a 64-bit integer. There probably is some (generally non-uniform) probability distribution with which the input values arrive, but it's statistically possible that over time all possible values pass by. Any cache without retention management will then grow to potentially enormous dimensions in memory which is undesirable, especially in memory-constrained environments.

The cache implemented in this library uses a sequential data storage with fixed size, pre-allocated memory. When the cache is full, an approximate least-frequently-used (LFU) eviction policy selects the entry to replace, based on per-slot hit counts.

Example usage

Suppose we have a pure method calculate on a type Process (without memoization):

struct Process { /* ... */ }

impl Process {
    fn calculate(&self, input: u64) -> f64 {
        // ..do expensive calculation on `input`..
    }
}

Each single call to this function results in the resource costs of the calculation. We can add memoization to this function in two different ways:

• Using MemoCache::get_or_insert_with (or get_or_try_insert_with),
• Using MemoCache::get and MemoCache::insert.

For each of the following examples: each call to calculate will first check if the input value is already in the cache. If so: use the cached value, otherwise update the cache with a new, calculated value.

The cache is fixed-size, so if it is full, a rarely used key/value pair will be evicted, and memory usage is constant.

See the examples/ directory for more example code.

Example A: get_or_insert_with

struct Process {
    cache: MemoCache<u64, f64, 32>,
}

impl Process {
    fn calculate(&mut self, input: u64) -> f64 {
        *self.cache.get_or_insert_with(&input, |&i| /* ..do calculation on `input`.. */)
    }
}

For fallible insert functions, there's get_or_try_insert_with that returns a Result.

Example B: get and insert

struct Process {
    cache: MemoCache<u64, f64, 32>,
}

impl Process {
    fn calculate(&mut self, input: u64) -> f64 {
        if let Some(result) = self.cache.get(&input) {
            *result // Use cached value.
        } else {
            let result = /* ..do calculation on `input`.. */;
            self.cache.insert(input, result);
            result
        }
    }
}

Performance notes

MemoCache stores its entries in a plain array and finds keys using a linear scan, so the per-lookup cost grows with the cache size, whereas HashMap lookup is (amortized) constant-time. The cache can therefore only win on raw lookup speed at small sizes. Indicative numbers from the included benchmarks (per lookup, all keys resident, one x86-64 test machine):

Broad conclusions from the measurements (but always analyze your input data and measure with your own workload!):

• Up to roughly 16-32 elements, MemoCache lookups are the fastest of the three; beyond that, the linear scan loses to both HashMap and BTreeMap.
• The cache's own miss/evict overhead is small (on the order of 10-50 ns per operation, size-dependent). What dominates in practice is the miss rate: every miss re-runs your expensive computation.
• If the working set fits the cache capacity, MemoCache performs at par with or better than the unbounded maps, at a small fraction of their memory use.
• If the working set exceeds the capacity, entries are continuously evicted and recomputed, while an unbounded map would eventually stop missing altogether. This is the deliberate trade: bounded, constant memory in exchange for recomputation under cache pressure.
• Skewed input distributions (a small set of hot keys) favor MemoCache: hot keys tend to sit early in the scan order, shortening the average lookup well below the worst case.

Run the included benchmarks using criterion by invoking: cargo bench There are three benchmark families: steady-state memoization throughput per input distribution, hit-path-only lookups, and churn (miss/evict) overhead.

Implementation details

This cache stores its key/value pairs in a fixed-size array. A slot in this array represents a key/value and is either empty or occupied.

When a new item is inserted, first a check for empty slots is performed. If all cache slots are occupied, an approximate least-frequently-used (LFU) eviction policy is used to determine the slot that will be replaced. This policy works as follows:

1. For each cache slot value access, a "hit count" is stored,
2. Using a PRNG (Xorshift32), a random buffer index is generated,
3. Starting from the random buffer index, a (wrapping) window of elements is queried for the slot with the lowest hit count,
4. The slot with the lowest hit count is replaced with the new key/value pair.

Cache slot hit count is registered as a single byte value, and is decayed for all slots if any slot reaches a threshold value. This decay slowly ages out entries that were popular in the past, adding a mild recency component to the otherwise frequency-based policy.

Other than the LFU-style eviction policy, the implementation of the cache makes no assumptions whatsoever about the input data probability distribution, keeping the cache clean and simple.

TODO

• Currently, the implementation focuses on simplicity and makes no assumptions about the data arrival probability distribution. However, this could potentially be very beneficial. Investigate cache performance improvements.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.