数组的前四行占用了缓存的一部分:
|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|...
上面是一个数组的示意图,如同一位应用数学家在纸上写的那样。每个元素由一个(x,y)对组成,即一个“点”。
图示中标记为“o”的四行共包含128个“点”,足以填满1024字节,仅占缓存的四分之一。但请注意:在您的代码中,变量i既是“主”循环计数器,也是数组的“行”索引(如在纸上写的那样)。
那么,让我们再次看一下这个图。您的嵌套循环如何按照图示遍历数组呢?
答案是:显然,您的循环从图示中的顶部行向右移动,其中j(列)是次要循环计数器。然而,正如您所观察到的,该数组是按列存储的。因此,当加载元素[j][i] == [0][0]时,将加载整个缓存行。那么,这个缓存行包含什么?它是图示中标记为“*”的四个元素。
因此,当您的内部循环按照图表遍历数组的顶行时,每次缓存都会缺失,每次获取四个元素。然后对于接下来的三行,全都是命中。
这不容易想到。这是一个好问题,我也不希望您立即理解我的答案,但是如果您仔细考虑我所解释的加载序列,经过一番思考后,应该开始有意义了。
在给定的循环嵌套中,命中率确实为3/4。
进一步讨论
在评论中,您提出了一个很好的后续问题:
您能写一个元素(例如`array[3][14].x`)来进行命中吗?
我可以。`array[j][i] == array[10][5]`将会命中。(`.x`和`.y`都会命中。)
我来解释一下。当
array[j][i] == array[10][4]
时,会错过,但
array[10][5]
、
array[10][6]
和
array[10][7]
最终会被访问到。为什么是“最终”呢?这很重要。虽然我提到的这四个元素都是由缓存硬件一次性加载的,但当访问
array[10][4]
时,你的代码(即CPU)并不会访问
array[10][5]
,而是在程序和CPU接下来访问
array[11][4]
之后才会访问
array[10][5]
。
实际上,程序和CPU只有在稍后才会访问array[10][5]
。
如果你想一想,这其实很合理,因为这就是缓存的作用之一:它们现在静默地将额外的数据作为缓存行加载,以便CPU在以后快速访问这些额外的数据。
附录:FORTRAN/BLAS/LAPACK矩阵排序
在数值计算中,按列而不是按行存储矩阵是标准做法。这被称为“列优先”存储。不幸的是,与早期的Fortran编程语言不同,C编程语言最初并非为数值计算而设计,因此,在C中,要按列存储数组,必须编写
array[column][row] == array[j][i]
——这种表示方法当然颠倒了应用数学家使用铅笔书写的方式。
这是C编程语言的一种特殊情况。这个特殊情况没有数学意义,但在C编程时,你必须记得键入
[j][i]
。[如果你正在使用现在大多已过时的Fortran编程语言,你会键入
(i, j)
,但这不是Fortran。]
列优先存储成为标准的原因与CPU执行标量浮点乘法和加法的顺序有关,当数学/铅笔术语中的矩阵[A]左作用于列向量x时。标准的基本线性代数子程序(BLAS)库(由LAPACK等使用)就是这样工作的。你和我也应该这样工作,不仅因为我们可能需要与BLAS和/或LAPACK进行接口交互,而且从数值上讲,这样更加平稳。
point[j][i].x
,由于空间局部性(在我们的情况下 point = 数组),point[j][i].y
存储在缓存中。 - cellkaarray[0][0].x
,我们将array[0][0].y
,array[0][1].x
,array[0][1].y
,...,array[0][3].x
,array[0][3].y
加载到第一个块中。 - cellka