c++ - Cachegrind:为什么有这么多缓存未命中？

Question

我目前正在学习 Linux 下的各种分析和性能实用程序，尤其是 valgrind/cachegrind。

我有以下玩具程序:

#include <iostream>
#include <vector>

int
main() {
    const unsigned int COUNT = 1000000;

    std::vector<double> v;

    for(int i=0;i<COUNT;i++) {
        v.push_back(i);
    }

    double counter = 0;
    for(int i=0;i<COUNT;i+=8) {
        counter += v[i+0];
        counter += v[i+1];
        counter += v[i+2];
        counter += v[i+3];
        counter += v[i+4];
        counter += v[i+5];
        counter += v[i+6];
        counter += v[i+7];
    }

    std::cout << counter << std::endl;
}

用 g++ -O2 -g main.cpp 编译这个程序并运行 valgrind --tool=cachegrind ./a.out，然后 cg_annotate cachegrind。 out.31694 --auto=yes 产生以下结果:

    --------------------------------------------------------------------------------
-- Auto-annotated source: /home/andrej/Data/projects/pokusy/dod.cpp
--------------------------------------------------------------------------------
       Ir I1mr ILmr        Dr    D1mr    DLmr        Dw D1mw DLmw 

        .    .    .         .       .       .         .    .    .  #include <iostream>
        .    .    .         .       .       .         .    .    .  #include <vector>
        .    .    .         .       .       .         .    .    .  
        .    .    .         .       .       .         .    .    .  int
        7    1    1         1       0       0         4    0    0  main() {
        .    .    .         .       .       .         .    .    .      const unsigned int COUNT = 1000000;
        .    .    .         .       .       .         .    .    .  
        .    .    .         .       .       .         .    .    .      std::vector<double> v;
        .    .    .         .       .       .         .    .    .  
5,000,000    0    0 1,999,999       0       0         0    0    0      for(int i=0;i<COUNT;i++) {
3,000,000    0    0         0       0       0 1,000,000    0    0          v.push_back(i);
        .    .    .         .       .       .         .    .    .      }
        .    .    .         .       .       .         .    .    .  
        3    0    0         0       0       0         0    0    0      double counter = 0;
  250,000    0    0         0       0       0         0    0    0      for(int i=0;i<COUNT;i+=8) {
  250,000    0    0   125,000       1       1         0    0    0          counter += v[i+0];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+1];
  125,000    1    1   125,000       0       0         0    0    0          counter += v[i+2];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+3];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+4];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+5];
  125,000    0    0   125,000 125,000 125,000         0    0    0          counter += v[i+6];
  125,000    0    0   125,000       0       0         0    0    0          counter += v[i+7];
        .    .    .         .       .       .         .    .    .      }
        .    .    .         .       .       .         .    .    .  
        .    .    .         .       .       .         .    .    .      std::cout << counter << std::endl;
       11    0    0         6       1       1         0    0    0  }

我担心的是这一行:

125,000    0    0   125,000 125,000 125,000         0    0    0          counter += v[i+6];

为什么这一行有这么多缓存未命中？数据在连续内存中，每次迭代我读取 64 字节的数据(假设缓存行长 64 字节)。

我在 Ubuntu Linux 18.04.1、内核 4.19、g++ 7.3.0 上运行这个程序。电脑是AMD 2400G。

Answer 1

首先检查生成的汇编代码很重要，因为这就是 cachegrind 将要模拟的内容。您感兴趣的循环被编译成以下代码:

.L28:
addsd xmm0, QWORD PTR [rax]
add rax, 64
addsd xmm0, QWORD PTR [rax-56]
addsd xmm0, QWORD PTR [rax-48]
addsd xmm0, QWORD PTR [rax-40]
addsd xmm0, QWORD PTR [rax-32]
addsd xmm0, QWORD PTR [rax-24]
addsd xmm0, QWORD PTR [rax-16]
addsd xmm0, QWORD PTR [rax-8]
cmp rdx, rax
jne .L28

每次迭代有 8 次读取访问，每次访问的大小为 8 字节。在 C++ 中，保证每个元素都是 8 字节对齐的，但是每次迭代最多可以访问两个缓存行，具体取决于 v vector 数组的地址。 cachegrind 使用动态二进制检测来获取每个内存访问的地址，并应用其缓存层次结构模型来确定访问在层次结构中的每个级别是命中还是未命中(尽管它仅支持 L1 和 LLC)。在这个特定的实例中，碰巧在 counter += v[i+6]; 处访问了一个新的缓存行。然后，接下来的 7 次访问将针对相同的 64 字节缓存行。访问新缓存行的源代码行不会影响 cachegrind 报告的未命中总数。它只会告诉您不同的源代码行会导致许多未命中。

请注意，cachegrind 根据其运行的机器模拟了一个非常简化的缓存层次结构。在这种情况下，它是 AMD 2400G，它在所有高速缓存级别都有 64 字节的行大小。此外，L3 的大小为 4MB。但由于总数组大小为 8MB，因此以下循环:

for(int i=0;i<COUNT;i++) {
    v.push_back(i);
}

将只在 LLC 中保留数组的后半部分。现在，在计算 counter 的第二个循环的第一次迭代中，访问的第一行将不在 L1 或 LLC 中。这解释了 D1mr 和 DLmr 列中的 1。然后在counter += v[i+6];处，又访问了一行，这也是两级缓存的miss。但是，在这种情况下，接下来的 7 次访问都将被命中。此时，只有来自 counter += v[i+6]; 的访问会丢失，并且有 125,000 个这样的访问(100 万/8)。

请注意，cachegrind 只是一个模拟器，在真实处理器上实际发生的情况很可能非常不同。例如，在我的 Haswell 处理器上，通过使用 perf，所有代码(两个循环)中的 L1D 未命中总数仅为 65,796。因此 cachegrind 可能会显着高估或低估未命中和命中计数。