Is your cache the right size? fliplru can tell you

Every cache has a capacity, and almost every capacity is a guess. Too small and the cache thrashes: entries are evicted just before they are needed again. Too large and you pay memory for nothing. Most LRU caches give you no way to tell which one you have. fliplru is a small, fast LRU cache for Rust, no_std and safe, that measures its own fit and turns that measurement into a verdict: use fliplru::{LruCache, Sizing}; use std::num::NonZeroUsize; let mut cache = LruCache::new(NonZeroUsize::new(1000).unwrap()); // ... run your workload ... let stats = cache.stats(); println!("hit ratio {:.1}%", stats.hit_ratio() * 100.0); match stats.sizing() { Sizing::Oversized { needed } => println!("only {needed} entries were ever needed"), Sizing::TooSmall => println!("up to 2x the capacity would turn lucky hits into reliable ones"), Sizing::MuchTooSmall => println!("several times the capacity would help a lot"), Sizing::Thrashing => println!("almost nothing is reused before it is evicted"), Sizing::Fits => println!("a bigger cache would gain little"), _ => println!("run longer"), } Enter fullscreen mode Exit fullscreen mode This post covers how that works, how the verdicts were checked, and how fliplru compares with the popular LRU crates. Two generations and a flip fliplru keeps two hash maps, a current generation and a previous one. New and recently used keys go into the current one. When it holds cap entries the cache flips: the current generation becomes the previous one, the old previous generation is dropped, and an empty current generation begins. A lookup that finds its key in the previous generation moves it back into the current one, so anything still in use survives the next flip. The design is old (the JavaScript hashlru package works the same way), and it has three useful properties: A get of a recently used key is a single hash-table lookup, with no linked list to update. The last cap distinct keys you used are always present. Up to 2 * cap may be, since the previous generation holds on to more, so you plan memory for 2 * cap. Flips measure turnover. No flips means everything you use fits. Flips approaching accesses / cap means almost nothing is used twice before it is dropped. From a flip count to a verdict The flip count alone already tells you a lot, and stats() adds the numbers around it: counter what it is hits lookups found in the current generation promotions lookups found in the previous generation: hits, but lucky ones, since that generation was about to be dropped misses lookups that found nothing inserts, updates, flips peak_entries the most entries ever held: the memory the workload actually needed Promotions are the interesting one. A promotion means the key was reused at a distance between cap and 2 * cap. Many promotions mean the keys in use slightly outnumber the capacity, and a modest increase would turn those lucky hits into reliable ones. No conventional LRU can report this, because it has no second generation to catch the near misses. stats().sizing() combines these into one of six verdicts. The rules are simple: NotEnoughData: fewer than 10 x cap lookups so far. Oversized { needed }: there were no flips. needed is the peak number of entries. Thrashing: the hit ratio is under 10%. TooSmall: more than a quarter of hits were promotions, and either the hit ratio is at least 50% or nearly all hits were promotions. MuchTooSmall: more than a quarter of hits were promotions, with a low hit ratio. Fits: anything else. Checking the verdicts against the truth Rules like these are easy to write and easy to get wrong, so I checked them against ground truth. I ran each test workload at the chosen capacity, then again at half, double and four times that capacity. If halving costs nothing, the cache was oversized. If doubling gains a lot, it was too small. If doubling gains little, it fits. The test set was 21 scenarios: fixed working sets of 0.3 to 20 times the capacity, in rotation and at random; Zipf traffic (a few very popular keys and a long tail) at skews 0.7 to 1.2; Zipf traffic interrupted by one-off scans. Each ran at capacities of 1,000, 10,000 and 100,000. A few of the results: workload (cap 10,000) hit ratio at 2x cap at 4x cap verdict 8,000 keys in rotation 99.2% 99.2% 99.2% Oversized { needed: 8000 } 12,000 keys in rotation 79.2% 98.8% 98.8% TooSmall 50,000 keys at random 28.0% 52.1% 86.7% MuchTooSmall 200,000 keys at random 7.4% 14.4% 27.5% Thrashing Zipf 0.99 over 100,000 keys 75.4% 82.6% 89.0% Fits the same, with scans 18.5% 21.7% 23.7% Fits (scans cannot be cached) The first version of the rules called the 50,000-key case TooSmall ("raise it a little"), when it really needed about four times the capacity. That is why there are two "too small" verdicts. With the split, all 21 scenarios get the right verdict at all three capacities. One case per verdict is now a test in the crate. The counters are plain integers updated as the cache runs. They cost nothing measurable on lookups and about 0.4 ns per put. How fast is it? Here is fliplru against the most-used LRU crates on an Apple M1, with a capacity of 100,000 and times in nanoseconds per operation: cache get (all hits) put Zipf, integer keys loop, String keys fliplru 7.1 16.3 15.4 84.7 fliplru + Fx hasher 5.3 6.0 14.2 85.2 lru 0.18 8.7 36.5 16.7 106.4 (every request misses) schnellru 0.2 7.3 25.5 14.8 100.8 (every request misses) quick_cache 0.7 7.7 31.2 19.9 74.9 Read-throughs use each crate's own best "get or insert" method. fliplru was measured before the counters were added; they add about 0.4 ns to each put. fliplru is clearly fastest on puts, and on gets with a faster hasher. On realistic read traffic it is level with the best; with String keys, the top three trade places from run to run. That is also where I will be careful. Speed is not the main reason to choose fliplru. When a miss costs a database query, a few points of hit ratio matter far more than a few nanoseconds per hit. And at equal memory, fliplru's hit ratio is lower than a classic LRU's (78.7% against 82.0% on Zipf traffic), because a flip drops a whole generation at once where an LRU drops one key at a time. If hit ratio is what you need, quick_cache (S3-FIFO) is better, especially on traffic with one-off scans. So fliplru fits best where operations are very frequent and misses are cheap (memoizing small computations, interning, write-heavy caches), or wherever you want the cache to tell you whether it is the right size. It is also no_std and builds for bare-metal targets such as Cortex-M (it needs an allocator). All of its memory is allocated when the cache is created, and flips reuse it, so it never allocates afterwards, which matters where heap fragmentation is a risk. Design notes Most of the speed comes from ordinary care: the two generations are hashbrown HashTables sharing one hasher, so a key is hashed once per operation; a promotion takes two table operations; a flip reuses the retired table's memory; and get_or_insert_with does a read-through with a single hash. The fast path has one Rust-specific wrinkle. "Return the value if it is in the current generation, otherwise look in the previous one" is a known limitation of today's borrow checker: returning a borrow from one branch, then using the map again in the other. polonius-the-crab makes that single-lookup version expressible in safe Rust, with no runtime cost. Two experiments did not pay off: One table instead of two, with each entry tagged by its generation. Promotions became a single in-place write, and gets got 15% faster. But dropping a generation from a shared table leaves deleted markers that lookups have to skip, and puts became 2.2x slower. The second table's probe that this was meant to save turned out to be cheap: hashbrown checks a whole group of slots in one SIMD comparison. A "probation" generation, the admission idea behind S3-FIFO: new keys must prove themselves before entering the main cache. It nearly matched S3-FIFO on scans, but it gained little on ordinary traffic. It also broke fliplru's guarantee that the last cap keys are always present, which is the property the sizing signal relies on. Benchmarking lessons Run order matters. On a laptop, the order in which benchmarks run moved results by 10-20%. The harness in the repo runs every cache in every round and rotates the order between rounds. Report hit ratio next to time. A cache that misses more is doing different work. On a loop slightly larger than the capacity, a classic LRU misses every request, and its time there measures misses, not hits. Use each crate's best API. Comparing your get_or_insert against someone else's get followed by put is not a fair comparison. Try it cargo add fliplru Enter fullscreen mode Exit fullscreen mode The docs are on docs.rs, and the benchmark harness is in the repository: cd bench && cargo run --release. If stats().sizing() tells you something surprising about one of your caches, I would like to hear about it.