HashLRU

HashLRU is a LRU cache implemented in Rust.

It tries to follow the API exposed by a standard Rust HashMap while enforcing a limited memory footprint by limiting the number of keys using the LRU (least recently used) strategy, which is a quite common cache replacement policy.

The package also comes with some basic FIFO queue implementation, based on a VecDeque. The idea was to restrain the API so that it enforces the fact one pushes on one end and pops from the other. It also has a behavior similar to the LRU, as it drops old entries when the capacity is exceeded.

It has been heavily inspired by lru by Jerome Froelich. The underlying logic is similar, using a double-linked list implemented with pointers, combined with a hash map. HashLRU is slightly less optimized, but the API is a bit richer in some areas.

Typically, on top of common LRU implementations, HashLRU has:

• (de)serialization support
• all kinds of import/export/iterators/dump and other goodies
• a sync version which can be shared between threads

• DiskLRU is very similar in its design, and acts as a persistent store, as opposed to HashLRU being an in-memory cache.
• MenhirKV solves the same problem that DiskLRU addresses, which is "store stuff, keep most used value at hand, drop the rest". It does it in a less pedantic and precise way, but much more efficiently.

Status

HashLRU is between the toy project and something you could use. It comes with with a rather complete test harness and tries to have reasonable documentation, so that's a plus. OTOH it is quite young, and to my knowledge not used in production anywhere.

Also there are many other libraries you could use instead:

• lru is faster, and has a more bare-metal API. See doc and source.
• cached comes with batteries included, has support for many other features than just LRU. See doc and source.
• caches implementes many different types of caches. See doc and source.

Usage

```rust use hashlru::Cache;

let mut cache = Cache::new(4); cache.insert("key1", 10); cache.insert("key2", 20); cache.insert("key3", 30); cache.insert("key4", 40); cache.insert("key5", 50); // key1 has been dropped, size is limited to 4 asserteq!(Some("key2"), cache.lru()); asserteq!(Some(&20), cache.get(&"key2")); // getting key2 has made key3 the least recently used item asserteq!(Some("key3"), cache.lru()); asserteq!(Some(&40), cache.get(&"key4")); // getting key4 makes it the most recently used item assert_eq!("[key3: 30, key5: 50, key2: 20, key4: 40]", format!("{}", cache)); ```

Benchmarks

Taken from a random CI job:

running 10 tests test tests::bench_read_usize_builtin_hashmap ... bench: 34 ns/iter (+/- 1) test tests::bench_read_usize_extern_caches ... bench: 58 ns/iter (+/- 30) test tests::bench_read_usize_extern_lru ... bench: 24 ns/iter (+/- 5) test tests::bench_read_usize_hashlru_cache ... bench: 25 ns/iter (+/- 3) test tests::bench_read_usize_hashlru_sync_cache ... bench: 61 ns/iter (+/- 18) test tests::bench_write_usize_builtin_hashmap ... bench: 104 ns/iter (+/- 19) test tests::bench_write_usize_extern_caches ... bench: 116 ns/iter (+/- 46) test tests::bench_write_usize_extern_lru ... bench: 62 ns/iter (+/- 32) test tests::bench_write_usize_hashlru_cache ... bench: 64 ns/iter (+/- 34) test tests::bench_write_usize_hashlru_sync_cache ... bench: 100 ns/iter (+/- 42) test result: ok. 0 passed; 0 failed; 0 ignored; 10 measured; 0 filtered out; finished in 43.16s

Those are done with a 100k items cache.

Not the results of thorough intensive benchmarking but here are a few facts:

• using hasbrown hash maps speeds up things, this is mostly why hashlru and lru perform better than a vanilla HashMap on these benches.
• hashlru is not the fastest, lru always performs best, it has interesting corner-case optimizations. Use lru if you are after raw speed.

To run the benchmarks:

shell cd bench rustup default nightly cargo bench

Links

• crate on crates.io
• doc on docs.rs
• source on gitlab.com
• DiskLRU, a similar persistent store
• Rust Doubly Linked List Implementation explains how RefCell can be used
• Implementing an LRU Cache in Rust using an array-backed storage
• Source code for lru which has been a great source of inspiration
• early implementation of lru in Rust 0.12.0, great source of inspiration as well

License

HashLRU is licensed under the MIT license.