c++ - 自定义分配器可以改善列表的缓存局部性吗？

Question

这是一个相当假设的问题。

我对 cpu 缓存如何工作的了解有限。

我知道 CPU 会将后续字节加载到缓存中。

vector由于列表使用指向内存中随机位置的指针/间接，因此与假设或数组相比，它的局部性相对较差。

我的问题是：如果我编写一个所有节点的数据彼此相邻的分配器（通过线性分配器），这会改善缓存加载吗？间接性仍然存在，但不同节点的数据位于相似的位置。

Answer 1

是也不是，但大多倾向于否，至少如果你使用列表的方式可以让你从中得到任何东西。

链表的优点是能够在恒定时间内在列表中间插入和删除元素（前提是您已经知道要插入/删除的点）。

如果您线性分配对象并将它们线性插入列表并线性访问它们，是的，您将获得局部性的改进。问题是，如果您要以这种方式使用数据，您不妨将其放入向量中并完成处理。

如果您在列表中的任意位置执行插入和删除操作，即使您最初以线性顺序分配节点，您很快就会发现列表的顺序不再与分配顺序匹配。

所以是的，在某些情况下你可以获得良好的局部性——但这些情况基本上是你从不利用列表的特性，使其首先有用。

Answer 2

如果我编写一个分配器，其中所有节点的数据彼此相邻（通过线性分配器），这会改善缓存加载吗？

是的，如果您以从中受益的方式访问对象。即，如果您访问序列中的元素。