HashLRU
HashLRU is an experimental 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 strategy, which is a quite common cache replacement policy.
Status
For now this is a toy project, clearly NOT suitable for production use.
There are many other libraries you could use instead:
- lru is faster, and has support for mutable iterators, among other things. See doc and source.
- cached comes with batteries included, has support for many other features than just LRU. See doc and source.
It is written in 100% safe rust code, and as it uses only a HashMap
to store data,
and no RefCell
or pointer or anything, it deals rather nicely with being shared
between threads, moved, etc.
Here is a quick bench done on a 100k items map:
$ cargo bench
Finished bench [optimized] target(s) in 0.03s
Running unittests src/lib.rs (target/release/deps/benches-cc4ef79ee8fe94e4)
running 6 tests
test tests::bench_read_usize_hashlru ... bench: 41 ns/iter (+/- 10)
test tests::bench_read_usize_hashmap ... bench: 14 ns/iter (+/- 1)
test tests::bench_read_usize_lru ... bench: 10 ns/iter (+/- 2)
test tests::bench_write_usize_hashlru ... bench: 114 ns/iter (+/- 22)
test tests::bench_write_usize_hashmap ... bench: 65 ns/iter (+/- 13)
test tests::bench_write_usize_lru ... bench: 24 ns/iter (+/- 5)
test result: ok. 0 passed; 0 failed; 0 ignored; 6 measured; 0 filtered out; finished in 24.36s
Those results are not super reliable, just a one-chost test ran on a laptop.
However there is a tendency: hashlru
is the slowest, lru
performs best (probably because
it keeps the number of items below 100k) and standard hashmap
is in between.
Proof this is a toy project.
Usage
use Cache;
let mut lru = new;
lru.insert;
lru.insert;
lru.insert;
lru.insert;
lru.insert;
// key1 has been dropped, size is limited to 4
assert_eq!;
assert_eq!;
// getting key2 has made key3 the least recently used item
assert_eq!;
assert_eq!;
// getting key4 makes it the most recently used item
assert_eq!;
Links
License
HashLRU is licensed under the MIT license.