一个简单 C 程序的令人困惑的缓存行为

Question

我正在试验一个程序，看看它的缓存行为是否符合我的概念理解。

为此，我使用 Perf 命令：

perf stat -e cache-misses ./a.out

记录以下简单C程序的cache-miss率：

int main() {
    int N = 10000;
    double *arr = malloc(sizeof(double) * N * N);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++){
            arr[i * N + j] = 10.0;
        }
    }
    return 0;
}

我得到的缓存未命中率为 50.212%。如果我按如下方式更改数组访问模式：

arr[j * N + i]

我知道缓存未命中率为 22.206%。

这些结果令我惊讶。

50.212% 的缓存未命中率对于这样一个具有非常规律的内存访问模式的简单程序来说似乎非常高。我希望这更接近 1/(num-words-per-cache-line)，这绝对大于 1/2。为什么缓存未命中率这么高？
我对内存的（有限）理解表明，以列优先顺序遍历数组应该会导致更糟糕的缓存行为，但我得到的结果表明相反。怎么回事？

Answer 1

答案很简单：编译器优化了你的赋值。以下是您的代码的反汇编结果：

10  int main() {
   0x00000000004004d6 <+0>: mov    [=10=]x2710,%edx
   0x00000000004004db <+5>: jmp    0x4004e7 <main+17>

15          for(int j = 0; j < N; j++){
   0x00000000004004dd <+7>: sub    [=10=]x1,%eax
   0x00000000004004e0 <+10>:    jne    0x4004dd <main+7>

14      for(int i = 0; i < N; i++) {
   0x00000000004004e2 <+12>:    sub    [=10=]x1,%edx
   0x00000000004004e5 <+15>:    je     0x4004ee <main+24>

10  int main() {
   0x00000000004004e7 <+17>:    mov    [=10=]x2710,%eax
   0x00000000004004ec <+22>:    jmp    0x4004dd <main+7>

16              arr[i * N + j] = 10.0;
17          }
18      }
19      return 0;
20  }
   0x00000000004004ee <+24>:    mov    [=10=]x0,%eax
   0x00000000004004f3 <+29>:    retq

如您所见，没有为行 arr[i * N + j] = 10.0; 生成汇编程序指令，因此您使用 perf 观察到的那些缓存未命中是无关的。

修复非常简单。只需将 volatile 添加到指针声明中，强制编译器生成赋值，即：

volatile double *arr = malloc(sizeof(double) * N * N);

现在的反汇编：

10  int main() {
   0x0000000000400526 <+0>: sub    [=12=]x8,%rsp

11      int N = 10000;
12      volatile double *arr = malloc(sizeof(double) * N * N);
   0x000000000040052a <+4>: mov    [=12=]x2faf0800,%edi
   0x000000000040052f <+9>: callq  0x400410 <malloc@plt>
   0x0000000000400534 <+14>:    mov    [=12=]x0,%edx

16              arr[i * N + j] = 10.0;
   0x0000000000400539 <+19>:    movsd  0xc7(%rip),%xmm0        # 0x400608
   0x0000000000400541 <+27>:    jmp    0x40055f <main+57>
   0x0000000000400543 <+29>:    movslq %edx,%rcx
   0x0000000000400546 <+32>:    lea    (%rax,%rcx,8),%rcx
   0x000000000040054a <+36>:    movsd  %xmm0,(%rcx)
   0x000000000040054e <+40>:    add    [=12=]x1,%edx

15          for(int j = 0; j < N; j++){
   0x0000000000400551 <+43>:    cmp    %esi,%edx
   0x0000000000400553 <+45>:    jne    0x400543 <main+29>
   0x0000000000400555 <+47>:    mov    %esi,%edx

14      for(int i = 0; i < N; i++) {
   0x0000000000400557 <+49>:    cmp    [=12=]x5f5e100,%esi
   0x000000000040055d <+55>:    je     0x400567 <main+65>
   0x000000000040055f <+57>:    lea    0x2710(%rdx),%esi
   0x0000000000400565 <+63>:    jmp    0x400543 <main+29>

17          }
18      }
19      return 0;
20  }
   0x0000000000400567 <+65>:    mov    [=12=]x0,%eax
   0x000000000040056c <+70>:    add    [=12=]x8,%rsp
   0x0000000000400570 <+74>:    retq

还有更多的缓存未命中。

运行你只测试一次可能会得到非常嘈杂的结果。您应该运行测量几次并取中值。有基准框架，比如Google Benchmark，所以请看一下。

最后一个。 i * N + j 和 j * N + i 等两种模式很容易被 CPU 预取器识别，因此两种情况下的缓存未命中率应该非常相似...

一个简单 C 程序的令人困惑的缓存行为

Confusing Caching Behaviour of a Simple C Program

c

memory

performance

caching

perf