如何从理论上计算超出L1缓存容量的矩阵遍历的缓存缺失次数？

咱们先把所有关键参数掰扯清楚，再分别分析行优先和列优先两种遍历方式的缺失情况：

核心参数梳理 #

• 每个矩阵元素是64位（8字节）
• L1缓存块大小为64B → 每个块能装 64 ÷ 8 = 8 个连续的矩阵元素
• L1总容量16KB → 总共能容纳 16×1024 ÷ 64 = 256 个缓存块
• 256×256矩阵总元素数为65536，总大小512KB，远大于16KB的L1缓存，必然会出现缓存置换

1. 行优先遍历（完全利用空间局部性） #

行优先是按「每行从左到右」的顺序访问元素（比如M[0][0]→M[0][1]→…→M[0][255]→M[1][0]→…）。

这里空间局部性发挥了最大作用：因为矩阵是行主序存储的，每行元素在内存中是连续的。每一次缓存缺失会加载一个64B的块，里面包含8个连续元素——也就是说，每8个元素只会产生1次缺失（第一次访问块内第一个元素时缺失，后面7个元素直接命中缓存）。

具体计算：

• 每行有256个元素 → 每行需要加载 256 ÷ 8 = 32 个缓存块
• 总共有256行 → 总缺失次数 = 256 × 32 = 8192 次

哪怕缓存只能装256个块，行优先访问时，我们处理完一行的块后，下一行的块会自然置换掉不再需要的旧块，不会额外增加缺失次数——因为我们不会回头访问之前行的元素。

2. 列优先遍历（几乎无法利用空间局部性） #

列优先是按「每列从上到下」的顺序访问元素（比如M[0][0]→M[1][0]→…→M[255][0]→M[0][1]→…）。

这种情况下空间局部性基本失效：矩阵是行主序存储的，同一列的元素在内存中是间隔256个元素的位置（间隔2048字节），远大于64B的缓存块大小——也就是说，同一列的相邻元素不在同一个缓存块里。

更关键的是：当我们访问某一列的元素时，每个元素所在的缓存块里包含的是该行的前8个元素（比如M[i][0]所在的块包含M[i][0]到M[i][7]），但我们后续访问其他列的元素时，这些块会被新加载的块置换出去（缓存只有256个块，而每列要加载256个不同的块）。等我们再次需要这个块里的元素（比如访问M[i][1]）时，块已经不在缓存里了，只能重新加载。

具体计算：

• 每个元素的访问都会触发一次缓存缺失（要么块从未被加载过，要么已经被置换）
• 总元素数65536 → 总缺失次数 = 256 × 256 = 65536 次

对你问题的直接解答 #

不能直接把所有未存入缓存的元素都算缺失，必须考虑空间局部性：

• 行优先遍历充分利用了空间局部性，每个缓存块只缺失一次，后续7个元素都命中，缺失次数大幅降低
• 列优先遍历几乎无法利用空间局部性，每个元素的访问都对应一次缓存缺失，缺失次数接近总元素数

内容的提问来源于stack exchange，提问作者chris_lee