自定义分配器能否改善列表的缓存位置？
Can a custom allocator improve cache locality for lists?
这是一个相当假设的问题。
我对 cpu 缓存的工作原理知之甚少。
我知道 cpu 将后续字节加载到缓存中。
由于列表使用 pointers/indirection 进入内存中的随机位置，因此与假设 vector 或数组相比，它的局部性相对较差。
我的问题是：如果我编写一个所有节点的数据彼此相邻的分配器（通过线性分配器），这会改善缓存加载吗？间接寻址仍然存在，但不同节点的数据位于相似的位置。
If I write an allocator where the data of all nodes is next to each other (via linear allocator), will this improve the cache loading?
是的，如果您以从中受益的方式访问对象。 IE。如果您访问序列中的元素。
是和否，但主要倾向于否，至少如果您以可以让您从中得到任何东西的方式使用该列表。
链表的优点是可以在常数时间内插入和删除列表中间的元素（前提是你已经知道你要去的地方insert/delete）。
如果您线性分配对象并将它们线性插入列表并线性访问它们，是的，您会在局部性方面得到改进。问题是，如果您要以这种方式使用数据，您不妨将其放入向量中并完成它。
如果你在列表中的任意位置进行插入和删除，即使你最初是按线性顺序分配节点，你很快也会导致列表的顺序不再符合分配的顺序。
所以是的，你 可以 在某些情况下获得良好的局部性——但这些情况基本上是你永远不会利用列表的特性来实现它首先有用。
这是一个相当假设的问题。
我对 cpu 缓存的工作原理知之甚少。
我知道 cpu 将后续字节加载到缓存中。
由于列表使用 pointers/indirection 进入内存中的随机位置，因此与假设 vector 或数组相比，它的局部性相对较差。
我的问题是：如果我编写一个所有节点的数据彼此相邻的分配器（通过线性分配器），这会改善缓存加载吗？间接寻址仍然存在，但不同节点的数据位于相似的位置。
If I write an allocator where the data of all nodes is next to each other (via linear allocator), will this improve the cache loading?
是的，如果您以从中受益的方式访问对象。 IE。如果您访问序列中的元素。
是和否，但主要倾向于否，至少如果您以可以让您从中得到任何东西的方式使用该列表。
链表的优点是可以在常数时间内插入和删除列表中间的元素（前提是你已经知道你要去的地方insert/delete）。
如果您线性分配对象并将它们线性插入列表并线性访问它们，是的，您会在局部性方面得到改进。问题是，如果您要以这种方式使用数据，您不妨将其放入向量中并完成它。
如果你在列表中的任意位置进行插入和删除，即使你最初是按线性顺序分配节点，你很快也会导致列表的顺序不再符合分配的顺序。
所以是的，你 可以 在某些情况下获得良好的局部性——但这些情况基本上是你永远不会利用列表的特性来实现它首先有用。