4

我目前正在学习 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。

4

3 回答 3

4

首先检查生成的汇编代码很重要，因为这就是 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向量数组的地址。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 中。这解释了 1 inD1mr和DLmr列。然后在 处counter += v[i+6];，访问另一行，这也是两级缓存中的未命中。但是，在这种情况下，接下来的 7 次访问都将是命中。此时，只有来自的访问counter += v[i+6];会丢失，并且有 125,000 次这样的访问（100 万 / 8）。

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

于 2018-11-09T20:19:38.780 回答
2

我怀疑这是因为向量缓冲区未在缓存行边界上对齐。那是缓存未命中的突然跳跃标志着我们进入下一行时的一个点。所以我建议检查v.data()价值。

于 2018-11-09T18:55:08.067 回答
1

在我看来，如果我们忘记最初的 1M 后推（8Mb ......好吧，也许你在 L2 中没有足够的空间来处理它），这看起来绝对没问题。因此，如果我们假设我们的数据不在任何级别的缓存中，那么每次您读取 8 个双精度数据时，您都必须向 RAM 询问下一条 L1 行。所以总的来说你的统计数据看起来不错。由于简单的顺序访问模式，您正在调用 QWORD 读取 1M 次并生成 125k 对 RAM 的请求。

于 2019-09-05T22:46:32.863 回答