Crate fliplru 

An LRU cache with a fast get and a built-in signal for sizing it.

fliplru keeps two hash maps, the current and the previous generation. New and recently used keys live in the current one; when it reaches cap entries it flips: it becomes the previous generation, the old previous generation is dropped, and an empty current generation starts. A key found in the previous generation is moved back into the current one, so anything still in use survives the next flip.

• get is one hash lookup when the key is in the current generation, and every operation hashes the key once.
• The last cap distinct keys used are always in the cache. Up to 2 * cap may be (the previous generation too), so plan memory for 2 * cap entries.
• LruCache::stats tells you whether cap fits your workload: hits, misses, flips and a verdict (Sizing). The flip count alone (LruCache::get_flips) says:
  • no flips: everything you use fits — the cache may be larger than it needs to be;
  • flips close to accesses / cap: almost nothing is reused before it is dropped — the cache is too small to help;
  • in between: the cache is working; fewer flips per access means more reuse.

Example

use fliplru::LruCache;
use std::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("apple", 3);
cache.put("pear", 5);
assert_eq!(cache.get(&"apple"), Some(&3));

// read-through: compute the value only on a miss, with one hash
let n = *cache.get_or_insert_with("plum", || 7);
assert_eq!(n, 7);

// with String keys, look up by &str: no String is built on a hit
let mut by_name: LruCache<String, u32> = LruCache::new(NonZeroUsize::new(100).unwrap());
by_name.get_or_insert_with_ref("alice", || 1);
assert_eq!(by_name.get("alice"), Some(&1));

Choosing the capacity

use fliplru::LruCache;
use std::num::NonZeroUsize;

// 5 keys used round-robin, cache of 2: every access misses, the flips say so
let mut small = LruCache::new(NonZeroUsize::new(2).unwrap());
for i in 0..20 { small.get_or_insert_with(i % 5, || i); }
assert_eq!(small.get_flips(), 9);

// a cache of 5: everything fits, no flips
let mut big = LruCache::new(NonZeroUsize::new(5).unwrap());
for i in 0..20 { big.get_or_insert_with(i % 5, || i); }
assert_eq!(big.get_flips(), 0);

When to use something else

fliplru evicts a whole generation at a time, so at equal memory it keeps somewhat fewer useful keys than a classic LRU, and it is not scan resistant. If hit ratio matters more than speed and the sizing signal, see quick_cache (S3-FIFO) or moka (W-TinyLFU). fliplru is single-threaded (&mut self); wrap it in a lock to share it.

Structs

LruCache

An LRU cache of K to V, hashing keys with S (hashbrown’s default hasher unless chosen with LruCache::with_hasher).

Stats

What a cache has done since it was created or reset: see LruCache::stats.

Enums

Sizing

A verdict on a cache’s capacity, from Stats::sizing.