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.

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
• SQueue, a FIFO queue that drops old items (was present in 0.10.0)
• 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.