Implement FIFO and LRU caches through a Map memory limit

[mrj]

I would like to allow a max_bytesize to be set for a Concurrent::Map, which would stop the combination of the map and its entries from getting any bigger by automatically deleting entries when a new one is added. Deletion of the oldest entry is easy through Hash#shift. New entries would automatically make a FIFO cache, while an LRU cache would need each accessed entry to be deleted and re-added.

Is this something worth working up a PR for? If so, does anyone have any suggestions on what to do and what not to do?

[eregon]

Note that Concurrent::Map does not have ordering and no Hash#shift equivalent, so you probably mean Concurrent::Hash instead.

It sounds pretty easy to make your own on top of Concurrent::Hash so I guess the question is should that be part of concurrent-ruby or not.
@byroot I think you have experiences with such caches, any thoughts?

max_bytesize is probably quite hard though because how would you find out the memory used by Ruby objects?
AFAIK such caches are typically bound by a number of entries instead.

[byroot]

I think you have experiences with such caches, any thoughts?

My experience is that most of the time they are heavily mis-used and make things worse (stressing the GC, causing majors to trigger more often, hence wasting more resources than it saves), but in a few case they're useful.

The memsize can indeed only be cooperative (entry must implement #bytesize) or limited to strings.

[mrj]

Thank you Benoit and Jean for those thoughts.

I'd looked at the code, and the (C) Map backend seemed to be a standard Hash. So I don't yet understand in what ways a Concurrent::Map can be non-order-preserving.

But yes, for Concurrent::Hash I could probably implement this separately through its standard API calls.

I was planning to use ObjectSpace.memsize_of to calculate memory usage.

I need this, otherwise my caches will expand without bound. But I note your performance concerns. Perhaps the deletion of old keys should happen periodically rather than after most insertions, limiting memory usage to a range. But there's no bulk equivalent of shift.

[byroot]

I was planning to use ObjectSpace.memsize_of to calculate memory usage.

You can't. This only give you the size of a single object. e.g. ObjectSpace.memsize_of([1]) == ObjectSpace.memsize_of(["A" * 999999999]).

[mrj]

I was going to sum the sizes of each Hash/Map entry (with support for a custom size-calc proc if one needs to go deeper) , maybe even not bothering to add the size of the Hash/Map itself.

[eregon]

I'd looked at the code, and the (C) Map backend seemed to be a standard Hash.

There is no implementation of Concurrent::Map in C in this repository, what do you mean?

https://github.com/ruby-concurrency/concurrent-ruby/blob/master/lib/concurrent-ruby/concurrent/map.rb happens to use Hash internally on CRuby for simplicity, but it's not the case on other Ruby implementations which have a proper concurrent map and therefore no ordering (maintaining order kills concurrency for a map-like data structure).

[mrj]

Sorry, by C I meant MRI. A custom map implementation by other Rubies explains why Map disclaims ordering.

I like the Map API, and probably won't need its iteration methods. Are these the ones that are especially bad for concurrency? Would it be worthwhile to create an OrderedMap with a subset of the map API and a forced Hash backend that is relatively performant, on which I can build automatic size limits.

[eregon]

a forced Hash backend

Then just use Concurrent::Hash.
The cost of ordering is all writes contend on the same pointer compare-and-swap, so the cache line needs to change from CPU core to CPU core for basically every write. With a LRU there is also a write for every get. So you end up with a collection that's anyway no faster than locking around every operation, and then Concurrent::Hash is fine enough for that.