c++ - 堆分配如何影响硬件缓存命中率？

Question

我做了一些测试来研究堆分配和硬件缓存行为之间的关系。实证结果很有启发性，但也可能具有误导性，尤其是在不同平台和复杂/不确定的用例之间。

我对两种情况感兴趣:批量分配(实现自定义内存池)或后续分配(信任操作系统)。

下面是 C++ 中的两个示例分配测试

//Consequent allocations
for(auto i = 1000000000; i > 0; i--)
    int *ptr = new int(0);
    store_ptr_in_some_container(ptr);

//////////////////////////////////////

//Bulk allocation
int *ptr = new int[1000000000];
distribute_indices_to_owners(ptr, 1000000000);

我的问题是:

• 当我为只读操作遍历所有这些时，将如何缓存 CPU 中的内存可能会自行分区吗？

• 尽管有实证结果(明显的性能提升 解决方案)，当其他一些相对非常小的时候会发生什么 批量分配会覆盖以前分配的缓存吗？

• 为了避免代码膨胀和保持代码可读性，将两者混合是否合理？

• std::vector、std::list、std::map、std::设置这些概念的立场？

Answer 1

通用堆分配器有一组困难的问题需要解决。它需要确保释放的内存可以回收，必须支持任意大小的分配并强烈避免堆碎片。

这将始终包括每次分配的额外开销，分配器需要的簿记。它至少必须存储 block 的大小，以便在释放分配时可以正确地回收它。并且几乎总是指向堆段中下一个 block 的偏移量或指针，分配大小通常大于请求以避免碎片问题。

这个开销当然会影响缓存效率，当元素很小的时候，你会情不自禁地把它放到一级缓存中，即使你从不使用它。当您一次性分配数组时，每个数组元素的开销都是零。而且您很难保证每个元素在内存中都是相邻的，因此按顺序迭代数组将与内存子系统可以支持的速度一样快。

通用分配器的情况并非如此，对于如此小的分配，开销可能为 100% 到 200%。当程序运行了一段时间并且数组元素被重新分配时，也不能保证顺序访问。值得注意的是，您的大数组无法支持的操作，因此请注意不要自动假设分配不能长时间释放的巨型数组必然更好。

所以是的，在这种人工场景中，您很可能会领先于大阵列。

从引用的集合类列表中抓取 std::list，它的缓存效率非常低，因为下一个元素通常位于内存中完全随机的位置。 std::vector 是最好的，只是引擎盖下的一个数组。 std::map 通常是用红黑树完成的，尽可能合理地完成，但您使用的访问模式当然很重要。 std::set 也一样。