c++ - 如何在现代 C++ 中创建以字节大小(而不是项目数)为界的 LRU 缓存？

Question

我目前正在使用 C++17，我正在寻找一种实现 LRU 缓存的方法，但它是否受缓存内容的字节大小(例如 100MB)的限制，而不是缓存包含的项目数.我不关心模板化的通用结构；它可以特定于类型。
我知道如何制作 LRU 缓存并按大小限制它(例如，参见 https://www.boost.org/doc/libs/1_70_0/boost/compute/detail/lru_cache.hpp )，因此按字节大小限制，而不是 LRU 算法本身，是问题的症结所在。
假设我有这样的结构:

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

我想用这样的基本接口(interface)创建一个 LRU 缓存(我使用 std::optional 作为负缓存的占位符，所以我可以存储 std::nullopt 作为一个键来缓存我知道它不存在的事实):

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);
}

界面不是一成不变的；我也愿意接受那里的建议，但我最感兴趣的部分是:

在运行时(字面意思是缓存放置时间)，我如何知道 MyItem 的实例有多大(以字节为单位)是？

如何分配 max_size_bytes缓存限制？我是否预先分配缓存的内存块并尝试从中添加/删除？或者我是否保留一个“total_bytes”计数器类成员，我只是在添加和删除项目时上下打勾？

预先感谢您的所有建议!

Answer 1

这里的主要问题是没有“深”sizeof在 C++ 中。您必须通过递归估计来手动跟踪对象大小。 This answer对此有一些提示。您可以使用带有 STL 容器的自定义分配器来帮助进行估算(参见 this answer 示例)。
或者，您可以使用支持竞技场的第 3 方堆分配器(例如 jemalloc )并在特定竞技场中分配 map 元素。然后您应该能够检查该竞技场的分配大小。
一旦知道大小，您就可以维护，例如，iterators 的链表。指向 map 元素(或简单的键列表，如 Boost lru_cache 所做的)+ 运行总数，当添加新元素时，首先从列表的头部删除，直到运行总数适合 max_size_bytes (本质上是 LRU 算法)。
最后，我建议不要从一大块内存中重新实现堆分配——这将是很多工作，即使完成，它也不会执行。一个委托(delegate)分配器，例如另一方面，jemalloc 或 tcmalloc 应该很容易实现。