Cachegrind：为什么会有那么多缓存未命中？

Question

Cachegrind：为什么会有那么多缓存未命中？

c++performanceprofilingcpu-cachecachegrind

5

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

- Andrej Kesely

什么是列图例？什么是 D1mr？ - user7860670

@VTT 来自 http://valgrind.org/docs/manual/cg-manual.html 的内容：`I cache reads (Ir，即执行的指令数)，I1 cache read misses (I1mr) 和 LL cache instruction read misses (ILmr)。D cache reads (Dr，即内存读取次数)，D1 cache read misses (D1mr) 和 LL cache data read misses (DLmr)。D cache writes (Dw，即内存写入次数)，D1 cache write misses (D1mw) 和 LL cache data write misses (DLmw)。` - Andrej Kesely

我在这里没有看到很多未命中的读取。那一行代码...在循环过程中，你肯定会出现一个未命中的缓存（在接近结尾的地方对我来说看起来很有说服力）。与读取次数相比，未命中次数似乎并不那么糟糕（125000/800万+？）我读对了吗？ - Galik

@Galik 虽然看起来不错，但它不是0，所以还不够好 ;) - NathanOliver

1

你有没有试过将循环增量仅设置为“1”，并让优化器自行展开循环以查看其性能如何？（同时使用-O3） - Galik

显示剩余2条评论

3个回答

2

我猜测这是因为向量缓冲区没有对齐到高速缓存线边界。突然的高速缓存未命中标志着我们进入下一行时发生了跳变。因此，我建议检查 v.data() 的值。

- user7860670

@NathanOliver 我认为 OP 可以分配一个字节数组并选择一个对齐的起始位置。或者只需在双精度向量中选择一个对齐的起始位置。 - user7860670

将向量对齐到缓存行边界不会使缓存未命中的位置移动到其他地方吗？当您遍历内存时，您仍然会像以前一样经常遇到缓存未命中吧？ - Galik

1

@Galik 是的，我现在尝试使用double* v = (double *)aligned_alloc(64, COUNT * 8);来分配向量，而不是使用std::vector，缓存未命中出现在counter += v[i+0];这一行。我以为CPU预取器会随着数据的进行而提取数据。 - Andrej Kesely

@Galik 是的，但这种不对齐解释了为什么缓存未命中发生在循环的中间。 - user7860670

@VTT 那么循环能否在不每次迭代都产生缓存失效的情况下编写？还是我运气不好，一切都取决于CPU？ - Andrej Kesely

显示剩余2条评论

1

在我的看法中，如果我们忽略前1M个推回（8Mb…也许你的L2空间不足），这看起来绝对没问题。因此，如果我们假设我们的数据不在任何级别的缓存中，那么每次读取8个双精度数时，您都必须向RAM请求下一个L1行。所以总体而言，您的统计数据看起来很好。您调用QWORD读取1M次，并由于简单的顺序访问模式而生成125k个RAM请求。

- user2713607

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hadi Brais · Accepted Answer

首先检查生成的汇编代码非常重要，因为这是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中。这解释了D1mr和DLmr列中的1。然后在counter += v[i+6];处，又访问了另一行，这在缓存的两个级别中都是未命中。但是，在这种情况下，接下来的7个访问都将是命中的。此时，只有从counter += v[i+6];访问会丢失，并且有125,000次此类访问（1百万/8）。

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