这是一个相当假设性的问题。我对CPU缓存的工作原理只有有限的了解。我知道一个cpu会将随后的字节加载到该高速缓存中。由于列表使用指针/间接指向内存中的随机位置，因此与vector或数组相比，它的局部性相对较差。我的问题是：如果我写一个分配器，其中所有节点的数据都是相邻的（通过线性分配器），这会改善该高速缓存的加载吗？间接性仍然存在，但不同节点的数据位于相似的位置。
vector
zaqlnxep1#
是也不是，但大多倾向于否定，至少如果你以一种让你从中得到任何东西的方式使用列表。链表的优点是能够在恒定的时间内插入和删除列表中间的元素（前提是您已经知道要插入/删除的位置）。如果你线性地分配对象，线性地将它们插入到列表中，线性地访问它们，是的，你会在局部性上得到改进。问题是，如果你要以这种方式使用数据，你最好把它放在一个向量中，然后完成它。如果你在列表中的任意位置进行插入和删除，即使你最初是按照线性顺序分配节点的，你很快就会发现列表的顺序不再匹配分配的顺序。在这种情况下，自定义分配器可能还是有一点用处的。至少列表中的节点不会与其他数据混在一起，所以至少可以稍微提高引用的局部性。但是，即使在最好的情况下，这方面的改善也可能是相当小的。所以，是的，在某些情况下你可以得到很好的局部性--但是这些情况基本上是你从来没有利用过列表的特性，这些特性使它首先变得有用。
lztngnrs2#
如果我写一个分配器，其中所有节点的数据都是相邻的（通过线性分配器），这会改善该高速缓存的加载吗？是的，如果你以一种从中受益的方式访问对象。也就是说，如果你访问序列中的元素。
2条答案
按热度按时间zaqlnxep1#
是也不是，但大多倾向于否定，至少如果你以一种让你从中得到任何东西的方式使用列表。
链表的优点是能够在恒定的时间内插入和删除列表中间的元素（前提是您已经知道要插入/删除的位置）。
如果你线性地分配对象，线性地将它们插入到列表中，线性地访问它们，是的，你会在局部性上得到改进。问题是，如果你要以这种方式使用数据，你最好把它放在一个向量中，然后完成它。
如果你在列表中的任意位置进行插入和删除，即使你最初是按照线性顺序分配节点的，你很快就会发现列表的顺序不再匹配分配的顺序。在这种情况下，自定义分配器可能还是有一点用处的。至少列表中的节点不会与其他数据混在一起，所以至少可以稍微提高引用的局部性。但是，即使在最好的情况下，这方面的改善也可能是相当小的。
所以，是的，在某些情况下你可以得到很好的局部性--但是这些情况基本上是你从来没有利用过列表的特性，这些特性使它首先变得有用。
lztngnrs2#
如果我写一个分配器，其中所有节点的数据都是相邻的（通过线性分配器），这会改善该高速缓存的加载吗？
是的，如果你以一种从中受益的方式访问对象。也就是说，如果你访问序列中的元素。