marmeladema / clru-rs Goto Github PK

38.0 2.0 8.0 72 KB

An LRU cache implementation with constant time operations and weighted semantic.

License: MIT License

Rust 100.00%

lru cache hashmap rust

clru-rs's Introduction

CLru

Another LRU cache implementation in rust. It has two main characteristics that differentiates it from other implementation:

It is backed by a HashMap: it offers a O(1) time complexity (amortized average) for common operations like:
- get / get_mut
- put / pop
- peek / peek_mut
It is a weighted cache: each key-value pair has a weight and the capacity serves as both as:
- a limit to the number of elements
- and as a limit to the total weight of its elements
using the following formula:

CLruCache::len + CLruCache::weight <= CLruCache::capacity

Even though most operations don't depend on the number of elements in the cache, CLruCache::put_with_weight has a special behavior: because it needs to make room for the new element, it will remove enough least recently used elements. In the worst case, that will require to fully empty the cache. Additionally, if the weight of the new element is too big, the insertion can fail.

For the common case of an LRU cache whose elements don't have a weight, a default ZeroWeightScale is provided and unlocks some useful APIs like:

CLruCache::put: an infallible insertion that will remove a maximum of 1 element.
CLruCache::put_or_modify: a conditional insertion or modification flow similar to the entry API of [HashMap].
CLruCache::try_put_or_modify: fallible version of CLruCache::put_or_modify.
All APIs that allow to retrieve a mutable reference to a value (e.g.: CLruCache::get_mut).

Disclaimer

Most of the API, documentation, examples and tests have been heavily inspired by the lru crate. I want to thank jeromefroe for his work without which this crate would have probably never has been released.

Differences with lru

The main differences are:

Smaller amount of unsafe code. Unsafe code is not bad in itself as long as it is thoroughly reviewed and understood but can be surprisingly hard to get right. Reducing the amount of unsafe code should hopefully reduce bugs or undefined behaviors.
API closer to the standard HashMap collection which allows to lookup with Borrow-ed version of the key.

Example

Below are simple examples of how to instantiate and use this LRU cache.

Using the default `ZeroWeightScale`:

use std::num::NonZeroUsize;
use clru::CLruCache;

let mut cache = CLruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("apple".to_string(), 3);
cache.put("banana".to_string(), 2);

assert_eq!(cache.get("apple"), Some(&3));
assert_eq!(cache.get("banana"), Some(&2));
assert!(cache.get("pear").is_none());

assert_eq!(cache.put("banana".to_string(), 4), Some(2));
assert_eq!(cache.put("pear".to_string(), 5), None);

assert_eq!(cache.get("pear"), Some(&5));
assert_eq!(cache.get("banana"), Some(&4));
assert!(cache.get("apple").is_none());

{
    let v = cache.get_mut("banana").unwrap();
    *v = 6;
}

assert_eq!(cache.get("banana"), Some(&6));

Using a custom `WeightScale` implementation:

use std::num::NonZeroUsize;
use clru::{CLruCache, CLruCacheConfig, WeightScale};

struct CustomScale;

impl WeightScale<String, &str> for CustomScale {
    fn weight(&self, _key: &String, value: &&str) -> usize {
        value.len()
    }
}

let mut cache = CLruCache::with_config(
    CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(CustomScale),
);

assert_eq!(cache.put_with_weight("apple".to_string(), "red").unwrap(), None);
assert_eq!(
    cache.put_with_weight("apple".to_string(), "green").unwrap(),
    Some("red")
);

assert_eq!(cache.len(), 1);
assert_eq!(cache.get("apple"), Some(&"green"));

Tests

Each contribution is tested with regular compiler, miri, and 4 flavors of sanitizer (address, memory, thread and leak). This should help catch bugs sooner than later.

TODO

improve documentation and add examples

clru-rs's People

Stargazers

Watchers

Forkers

webmaster128 maurolacy bhgomes yun-yeo yosi-hezi pholien163 calmofthestorm martinvonz

clru-rs's Issues

Send trait implementation

Currently CLruCache never implements Send trait because Key<K> uses Rc internally. However in this crate, Key/Rc is always owned by CLruCache and never leaves the structure which means that CLruCache could in theory implement Send (assuming K, V, S and W are all Send).

Implementing Send would allow for usage of &Mutex<CLruCache<...>> from multiple threads.

Does the order of elements in FixedSizeList::free matter?

If I understand correctly, FixedSizeList::free contains a list of position in FixedSizeList::nodes that are free to be used. If I also understand correctly, the order in FixedSizeList::nodes is irrelevant for the logic, since elements are sorted via the FixedSizeListNode::prev/::next links.

I wonder because during review I noticed that free is filled with elements in descending order in the constructor and in ascending order in clear.

Then, isn't FixedSizeList::free better modelled as a set, which has no order and elements must be unique?

Add `Sync` version

Hey, I was interested in using this crate in one of projects, however I need CLruCache to be Sync, as I want to share the cache between threads. Would you be willing to either changing to be using Arc internally or providing a sync version of CLruCache?

How to access LruCache<&'a str, String> with the key of String?

It looks like get requires the argument has the same lifetime as it's key.

use clru::CLruCache;
use std::collections::HashMap;

struct Store<'a> {
    index: HashMap<&'a str, String>,
    cache: CLruCache<&'a str, String>,
}

impl<'a> Store<'a> {
    fn foo(&mut self, key: String) -> String {
        self.index.get(&key.as_str()).unwrap().to_owned()
    }

    fn bar(&mut self, key: String) -> String {
        self.cache.get(&key.as_str()).unwrap().to_owned()
    }
}

How can I get the method bar to compile?

I firstly opend a same issue at lru-rs. Then I found this crate and tried it. But it also doesn't compile. Maybe I did not use it in a correct way?

Resize API

It should be possible to implement a CLruCache::resize method to shrink or grow the capacity of the cache.
There is actually two cases:

Growing: it should be easy, its just a matter of increasing the size of the boxed slice in the FixedSizeList
Shrinking: its more complicated and one idea might be to first provide a re-order / sort internal API such that the node in the FixedSizeList would be sorted from most recent to least recent (same order as iteration) and then truncating the boxed slice of nodes.