0

我正在学习基本的数据结构，到目前为止已经展开了链表。我有一本书说，如果我将每个块中的元素数量最多设置为一个缓存行的大小，我将从改进的内存局部性中获得更好的缓存性能。我对此有两个问题。

首先，使其与高速缓存行的大小完全相同是最佳选择，还是任何更小的不可分割的大小都是好的？

其次，我在这篇文章中发现 L1/2/3 缓存的行大小为 64 字节。我只是想确保这适用于所有型号 i7？我有一个 2014 年中期的 MBP，并试图创建一个最适合我的系统的展开链表。是否有任何终端命令来检查缓存行大小？

4

1 回答 1

3

展开链表中节点中的元素都被访问得非常快1。
缓存行中的字节都被非常快地访问。

我们可以在这里看到类比，展开的链表用于将项目压缩到连续的内存区域中，以便它们对缓存更加友好。

要了解为什么节点大小大于高速缓存行可能会成为问题，请考虑具有高速缓存（具有任何关联性）的体系结构，其中只有一条大小为S的行。还要考虑一个节点大小为2S
的展开链表。 最后，让我们分析一下算法的缓存未命中

For each node N
  Let avg = ArithmeticMean(N.items)
  For i = 0 To N.numerOfItems - 1
     N.items[i] = avg

这将节点中每个项目（假设是一个完整节点）的值设置为该节点的算术平均值。

要计算平均值，必须对所有元素求和，访问第一个元素会触发缓存加载 (+1)。在前半部分，从刚刚加载的缓存行中读取元素。
一旦访问后半部分的第一个元素，就需要另一个缓存加载，并刷新旧行（+2）。直到节点结束，第二次加载完成所有未来的访问。
一旦我们得到平均值，前半部分将再次通过随后的缓存加载 (+3) 访问，后半部分的行将很快再次加载 (+4)。

该算法为节点触发 4 次缓存加载。如果我们确定节点S的大小并重复分析，我们将看到只需要缓存加载。

使节点小于缓存线也可以，一些节点最终可能会共享同一条线，但一般不会受到伤害。然而，这将使用更多的行而不是列表中的元素总数，因为每个元素都位于其自己的地址并且它们不一定靠近在一起。如果S=1，我们有一个普通的链表。

到目前为止，所有不太旧的 Intel CPU 都有 64 字节的缓存线。
不过，这可以很好地改变。

要查看您的 CPU 缓存信息，您可以参考这个问题：finding L2 cache size in Linux 2。

它归结为使用sudo dmidecode -t cache。

1感谢数组用于存储元素，允许随机访问。

2对于所有缓存级别事实上。

于 2016-07-14T18:30:23.023 回答