我相信您正在查看的是计算机内存层次结构中参考位置的影响。
通常,计算机内存被分为具有不同性能特征的不同类型(这通常称为内存层次结构)。最快的内存在处理器的寄存器中,(通常)可以在单个时钟周期内访问和读取。但是,这些寄存器通常只有少数几个(通常不超过 1KB)。另一方面,计算机的主内存很大(比如 8GB),但访问速度要慢得多。为了提高性能,计算机通常在物理上被构造成具有多级缓存在处理器和主存储器之间。这些缓存比寄存器慢,但比主内存快得多,因此,如果您执行在缓存中查找某些内容的内存访问,它往往比必须转到主内存时快得多(通常在 5-25 倍之间)快点)。访问内存时,处理器首先检查内存缓存中的该值,然后再返回主内存以读取该值。如果您始终如一地访问缓存中的值,那么您最终将获得比跳过时更好的性能内存,随机访问值。
大多数程序的编写方式是,如果将内存中的单个字节读入内存,程序随后也会从该内存区域周围读取多个不同的值。因此,这些缓存通常被设计成当您从内存中读取单个值时,该单个值周围的一块内存(通常在 1KB 到 1MB 之间)也会被拉入缓存中。这样,如果您的程序读取附近的值,它们已经在缓存中,您不必转到主内存。
现在,最后一个细节 - 在 C/C++ 中,数组以行优先顺序存储,这意味着矩阵的单行中的所有值彼此相邻存储。因此,在内存中,数组看起来像第一行,然后是第二行,然后是第三行,等等。
鉴于此,让我们看看您的代码。第一个版本如下所示:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
现在,让我们看一下最里面的代码行。在每次迭代中,k 的值都在变化增加。这意味着在运行最内层循环时,循环的每次迭代都可能在加载 的值时出现缓存未命中b[k][j]
。这样做的原因是因为矩阵以行优先顺序存储,每次增加 k 时,您都会跳过矩阵的整行并跳到内存中更远,可能远远超过您缓存的值. 但是,您在查找时不会错过c[i][j]
(因为i
和j
相同),也不会错过a[i][k]
,因为这些值是按行优先顺序排列的,并且如果 的值a[i][k]
是从上一次迭代中缓存的,那么 的值a[i][k]
此迭代中的读取来自相邻的内存位置。因此,在最内层循环的每次迭代中,您都可能发生一次缓存未命中。
但考虑第二个版本:
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
for (int j = 0; j < n; j++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
现在,由于j
每次迭代都在增加,让我们考虑一下在最里面的语句中可能有多少缓存未命中。因为这些值是行优先顺序的,所以 的值c[i][j]
很可能在缓存中,因为c[i][j]
来自前一次迭代的值也很可能被缓存并准备好被读取。同样,b[k][j]
可能已缓存,并且由于i
并且k
没有更改,因此也a[i][k]
已缓存了机会。这意味着在内部循环的每次迭代中,您很可能没有缓存未命中。
总的来说,这意味着代码的第二个版本不太可能在循环的每次迭代中出现缓存未命中,而第一个版本几乎肯定会出现。因此,如您所见,第二个循环可能比第一个循环快。
有趣的是,许多编译器开始提供原型支持,以检测第二版代码比第一版快。有些人会尝试自动重写代码以最大化并行性。如果您有《紫龙书》的副本,第 11 章将讨论这些编译器的工作原理。
此外,您可以使用更复杂的循环进一步优化此循环的性能。例如,一种称为阻塞的技术可用于通过将数组拆分为可以在缓存中更长时间保存的子区域来显着提高性能,然后对这些块使用多个操作来计算整体结果。
希望这可以帮助!