程序模拟分析

性能分析的另外一种方法（或者说一组方法），并不是通过实际运行程序来收集数据，而是通过使用专门的工具模拟程序应该发生的情况来分析。

这类分析器有许多种类，它们在模拟计算的哪个方面上有所不同。在这篇文章中，我们将重点关注缓存和分支预测，并使用Cachegrind进行分析，它是Valgrind的一部分，Valgrind是一个用于检测内存泄漏和一般内存调试的成熟工具。

使用Cachegrind进行性能分析

Cachegrind本质上是检查二进制文件中的“感兴趣的”指令：执行内存读/写和条件/间接跳转的指令，并将它们替换为用软件数据结构模拟相应硬件操作的代码。因此，它不需要访问源代码，可以与已编译的程序一起工作，并且可以像下面这样在任何程序上运行：

valgrind --tool=cachegrind --branch-sim=yes ./run#       也模拟分支预测                         ^   ^ 任何命令，不一定是一个进程

它对所有涉及的二进制文件进行插桩，运行它们，并输出一个类似于perf stat的摘要：

I   refs:      483,664,426I1  misses:          1,858LLi misses:          1,788I1  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，统一的）缓存，其特性是从系统中推断出来的。它不以任何方式限制你，因为你也可以从命令行设置它们，例如，模拟L2缓存：--LL=<大小>,<关联度>,<行大小>。

到目前为止，它似乎只是减慢了我们的程序，并没有提供perf stat无法提供的任何信息。为了获得不仅仅是摘要信息，我们可以检查一个特殊的包含分析信息的文件，它默认在同一目录下以cachegrind.out.<pid>命名。它是人类可读的，但预期通过cg_annotate命令读取：

cg_annotate cachegrind.out.4159404 --show=Dr,D1mr,DLmr,Bc,Bcm#                                    ^ 我们只对数据读取和分支感兴趣

首先它显示了运行期间使用的参数，包括缓存系统的特性：

I1 cache:         32768 B, 64 B, 8-way associativeD1 cache:         32768 B, 64 B, 8-way associativeLL cache:         8388608 B, 64 B, direct-mapped

它没有完全正确获取L3缓存：它不是统一的（总共8M，但单个核心只能看到4M）并且是16路组相联的，但我们现在将忽略这一点。

接下来，它输出一个与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_r18,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

你可以看到在排序阶段有很多分支预测错误，以及在二分查找期间有很多L1缓存未命中和分支预测错误。我们无法通过perf获得这些信息——它只会为整个程序提供这些计数。

Cachegrind的另一个伟大特性是对源代码进行逐行注解。为此，你需要用调试信息编译程序（-g）并且要么明确告诉cg_annotate注解哪些源文件，要么只是传递--auto=yes选项，这样它就可以注解它能够到达的所有内容（包括标准库源代码）。

因此，整个源代码到分析过程将如下进行：

g++ -O3 -g sort-and-search.cc -o runvalgrind --tool=cachegrind --branch-sim=yes --cachegrind-out-file=cachegrind.out ./runcg_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;         .         .    .          .         .  }

不幸的是，Cachegrind只跟踪内存访问和分支。当瓶颈由其他原因引起时，我们需要其他模拟工具。