展开链表的最佳块大小
Optimal block size for unrolled linked lists
我正在学习基本数据结构，到目前为止已经展开了链表。我有一本书说，如果我使每个块中的元素数量最多达到一个缓存行的大小，我将从改进的内存局部性中获得更好的缓存性能。我有两个问题。
首先，使它恰好与高速缓存行一样大是最优的，还是更小的不可分割的大小更好？
其次，我在 this post 中发现 L1/2/3 缓存的行大小为 64 字节。我只是想确保这适用于所有 i7 型号？我有一个 2014 年年中的 MBP，并试图创建一个最适合我的系统的展开链表。是否有任何终端命令来检查缓存行大小？
展开链表中节点中的元素都被访问得非常快1.
缓存行中的字节都可以非常快速地访问。
我们可以看到这里的类比，展开的链表可以将项目压缩到连续的内存区域，从而使它们对缓存更友好。
要了解为什么节点大小大于缓存行可能是个问题，请考虑具有缓存（具有任何关联性）且只有一行大小 S 的架构.
还考虑一个节点大小为 2S.
的展开链表
最后分析一下算法的cache misses
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 并重复分析，我们将看到只需要加载缓存。
使节点小于缓存行也可以，一些节点最终可能会共享同一条行，但通常不会有什么坏处。
然而，这将使用更多行而不是列表中的元素总数，因为每个元素都有自己的地址并且它们不一定靠近在一起。
在极限if S=1我们有一个普通的链表。
到目前为止，所有不太老的英特尔 CPU 都有 64 字节缓存行。
不过，这很可能会改变。
要查看您的 CPU 缓存信息，您可以参考这个问题：finding L2 cache size in Linux2。
归结为使用sudo dmidecode -t cache。
1感谢数组用于存储元素，允许随机访问。
2 事实上所有缓存级别。
我正在学习基本数据结构，到目前为止已经展开了链表。我有一本书说，如果我使每个块中的元素数量最多达到一个缓存行的大小，我将从改进的内存局部性中获得更好的缓存性能。我有两个问题。
首先，使它恰好与高速缓存行一样大是最优的，还是更小的不可分割的大小更好？
其次，我在 this post 中发现 L1/2/3 缓存的行大小为 64 字节。我只是想确保这适用于所有 i7 型号？我有一个 2014 年年中的 MBP，并试图创建一个最适合我的系统的展开链表。是否有任何终端命令来检查缓存行大小？
展开链表中节点中的元素都被访问得非常快1.
缓存行中的字节都可以非常快速地访问。
我们可以看到这里的类比，展开的链表可以将项目压缩到连续的内存区域，从而使它们对缓存更友好。
要了解为什么节点大小大于缓存行可能是个问题，请考虑具有缓存（具有任何关联性）且只有一行大小 S 的架构.
还考虑一个节点大小为 2S.
的展开链表
最后分析一下算法的cache misses
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 并重复分析，我们将看到只需要加载缓存。
使节点小于缓存行也可以，一些节点最终可能会共享同一条行，但通常不会有什么坏处。 然而，这将使用更多行而不是列表中的元素总数，因为每个元素都有自己的地址并且它们不一定靠近在一起。 在极限if S=1我们有一个普通的链表。
到目前为止，所有不太老的英特尔 CPU 都有 64 字节缓存行。
不过，这很可能会改变。
要查看您的 CPU 缓存信息，您可以参考这个问题：finding L2 cache size in Linux2。
归结为使用sudo dmidecode -t cache。
1感谢数组用于存储元素，允许随机访问。
2 事实上所有缓存级别。