created_at2020-01-05 16:12:43.78795
updated_at2024-03-17 13:12:19.176506
descriptionHashLRU is a LRU cache.
Christian Mauduit




# HashLRU [HashLRU](https://gitlab.com/liberecofr/hashlru) is a LRU cache implemented in [Rust](https://www.rust-lang.org/). It tries to follow the API exposed by a [standard Rust HashMap](https://doc.rust-lang.org/stable/std/collections/struct.HashMap.html) 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]( https://en.wikipedia.org/wiki/Cache_replacement_policies). It has been heavily inspired by [lru](https://crates.io/crates/lru) by [Jerome Froelich](https://github.com/jeromefroe). 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 ![HashLRU icon](https://gitlab.com/liberecofr/hashlru/raw/main/hashlru.png) * [DiskLRU](https://gitlab.com/liberecofr/disklru) is very similar in its design, and acts as a persistent store, as opposed to HashLRU being an in-memory cache. * [MenhirKV](https://gitlab.com/liberecofr/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](https://crates.io/crates/lru) is faster, and has a more bare-metal API. See [doc](https://docs.rs/lru/latest/lru/) and [source](https://github.com/jeromefroe/lru-rs). * [cached](https://crates.io/crates/cached) comes with batteries included, has support for many other features than just LRU. See [doc](https://docs.rs/cached/latest/cached/) and [source](https://github.com/jaemk/cached). * [caches](https://crates.io/crates/caches) implementes many different types of caches. See [doc](https://docs.rs/cached/latest/cached/) and [source](https://github.com/al8n/caches-rs). [![Build Status](https://gitlab.com/liberecofr/hashlru/badges/main/pipeline.svg)](https://gitlab.com/liberecofr/hashlru/pipelines) [![Crates.io](https://img.shields.io/crates/v/hashlru.svg)](https://crates.io/crates/hashlru) [![Gitlab](https://img.shields.io/gitlab/last-commit/liberecofr/hashlru)](https://gitlab.com/liberecofr/hashlru/tree/main) [![License](https://img.shields.io/gitlab/license/liberecofr/hashlru)](https://gitlab.com/liberecofr/hashlru/blob/main/LICENSE) # 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 assert_eq!(Some("key2"), cache.lru()); assert_eq!(Some(&20), cache.get(&"key2")); // getting key2 has made key3 the least recently used item assert_eq!(Some("key3"), cache.lru()); assert_eq!(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](https://crates.io/crates/hashbrown) 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](https://crates.io/crates/hashlru) on crates.io * [doc](https://docs.rs/hashlru/) on docs.rs * [source](https://gitlab.com/liberecofr/hashlru/tree/main) on gitlab.com * [DiskLRU](https://gitlab.com/liberecofr/disklru), a similar persistent store * [SQueue](https://gitlab.com/liberecofr/squeue), a FIFO queue that drops old items (was present in 0.10.0) * [Rust Doubly Linked List Implementation](https://rtoch.com/posts/rust-doubly-linked-list/) explains how `RefCell` can be used * [Implementing an LRU Cache in Rust](https://seanchen1991.github.io/posts/lru-cache/) using an array-backed storage * [Source code for lru](https://github.com/jeromefroe/lru-rs) which has been a great source of inspiration * [early implementation of lru in Rust 0.12.0](https://github.com/rust-lang/rust/blob/ba4081a5a8573875fed17545846f6f6902c8ba8d/src/libstd/collections/lru_cache.rs), great source of inspiration as well # License HashLRU is licensed under the [MIT](https://gitlab.com/liberecofr/hashlru/blob/main/LICENSE) license.
Commit count: 0

cargo fmt