5 stable releases
1.3.0 | May 18, 2023 |
---|---|
1.2.2 | Nov 26, 2022 |
1.2.1 | Apr 27, 2021 |
1.1.0 |
|
#63 in Caching
38 downloads per month
Used in 3 crates
100KB
2K
SLoC
lfu-cache
An implementation of a constant time Least Frequently Used (LFU) cache roughly based on the paper by Shah, Mitra, and Matani.
Example
use lfu_cache::LfuCache;
let mut cache = LfuCache::with_capacity(2);
// Fill up the cache.
cache.insert("foo", 3);
cache.insert("bar", 4);
// Insert returns the evicted value, if a value was evicted, in case additional
// bookkeeping is necessary for the value to be dropped.
let maybe_evicted = cache.insert("baz", 5);
// In the case of a tie, the most recently added value is evicted.
assert!(cache.get(&"bar").is_none());
assert_eq!(maybe_evicted, Some(4));
cache.get(&"baz");
// Otherwise, the least frequently value is evicted.
assert_eq!(cache.pop_lfu(), Some(3));
Reasons to use this implementation
- Zero dependencies.
- Small dependency, only providing the necessary features.
- Fully documented and fully tested (including
miri
). - Respects Rust API guidelines: interface is implements most container APIs where possible.
- Performant: Hits around 10 million insertions per section (using
i32
as elements; seebenches.rs
for bench implementation).
Reasons not to use this implementation
- Internally, this codebase uses
unsafe
as it works with raw pointers. - This can be considered a microcrate, which may be undesired if dependency count is a concern.
Alternatives
- Consider the
lfu
crate for an implementation written in only safe Rust. - Consider
matthusifer/lfu_rs
for another implementation of the same paper.
Deviances from the paper
This implementation very closely follows the paper, but has one modification to
ensure correctness. Each node in the node list contains a Rc
containing the
key it was stored under, and the lookup table instead is indexed on a Rc<Key>
instead. This is to ensure that the correct key-value in the lookup table can
be evicted when popping the least frequently used item.
This modification was necessary as the hash is surjective, and so each item necessarily needs to contain some reference to the original key it was stored under to ensure that we evict the correct key during hash collisions.
An alternative solution would be to use an monotonically increasing counter, but
the additional bookkeeping over an Rc
which functionally provides the same
benefit is unnecessary.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.