Allow limiting by memory limit instead of item count

[webmaster128]

Same issue as described here: jeromefroe/lru-rs#32. Would you be interested in implementing the solution proposed here?

If such a change is desired, that means the total number of elements is not known anymore. So this would require some changes and probably tradeoffs. Is this something you would like to see happening in this crate?

[marmeladema]

I am definitely not against it, but as always, it depends on the trade-offs.

I like the API you proposed with put_with_cost, other names could be put_with_weight or weighted_put.
Before jumping to implementation, I think it would be worthwhile to describe the semantic of common operations like get, put, put_with_cost with this new model.

[webmaster128]

Sounds good, thanks. I can write a few doc domments to the API functions in the next days to explain the user's view of things.

I like the renaming cost -> weight as it described a little better that this is carried around for the lifetime of the cache entry, not a one-time thing.

[webmaster128]

Looking into this a bit more, I think there are two core changes that the implementation would need:

1. Use a HashMap with no pre-set capacity since we don't know the number of elements in advance. I think we can assume HashMap increases its size in a clever way and at some point it does not grow anymore anyways.
2. Use a doubly-linked list of variable size that has a constant time remove (and get?) function (for moving to the front). Ideally we can use LinkedList at some point, where constant time remove is discussed right now. But it should be doable in the custom implementation somehow.

[marmeladema]

Use a HashMap with no pre-set capacity since we don't know the number of elements in advance. I think we can assume HashMap increases its size in a clever way and at some point it does not grow anymore anyways.

I don't think it's really related to the current work. Moreover, capacity still remains an upper bound number of elements.

Use a doubly-linked list of variable size that has a constant time remove (and get?) function (for moving to the front). Ideally we can use LinkedList at some point, where constant time remove is discussed right now. But it should be doable in the custom implementation somehow.

The current linked list implementation is already doubly-linked and supports constant time remove. I don't really see a value in using LinkedList from stdlib. It lacks some useful APIs and some are marked as deprecated.

Having said that, I think adding support for put_with_weight is not actually that much of a change.
I will PoC something later tonight with the following constraints:

• no change in FixedSizeList, capacity still being an upper bound number of elements, that part won't change.
• store weight alongside key and value in the linked list nodes. Probably introducing a struct CLruCacheNode to holds those fields instead of relying on a tuple.

One thing that we would have to be careful of is the fact, as you noted in the PR, that put_with_weight won't be constant for a weight greater than 1. It will have to pop_back() until the weight of the cache + the additional node is <= capacity. I think it's OK, as long as put itself remains O(1).

The last thing I am unsure is the type of the weight argument?

• Should it be a NonZeroUsize? But it might complicate the API too much?
• Or a plain usize? But then what is the semantic of a put_with_weight(key, value, 0) call?

[webmaster128]

After thinking about this a little more, I also don't think the STL's LinkedList will add the index table that we have here and that is required. The only property of it we might want to have is variable length.

I think the core difference between my original proposal and your proposal is the limits. There are two options:

1. One dimensional: there is a single limit, and elements have variable weight. We don't know the number of elements at all since the application can use extremely large weights for very little number of elements.
2. Two-dimensional: there is a limit for the number of elements and a limit for the weight. This allows us to make assumptions on the expected number of elements.

I think both ways can work. The first one feels more elegant to me, but the second one probably makes some of the implementation more performant. Some of your open questions can probably only answered after choosing one route or the other.

It will have to pop_back() until the weight of the cache + the additional node is <= capacity. I think it's OK, as long as put itself remains O(1).

Since you have the worst case scenario where the cache is filled with N elements of weight 1 and you need to remove all of them in order to put in an element of weight N, I don't think O(1) is achievable.

[marmeladema]

Since you have the worst case scenario where the cache is filled with N elements of weight 1 and you need to remove all of them in order to put in an element of weight N, I don't think O(1) is achievable.

Since put will always use a weight of 1, it you will never have to pop more then 1 element, just as it's done right now; so it should work. Providing we don't allow weight of 0

[webmaster128]

Nice catch, yeah, put and put_with_weight have different worst case characteristics then.

This makes weight > 0 an important property and I'd rather use NonZeroUsize than a panicking implementation or adding additional Result wrappers.

[marmeladema]

or adding additional Result wrappers.

I kind of think we will have to do this nonetheless. There is the case of someone calling put_with_weight() with a weigh bigger than the actual capacity of the cache. In that case, even clearing the cache won't make room for enough space.
It can already happen currently but only when the capacity is 0 which is a very unlikely scenario and thus in practice we ignore put() call if the capacity is 0 instead of returning an error.
But with put_with_weight is becomes very likely that this situation will arise and that people will need to know their insert failed. Ignoring the call all-together does not seem the right answer anymore.

[webmaster128]

Right.

I think it is reasonable to skip the put if it does not fit in just as the zero capacity case. It like filling water in a bucket. You can do that as much as you want but it can happen that the amount if water inside does not increase by doing so. Configuring the cache in a way that it makes sense for the use case and produces cache hits needs to be done by the application anyways.

I don't have a strong opinion here. Both APIs seem solid to me.

[marmeladema]

Done in #32