代码之家 › 专栏 › 技术社区 › DzedCPT

简单C程序的混乱缓存行为

perf memory caching performance c

8

DzedCPT · 技术社区 · 7 年前

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

为此,我使用性能命令:

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

要记录以下简单操作的缓存未命中率 C 计划:

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/(每个缓存线的字数),这肯定大于1/2。为什么缓存未命中率如此之高?
我对内存的(有限的)理解表明,按列主顺序遍历数组会导致更糟糕的缓存行为,但我得到的结果却恰恰相反。发生什么事?

1 回复 | 直到 7 年前

1

2

Andriy Berestovskyy 7 年前

答案很简单:编译器优化您的赋值。下面是代码的反汇编情况:

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

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

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

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

16              arr[i * N + j] = 10.0;
17          }
18      }
19      return 0;
20  }
   0x00000000004004ee <+24>:    mov    $0x0,%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    $0x8,%rsp

11      int N = 10000;
12      volatile double *arr = malloc(sizeof(double) * N * N);
   0x000000000040052a <+4>: mov    $0x2faf0800,%edi
   0x000000000040052f <+9>: callq  0x400410 <malloc@plt>
   0x0000000000400534 <+14>:    mov    $0x0,%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    $0x1,%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    $0x5f5e100,%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    $0x0,%eax
   0x000000000040056c <+70>:    add    $0x8,%rsp
   0x0000000000400570 <+74>:    retq

而且还有更多的缓存未命中。

只运行一次测试可能会得到非常嘈杂的结果。你应该进行几次测量并取一个中位数。有一些基准框架,比如googlebenchmark,请看一看。

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