c++ - 分配/释放大量小对象的策略

Question

我正在研究某种缓存算法，这在一定程度上具有挑战性。 基本上，它需要分配很多小对象(双数组，1 到 256 个元素)，对象可以通过映射值访问，map[key] = array。初始化数组的时间可能相当长，一般超过 10,000 个 cpu 周期。

很多我的意思是总共大约千兆字节。可能需要根据需要弹出/推送对象，通常是在随机位置，一次一个对象。对象的生命周期通常很长，几分钟或更长时间，但是，对象可能会在程序运行期间多次分配/取消分配。

什么是避免内存碎片的好策略，同时仍然保持合理的分配释放速度？

我正在使用 C++，所以我可以使用 new 和 malloc。 谢谢。

我知道网站上有类似的问题，Efficiently allocating many short-lived small objects ，有些不同，线程安全对我来说不是直接的问题。

我的开发平台是Intel Xeon，linux操作系统。 理想情况下，我也想在 PPC Linux 上工作，但这对我来说不是最重要的。

Answer 1

创建一个有槽的分配器:

分配器是用许多内存页创建的，每个内存页大小相等(512k、256k，应根据您的使用调整大小)。

对象第一次向此分配器请求内存时，它会分配一个页面。分配页面包括将其从空闲列表中删除(不搜索，所有页面大小相同)和设置将分配到该页面上的对象的大小。通常，此大小是通过获取请求的大小并将其四舍五入为最接近的 2 的幂来计算的。相同大小的后续分配只需要一点指针数学运算并增加页面上的对象数。

避免了碎片化，因为插槽的大小都相同，并且可以在后续分配时重新填充。效率得以保持(在某些情况下得到提高)，因为每个分配都没有 memheader(这在分配较小时会产生很大差异，一旦分配变大，此分配器就会开始浪费近 50% 的可用内存)。

分配和释放都可以在恒定时间内执行(无需在空闲列表中搜索正确的插槽)。关于释放的唯一棘手部分是你通常不希望在分配之前有一个 memheader，所以你必须自己弄清楚页面和页面中的索引......今天是星期六，我没有喝咖啡所以我没有关于这样做的任何好的建议，不过从释放的地址中很容易弄清楚。

编辑:这个答案有点啰嗦。一如既往boost有你的支持。