How can I create an LRU cache bounded by size in bytes (rather than number of items) in modern C++?

Question

I'm currently using C++17 and I'm looking for a way to implement an LRU cache, but have it be bounded by the size in bytes of the cache contents (e.g. 100MB) rather than the number of items the cache contains. I'm not concerned with a templatized, generic structure; it can be specific to the type.

I know how to make an LRU cache and bound it by size (e.g. see https://www.boost.org/doc/libs/1_70_0/boost/compute/detail/lru_cache.hpp), so the bounding by byte size, not the LRU algorithm itself, is the crux of the question.

Let's say I have a structure like this:

struct MyItem {
   std::string some_id;
   std::uint64 some_value;
   std::map<std::uint32_t, MyOtherItem> some_map;
}

And I want to create an LRU cache with a basic interface like this (I'm using std::optional as a placeholder for negative caching so I can store std::nullopt for a key to cache the fact that I know it doesn't exist):

class LruCache {
   LruCache(std::uint64_t max_size_bytes);

   void Put(const std::string& key, const std::optional<MyItem> &entity);
   std::optional<MyItem> Get(const std::string& key);
   void Delete(const std::string& key);
}

The interface is not written in stone; I'm open to suggestions there too, but the parts that I'm most interested in are:

At runtime (literally at cache put time), how do I know how big (in bytes) an instance of MyItem is?
How do I allocate the max_size_bytes cache limit? Do I allocate the cached block of memory up front and try to add/remove from that? Or do I keep a "total_bytes" counter class member that I just tick up and down as I add and remove items?

Thank you in advance for all of your suggestions!

A large portion of `MyItem` is going to reside on heap. What's the point of bounding it by bytes in that case? — Tanveer Badar, Jul 19 '20 at 20:39
The ultimate goal is for the overall memory usage of the executable to be predictable. Forcing a bound on how much of the overall memory the cache can use seemed like a good way to help with that. Is that a bad way to think about it? — Brent Writes Code, Jul 19 '20 at 20:42
Write your own allocator (that's the last template parameter of standard library containers). — n. m. could be an AI, Jul 19 '20 at 21:12
What exactly is the problem you are trying to solve? Post the problem, not the question you have. — Tanveer Badar, Jul 20 '20 at 05:25

rustyx · Accepted Answer · 2020-07-20T18:42:04.913

The main problem here is there's no "deep" sizeof in C++. You have to keep track of the object size manually by recursively estimating it. This answer has some hints for that. You can use a custom allocator with STL containers to help with the estimation (see this answer for an example).

Alternatively you can use an 3rd-party heap allocator that supports arenas (e.g. jemalloc) and allocate map elements in a specific arena. Then you should be able to just check the allocated size of that arena.

Once you know the size, you can maintain, for example, a linked list of iterators pointing to the map elements (or simply a list of keys like Boost lru_cache does) + a running total, and when adding a new element, first delete from the head of the list until the running total fits within max_size_bytes (essentially the LRU algorithm).

Finally, I advise against re-implementing heap allocation from one big chunk of memory - it's going to be a lot of work and even when done, it won't perform. A delegating allocator to e.g. jemalloc or tcmalloc on the other hand, should be easy to realize.

Thank you for the links! It turns out my understanding of how to calculate proper object sizes was the real issue here. Some of the custom allocator stuff allowed me to figure out the overhead introduced by the STL structures (e.g. a node in a std::list or std::unordered_map). I put jemalloc on my "to look at" list. — Brent Writes Code, Jul 22 '20 at 18:01

score 1 · Answer 2 · answered Jul 19 '20 at 21:30

At runtime (literally at cache put time), how do I know how big (in bytes) an instance of MyItem is?

The size of an instance of MyItem is sizeof(MyItem). However, if MyItem has pointers or containers, sizeof(MyItem) won't count how much bytes are used by all the memory pointed to. If you want to know that, you have to dig deeper. For example, if MyOtherItem is a POD type that doesn't contain pointers to even more memory, then you could approximate the size of MyItem by:

MyItem item = ...;
auto size = sizeof item + some_map.size() * (sizeof uint32_t + sizeof MyOtherItem);

But even that won't be exact, since a std::map might allocate some more memory for bookkeeping. If MyOtherItem contains pointers or containers, you have to iterate over all of them and calculate their sizes.

How do I allocate the max_size_bytes cache limit? Do I allocate the cached block of memory up front and try to add/remove from that? Or do I keep a "total_bytes" counter class member that I just tick up and down as I add and remove items?

It depends on how it is used. Do you expect to always fill it to the maximum size? If so, it is most efficient to allocate all memory up front. If not, then you should keep track of the current size and adjust it as you add and remove items. Have a look at how containers like std::vector work; they keep track of how much memory is allocated, and how much of the allocated memory is actually used. You can use reserve() to increase the allocated memory without actually storing any new elements.

Keeping track of the exact amount of memory used can be hard. Maybe you don't need to do that at all. Why not just limit the amount of elements in the LRU cache? It is much easier to reason about that. How many elements do you need to cache to ensure you program runs efficiently?

Thank you for the feedback. It's much appreciated! – Brent Writes Code Jul 22 '20 at 18:01 — Brent Writes Code, Jul 22 '20 at 18:01

How can I create an LRU cache bounded by size in bytes (rather than number of items) in modern C++?

2 Answers2