C语言中的矩阵计算

Question

我最近注意到，在C语言中访问矩阵的方式发生微小变化可能会对性能产生很大影响。例如，假设我们有以下两个C代码片段。第一个：

for(i = 0; i < 2048; i++)
{
    for(j = 0; j < 2048; j++) {
            Matrix[i][j] = 9999;    
    }
}

并且还有这个：

for(j = 0; j < 2048; j++)
{
    for(i = 0; i < 2048; i++) {
            Matrix[i][j] = 9999;    
    }
}

第二个版本比第一个版本慢了2倍。为什么？我认为这与内存管理有关：在每个循环中，第一个版本访问相邻的内存位置，而第二个版本必须在每个循环中“跳转”到不同的区域。 这种直觉正确吗？ 另外，如果我将矩阵缩小(例如64x64)，则性能没有差异。为什么？ 我希望有人能提供一个直观和严谨的解释。 顺便说一下，我正在使用Ubuntu 14.04 LTS。

- Peter

---

你的直觉可能是正确的，第一个版本可能更加友好。看一下生成的汇编代码。 - Jabberwocky

@MichaelWalz s/cash/cache - Code-Apprentice

@Code-Apprentice 将/cash/替换为/cache/g - TDk

Answer 1

        for(i=0;i<2048;i++)
        {
                for(j=0;j<2048;j++) {
                        Matrix[i][j]=9999;    
                }
        }

这个表单使用L1、L2和L3高速缓存对齐。当您循环使用j来访问Matrix[i][j]时，元素Matrix[i][0]、Matrix[i][1]等等会按顺序排列在连续地址上（实际上是相差sizeof(Matrix[i][0]))的地址），因此访问Matrix[i][0]时，缓存中也会加载下一个变量Matrix[i][1]。

另一方面，

        for(j=0;j<2048;j++)
        {
                for(i=0;i<2048;i++) {
                        Matrix[i][j]=9999;    
                }
        }

内部循环按顺序访问Matrix[0][j]、Matrix[1][j]等。假设你为数组Matrix[0]分配了2048个条目，那么Matrix[1][j]的地址为Matrix[0][j]+2048*sizeof(Matrix[0][0])。

因此，Matrix[0][j]和Matrix[1][j]在缓存的不同块中，需要从RAM中获取数据而不是从缓存中获取。

在第二种情况下，每次迭代都会访问RAM。

- alinsoar

Answer 2

"就是缓存！就是缓存！"

为了更好地理解，可以将内存视为一个线性数组...

通过定义一个二维数组：

uint8_t Matrix[4][4]

你简单地表达了以下意思：

allocate 16 bytes, and access them as a 2D array, 4x4

这个例子假设有4字节的缓存，为了使事情简单：

如果CPU的缓存只能容纳4字节，那么以[0][0]，[1][0]，[2][0]等形式访问数组会在每次访问时导致缓存未命中 - 需要我们16次访问RAM（这是昂贵的）！

以[0][0]，[0][1]，[0][2]等形式访问数组将允许完全访问2D数组仅需4次缓存未命中。

---

这个例子非常简化 - 现代系统几乎肯定拥有L1和L2缓存，并且许多现代系统现在还实现了L3缓存。

随着离处理器核心越远，内存变得更大而速度变慢。例如：

1. L1缓存（小而非常非常快）
2. L2缓存
3. L3缓存（？）
4. RAM
5. 持久存储（例如：HDD - 巨大但相对非常非常慢）。

- Attie

Answer 3

它与引用位置和CPU高速缓存有关。因此，它主要是处理器特定的（而不是操作系统特定的）。

高速缓存未命中可能非常昂贵（通常情况下，访问DRAM模块上的数据需要数百纳秒 - 足以执行从L1 I-cache读取的一百条机器指令），但访问L1高速缓存只需要一个或几个纳秒）。

也可以阅读this和that。有时（但并非总是），使用__builtin_prefetch可能提高性能（但通常GCC编译器可以更好地优化，通过适当地发出PREFETCH机器指令）。但是，过度或不恰当地使用__builtin_prefetch会降低性能。

在进行基准测试之前，请不要忘记在编译器中启用优化，至少使用gcc -Wall -O2 -march=native进行编译（甚至可以使用-O3代替-O2...）。

- Basile Starynkevitch

Answer 4

重点在于缓存。在后一种情况下，您基本上是按顺序读取内存。在第一种情况下，您需要在每次读取之间进行长跳转。

计算机中有电路会在读取时存储附近的数据，因为很可能很快就会读取附近的数据。您无法控制这些电路的工作方式。您所能做的就是调整您的代码以适应它们的行为。

- klutt