程序仿真

最后一种分析方法（或者更确切地说是一组分析方法）不是通过实际运行程序来收集数据，而是通过使用专用工具模拟程序来分析应该发生的事情。

这种profilers有很多类别，区别在于模拟计算过程中的不同部分。在本文中，我们将重点关注缓存和分支预测，并为此使用Cachegrind，这是Valgrind中一个面向性能分析的部分，Valgrind 是一个有名的内存泄漏检测和内存调试工具。

使用Cachegrind进行性能分析

Cachegrind本质上检查二进制文件中是否有“感兴趣的”指令——执行内存读/写和条件跳转/间接跳转的指令——并用相应的代码替换它们，这些代码使用软件数据结构模拟相应的硬件操作。因此，它不需要访问源代码，可以分析已经编译的程序，并且可以在任何程序上运行，如下所示：

valgrind --tool=cachegrind --branch-sim=yes ./run
#       also simulate branch prediction ^   ^ any command, not necessarily one process

它检测所有涉及的二进制文件，运行它们，并输出类似于perf stat的摘要：

I   refs:      483,664,426
I1  misses:          1,858
LLi misses:          1,788
I1  miss rate:        0.00%
LLi miss rate:        0.00%

D   refs:      115,204,359  (88,016,970 rd   + 27,187,389 wr)
D1  misses:      9,722,664  ( 9,656,463 rd   +     66,201 wr)
LLd misses:         72,587  (     8,496 rd   +     64,091 wr)
D1  miss rate:         8.4% (      11.0%     +        0.2%  )
LLd miss rate:         0.1% (       0.0%     +        0.2%  )

LL refs:         9,724,522  ( 9,658,321 rd   +     66,201 wr)
LL misses:          74,375  (    10,284 rd   +     64,091 wr)
LL miss rate:          0.0% (       0.0%     +        0.2%  )

Branches:       90,575,071  (88,569,738 cond +  2,005,333 ind)
Mispredicts:    19,922,564  (19,921,919 cond +        645 ind)
Mispred rate:         22.0% (      22.5%     +        0.0%   )

我们给 Cachegrind 提供了与上一节完全相同的测试代码：创建一个由一百万个随机整数组成的数组，对其进行排序，然后对其执行一百万次二分查找。Cachegrind 显示的数字与perf大致相同，除了perf测量的内存读取和分支的数量由于预测执行而略有膨胀之外：预测执行确实发生在硬件中，因此会使得硬件计数增加，但会被丢弃，不会影响实际性能，因此在仿真中被忽略。

Cachegrind 只对一级缓存（D1表示数据，I1表示指令）和最后一级缓存（统一用LL表示）进行建模，缓存的规格是从系统中推断出来的。当然你不会因此而受限，因为你也可以通过命令行来设置它们，例如，为二级缓存建模：--LL=<size>,<associativity>,<line-size>。

到目前为止，Cachegrind 所做的似乎只是让我们的程序跑的更慢了，除此之外，并没有为我们提供任何perf stat无法提供的信息。为了从中获得更多信息，我们可以查看一个包含分析信息的特殊文件，默认情况下，Cachegrind会将其dump到同一目录下，并以cachegrind.out.＜pid＞命令。它是可读的，可以通过cg_annotate命令读取：

cg_annotate cachegrind.out.4159404 --show=Dr,D1mr,DLmr,Bc,Bcm
#                                    ^ we are only interested in data reads and branches

首先，它会显示了运行过程中使用的参数，包括缓存系统的规格：

I1 cache:         32768 B, 64 B, 8-way associative
D1 cache:         32768 B, 64 B, 8-way associative
LL cache:         8388608 B, 64 B, direct-mapped

它没有完全正确地使用三级缓存：三级缓存不是统一内存（总共8M，但单个内核只能看到4M），而且是16-way associative的，但我们现在先忽略这一点。

接下来，它输出一个类似于perf report关于每个函数的摘要：

Dr         D1mr      DLmr Bc         Bcm         file:function
--------------------------------------------------------------------------------
19,951,476 8,985,458    3 41,902,938 11,005,530  ???:query()
24,832,125   585,982   65 24,712,356  7,689,480  ???:void std::__introsort_loop<...>
16,000,000        60    3  9,935,484    129,044  ???:random_r
18,000,000         2    1  6,000,000          1  ???:random
 4,690,248    61,999   17  5,690,241  1,081,230  ???:setup()
 2,000,000         0    0          0          0  ???:rand

你可以看到在排序阶段有很多分支预测失误，在二分查找过程中也有很多一级缓存未命中和分支预测失误。我们无法通过perf获得这些信息——它只会告诉我们整个程序的这些计数值。

Cachegrind的另一个很棒的功能是可以对源代码进行逐行注释。为此，你需要带调试信息（-g）编译程序，然后显式地告诉cg_annotate要注释哪些源文件，或者只传递--auto=yes选项，以便它注释所有可以访问的内容（包括标准库源代码）。

因此，基于源代码分析的整个过程如下：

g++ -O3 -g sort-and-search.cc -o run
valgrind --tool=cachegrind --branch-sim=yes --cachegrind-out-file=cachegrind.out ./run
cg_annotate cachegrind.out --auto=yes --show=Dr,D1mr,DLmr,Bc,Bcm

由于glibc实现的可读性不强，为了便于说明，我们将lower_bound替换为自己实现的二分查找，其注释如下：

Dr         D1mr      DLmr Bc         Bcm       
         .         .    .          .         .  int binary_search(int x) {
         0         0    0          0         0      int l = 0, r = n - 1;
         0         0    0 20,951,468 1,031,609      while (l < r) {
         0         0    0          0         0          int m = (l + r) / 2;
19,951,468 8,991,917   63 19,951,468 9,973,904          if (a[m] >= x)
         .         .    .          .         .              r = m;
         .         .    .          .         .          else
         0         0    0          0         0              l = m + 1;
         .         .    .          .         .      }
         .         .    .          .         .      return l;
         .         .    .          .         .  }