search

jeromefroe / lru-rs

An implementation of a LRU cache
https://docs.rs/lru/
MIT License
644 stars 106 forks source link

Allow arbitrary "costs" per value inserted #160

Open donald-pinckney opened 2 years ago

donald-pinckney commented 2 years ago

I wouldn't suggest merging this as-is, but its a possibly useful extension I made to LRU for myself, so I thought it might be useful to contribute it back.

The idea is that in some cases I want to limit the cache size not by the number of cache entries, but by some other metric, e.g. number of bytes. This is because that data that I have has a very long tail, in which some values to cache will be extremely large (100s of MBs), so if I were to set a cache size of e.g. 1024 I could easily eat up all my memory. But the large values only occur occasionally, so usually I would like to have a fairly large number of cache entries.

My solution is to add a method, put_with_cost that allows the caller to submit an arbitrary usize "cost" for the key-value pair, and entries from the cache are evicted only when the sum of all cost values exceeds the cost capacity of the cache. So if you were to always pass a cost of 1, that would be the exact same behavior as before. None of this changes the eviction order (still LRU), just the limit at which we have to start evicting.

Let me know if this is something that makes sense here, or not. Thanks!

jeromefroe commented 1 year ago

Hi @donald-pinckney 👋 This is very cool, being able to specify the cost of an entry has come up in the past so I think it could be pretty useful to others as well! Are there any other changes you want to make to the PR before you think it's ready?

rmccue commented 8 months ago

@jeromefroe Is this something you'd consider merging? We'd love to have this functionality in lru-rs, and it looks like it was just awaiting feedback on whether there was anything else @donald-pinckney wanted to add.

(Specifically for us, we're looking for that same functionality of cost based on size to limit memory usage; might be a common enough use case to warrant having something prebuilt included in lru-rs?)

donald-pinckney commented 8 months ago

Aahh, I totally forgot about this! Let me know if there are any specific things I can do to help.

joehoyle commented 8 months ago

I think primarily just the merge conflicts need resolving, and then per @jeromefroe, you're +1 that you think it's ready

jeromefroe commented 8 months ago

I think this would be a great change! So if you don't mind updating the PR to address the merge conflicts I'd be happy to then review