c++ - 我能否将 "force"Cachegrind 分析成一个操作(或行)？

Question

我正在对两种搜索算法的缓存行为进行基准测试，这两种搜索算法使用 Cachegrind 对已排序的项目范围进行操作。我在一个 vector 中有 n 个项目，另一个 vector 包含所有有效索引。我在第二个 vector 上使用 std::random_shuffle，然后对第一个 vector 中的项目执行 n 次成功查找。我正在进行基准测试的函数大致如下所示:

template <typename Iterator>
void lookup_in_random_order(Iterator begin, Iterator end)
{
    const std::size_t N = std::distance(begin, end);
    std::vector<std::size_t> idx(N);
    std::iota(idx.begin(), idx.end(), 0);

    std::srand(std::time(0));
    std::random_shuffle(idx.begin(), idx.end());

    // Warm the cache -- I don't care about measuring this loop.
    for(std::size_t i = 0; i < N; ++i)
        my_search(begin, end, idx[i]);

    std::random_shuffle(idx.begin(), idx.end());

    // This one I would care about!
    for(std::size_t i = 0; i < N; ++i)
    {
        int s = idx[i];
        // Especially this line, of course.
        my_search(begin, end, s);
    }
}

我使用 g++(使用 -g 和 -O2)编译我的代码。我运行 Cachegrind，然后运行 ​​cg_annotate。我得到如下内容:

       Ir I1mr ILmr        Dr    D1mr    DLmr Dw D1mw DLmw
        .    .    .         .       .       .  .    .    .  template <typename Iterator>
       17    2    2         0       0       0  6    0    0  void lookup_in_random_order(Iterator begin, Iterator end)
        .    .    .         .       .       .  .    .    .  {
        .    .    .         .       .       .  .    .    .      const std::size_t N = std::distance(begin, end);
        .    .    .         .       .       .  .    .    .      std::vector<std::size_t> idx(N);
        .    .    .         .       .       .  .    .    .      std::iota(idx.begin(), idx.end(), 0);
        .    .    .         .       .       .  .    .    .      
        4    0    0         0       0       0  2    1    1      std::srand(std::time(0));
        .    .    .         .       .       .  .    .    .      std::random_shuffle(idx.begin(), idx.end());
        .    .    .         .       .       .  .    .    .  
3,145,729    0    0         0       0       0  0    0    0      for(std::size_t i = 0; i < N; ++i)
        .    .    .         .       .       .  .    .    .              my_search(begin, end, idx[i]);
        .    .    .         .       .       .  .    .    .  
        .    .    .         .       .       .  .    .    .      std::random_shuffle(idx.begin(), idx.end());
        .    .    .         .       .       .  .    .    .  
3,145,729    1    1         0       0       0  0    0    0      for(std::size_t i = 0; i < N; ++i)
        .    .    .         .       .       .  .    .    .      {
1,048,575    0    0 1,048,575 132,865 131,065  0    0    0              int s = idx[i];
        .    .    .         .       .       .  .    .    .              my_search(begin, end, s);
        .    .    .         .       .       .  .    .    .      }
        7    0    0         6       1       1  0    0    0  }

出于某种原因，一些线(尤其是最有趣的线!)由点组成。现在，Cachegrind manual说“不适用于一条线的事件由一个点表示。这对于区分不可能发生的事件和可能但没有发生的事件很有用。”

这应该如何解释？我的第一个想法是编译器可能会优化我的搜索。我认为这不可能，因为该程序确实花费了相当多的时间来运行。尽管如此，我还是尝试在不使用 -O2 标志的情况下进行编译，并且在某种意义上它似乎可以工作，现在调用 my_search 的每一行都记录了一些数字(不再有点!)。但是，由于显而易见的原因，这似乎不是正确的方法。

一般来说，有没有一种方法可以告诉 Cachegrind“特别看看这一行，我非常感兴趣它导致了多少缓存未命中”？

Answer 1

我的猜测是，对于 O2，它允许编译器在您看到圆点的地方执行函数的自动内联。 Cachegrind 将看不到内联函数调用，因为调用已消失。尝试“-fno-inline”(Compiler options)

当然，使用和不使用内联，您可能会有不同的缓存性能数字。