2

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

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

下面是 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::set这些概念中处于什么位置？

4

1 回答 1

1

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

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

这种开销当然会影响缓存效率，当元素很小时，即使您从未使用过它，您也会情不自禁地将其放入 L1 缓存中。当您一次性分配数组时，每个数组元素的开销为零。而且你有一个硬性保证，每个元素在内存中是相邻的，因此顺序迭代数组将与内存子系统可以支持的一样快。

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

所以是的，在这个人为的场景中，你很可能会领先于大阵列。

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

于 2013-11-01T15:38:34.050 回答