contain-rs / lru-cache Goto Github PK
View Code? Open in Web Editor NEWA cache that holds a limited number of key-value pairs
Home Page: https://contain-rs.github.io/lru-cache/lru_cache/
License: Apache License 2.0
A cache that holds a limited number of key-value pairs
Home Page: https://contain-rs.github.io/lru-cache/lru_cache/
License: Apache License 2.0
LinkedHashMap
already opts in to {Send, Sync}
, so these should be unnecessary.
Since the capacity is restricted, it makes sense not to over- or underallocate on creation.
dashes vs underscores is causing trouble
Is it possible to implemented Serialize
and Deserialize
, just as LinkedHashMap did?
lru_time_cache have implement this feature, but it is licensed under the GPL-3.0. Can you implement the expire time support? It would be very useful and helpful.
Something like:
extern crate lru_cache;
use lru_cache::LruCache;
use std::sync::RwLock;
fn main() {
let mut cache = LruCache::new(2);
cache.insert(1, 10);
let rwlock = RwLock::new(cache);
let lock = rwlock.read().unwrap();
let value = lock.get_mut(&1);
println!("{:?}", value);
}
I got:
error: cannot borrow immutable borrowed content as mutable
--> src\main.rs:12:17
|
12 | let value = lock.get_mut(&1);
| ^^^^
This depends on contain-rs/linked-hash-map#3.
Please publish some of the latest changes to crates.io. I've been forced to set the dependency to point to the github repository for the time being in my project in order to use remove_lru
.
with_hash_state
should become with_hasher
.
$ cargo --version
cargo 0.7.0 (built 2016-01-18)
$ rustc --version
rustc 1.7.0-dev
Thanks to cargo outdated, I noticed:
cargo outdated
Checking for SemVer compatible updates...Done
Checking for the latest updates...Done
The following dependencies have newer versions available:
Name Project Ver SemVer Compat Latest Ver
lru-cache->linked-hash-map 0.2.1 -- 0.3.0
This is more of a feature request. But would it be possible to make remove_lru()
public?
I've been missing this when implementing an adaptative replacement cache.
Thanks!
Tag each entry with "last-used-at" timestamp, and at eviction time pick the LRU among N randomly selected entries.
This is one of the eviction policies supported by Redis: http://redis.io/topics/lru-cache
Maybe it should be a separate container though, because it won't need the linked hash map.
use lru_cache::LruCache;
fn main() {}
#[test]
fn test_panics() {
let mut l = LruCache::new(10);
l.insert(1, false);
}
cargo test
This code panics when the linked-hash-map
crate used by lru_cache
is under version 0.5.3, because it contains uninitialized memory allocation.
The uninitialized memory problem seems to be fixed for version 0.5.3, but because the dependency is specified in Cargo.toml
as
linked-hash-map = "0.5"
It means that cargo is free to choose any version >=0.5.0
, and if the 0.5.1
or 0.5.2
versions are present in the local package cache, they might be picked.
Rewriting it instead as
linked-hash-map = "0.5.3"
and releasing it as new minor version 0.1.3
would fix the problem, as cargo would be forced to pick a version >=0.5.3
Motivation:
My use-case for lru-cache
involves inspecting items' heap size. Rather than hack it in, I think it would be beneficial to make the cache adaptable to whatever limit needs to be imposed.
You might have a set of heterogeneous items, each using a different amount of allocation on the heap. Maybe a more general Meter
trait might help:
trait Meter<T> {
fn measure(&self, item: &T) -> usize;
}
The default Meter
could be a Count
:
struct Count;
impl<T> Meter<T> for Count {
fn measure(&self, _: &T) -> usize { 1 }
}
Here's an implementation that would use the HeapSizeOf
trait (I'd recommend this one for inclusion under a feature gate as it's generally useful.)
struct HeapSize;
impl<T: HeapSizeOf> Meter<T> for HeapSize {
fn measure(&self, item: &T) -> usize { item.heap_size_of_children() + ::std::mem::size_of::<T>() }
}
When you add or remove an item, you add or subtract meter.measure(&item)
from the maximum respectively. If the metered total exceeds the maximum while adding an item, other items must be removed in a loop until the total falls below the limit.
Caveats:
get_mut
or interior mutability could allow items to be altered such that their measure at insertion time differs from their measure at removal. We could add a UniformMeter<T>
which takes no reference to individual items when measuring -- indicating that the measurement is unrelated to item size. get_mut
might only be implemented when the meter is uniform, while fn get(&mut self, key: &Q) -> Option<&T>
would serve as an alternative implemented for all caches. This doesn't solve the interior mutability issue, but that can be addressed the same way as in HashMap
: documentation specifying that it's a logic error to modify the value such that its measure would be altered.insert
can remove multiple items -- how do we return each of them to the caller efficiently? (maybe an iterator?)Alternatively:
get_mut
and adjust the total correspondingly. The issue here is that it would need to be done through a CacheHandle<'a, T: 'a>
which contains that logic in its destructor. This would break backwards compatibility, and would need to handle returning displaced items if the size grows.Looking forward to your comments and naming suggestions below.
I made a fork that handle cache capacity using entries size rather than entries number.
I found it useful to keep control of memory usage, when cache entries are collections or strings with different legths.
I don't think it is should be merged back (that's why an issue instead of a PR), but I was wondering if you'd like to take it as a contain-rs
project. Let me know!
This depends on contain-rs/linked-hash-map#4.
Depends on contain-rs/linked-hash-map#34.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.