Weighted cache entries with size limit

[dave-yotta]

i.e. if we know or approx the memory usage of each entry in Mb and want to bound the cache to X Mb.

If we picked a suitable N for the capacity bound and did this psuedocode:

var cache = new ConcurrentCache<T>();
add(x) => { total = Interlocked.Increment(x.Size); while(total > limit) cache.Trim(1); }
onEvicted += x => total = Interlocked.Decrement(x.Size)

any thoughts on stability/performance? I've been asking this everywhere because I can't find an implementation in .NET!

[sakno]

What are you trying to achieve? To which part of .NEXT API the question belongs to? The lack of the context might lead to incorrect answer from my side.

Anyway, I can try. The following code is not thread safe:

total = Interlocked.Increment(x.Size); while(total > limit) cache.Trim(1);

Assuming that total === 1 and x.Size == 1 with two competing threads we can see the following picture:

• Thread 1:
  • total == 2 after Increment, but not yet reached while loop
• Thread 2:
  • total == 3 after Increment

Thread 2 removes 2 items, thread 1 removes 1 item. As a result, the cache removes 3 items instead of 2.

[sakno]

each entry in Mb and want to bound the cache to X Mb.

Just compute entry_max_size / cache_max_size and you'll get the maximum capacity of the cache. After that, LRU/LFU cache can be used normally.

[dave-yotta]

Sorry my bad - that's with a ConcurrentCache

entry size ranges from bytes to megabytes so would end up with an underutilized cache with the above

Been struggling to find a lib that implements this in .NET - been over here too: bitfaster/BitFaster.Caching#602

I don't think there's a lockless threadsafe way to do it from the outside. I'm guessing such a lock would be contended so much that performance would stuffer.