现代硬件算法[5.2]: 性能统计

Instrumentation是一种相当乏味的分析方法，尤其是当你对程序的多个片段感兴趣时。即使它可以被工具部分自动化，但由于其固有的开销，它仍然无法帮助你收集一些细粒度的统计信息。

另一种侵入性较小的分析方法是以随机间隔中断程序的执行，并查看指令指针的位置。指针停在每个函数块中的次数与执行这些函数所花费的总时间大致成比例。你还可以通过这种方式获得一些其他有用的信息，比如通过检查调用堆栈来找出哪些函数被哪些函数调用。

原则上，这可以通过运行一个带有gdb和ctrl+c的程序来实现，但现代CPU和操作系统为这种类型的分析方法提供了特殊的实用程序。

硬件事件

硬件性能计数器是内置在微处理器中的特殊寄存器，可以存储某些硬件相关活动的计数。它们可以很容易地被添加到微芯片上，因为它们基本上只是带有激活连线的二进制计数器。

每个性能计数器都连接到一个很大的电路子集，可以配置为在特定硬件事件（如分支预测失误或缓存未命中）时递增。你可以在程序开始时重置计数器，然后运行，并在结束时输出其存储值，该值将等于某个事件在整个执行过程中被触发的确切次数。

你还可以通过多路复用来跟踪多个事件，也就是说，以均匀的间隔停止程序并重新配置计数器。这种情况下的结果不会是精确的，而是一个统计近似值。这里的一个细节是，它的准确性不能通过简单地增加采样频率来提高，因为它会对性能产生很大影响，从而影响分布的准确性，所以要收集多个统计数据，你需要运行该程序更长的时间。

总体而言，事件驱动的统计分析通常是诊断性能问题的最有效、最简单的方法。

使用perf进行分析

利用上述事件采样技术的性能分析工具称为统计分析器（statistical profilers）。这样的工具有很多，我们在本书中主要使用的是 perf ，它是Linux内核附带的统计分析器。在非Linux系统上，你可以使用英特尔的 VTune ，它提供了大致相同的功能。它是免费的，但是需要专利授权，你需要每90天刷新一次社区许可证，而perf是完全免费的。

Perf是一个命令行应用程序，它根据程序的实时执行生成报告。它不需要源代码，可以分析的应用程序范围很广，包括那些涉及多个进程和与操作系统交互的应用程序。

为了解释，我编写了一个小程序，创建了一个由一百万个随机整数组成的数组，对其进行排序，然后对其进行一百万次二分查找：

void setup() {
    for (int i = 0; i < n; i++)
        a[i] = rand();
    std::sort(a, a + n);
}

int query() {
    int checksum = 0;
    for (int i = 0; i < n; i++) {
        int idx = std::lower_bound(a, a + n, rand()) - a;
        checksum += idx;
    }
    return checksum;
}

编译后（g++ -O3 -march=native example.cc -o run），我们可以使用perf stat ./run来运行它，它在执行过程中输出基本性能事件的计数：

Performance counter stats for './run':

       646.07 msec task-clock:u               # 0.997 CPUs utilized          
            0      context-switches:u         # 0.000 K/sec                  
            0      cpu-migrations:u           # 0.000 K/sec                  
        1,096      page-faults:u              # 0.002 M/sec                  
  852,125,255      cycles:u                   # 1.319 GHz (83.35%)
   28,475,954      stalled-cycles-frontend:u  # 3.34% frontend cycles idle (83.30%)
   10,460,937      stalled-cycles-backend:u   # 1.23% backend cycles idle (83.28%)
  479,175,388      instructions:u             # 0.56  insn per cycle         
                                              # 0.06  stalled cycles per insn (83.28%)
  122,705,572      branches:u                 # 189.925 M/sec (83.32%)
   19,229,451      branch-misses:u            # 15.67% of all branches (83.47%)

  0.647801770 seconds time elapsed
  0.647278000 seconds user
  0.000000000 seconds sys

你可以看到，在1.32 GHz的有效时钟频率下，执行耗时0.53秒或852M个周期，执行了479M条指令。还有122.7M个分支，其中15.7%是预测错误的。

你可以使用perf list获取所有支持的事件的列表，然后使用-e选项指定所需特定事件的列表。例如，对于诊断二分查找，我们主要关心缓存未命中：

> perf stat -e cache-references,cache-misses ./run

91,002,054      cache-references:u                                          
44,991,746      cache-misses:u      # 49.440 % of all cache refs

perf stat本身只是为整个程序设置性能计数器。它可以告诉你分支预测失误的总数，但不会告诉你它们发生在哪里，更别提为什么会发生了。

要尝试我们之前讨论过的“中断程序”的方法，我们会用到perf record ＜cmd＞，它记录分析数据并将其转储为perf.data文件，之后我们可以调用perf report进行查看。我强烈建议你自己去尝试一下，因为perf record命令是交互式的，有丰富的内容，但为了照顾那些现在没办法尝试的人，我会尽我所能去描述清楚。

当你执行perf report时，它首先显示一个类似top的交互式报告，该报告告诉你每个函数花费了多少时间：

Overhead  Command  Shared Object        Symbol
  63.08%  run      run                  [.] query
  24.98%  run      run                  [.] std::__introsort_loop<...>
   5.02%  run      libc-2.33.so         [.] __random
   3.43%  run      run                  [.] setup
   1.95%  run      libc-2.33.so         [.] __random_r
   0.80%  run      libc-2.33.so         [.] rand

请注意，对于每个函数，只列出了它的开销，而没有列出总运行时间（例如，setup包括std:：__introsort_loop，但它自己的开销只占3.43%）。有一些工具可以从性能报告中构建火焰图，使结果更清晰。你还需要考虑可能的内联，显然std::lower_bound就是这种情况。Perf还会跟踪共享库（如libc），通常还会跟踪所有其他派生进程：如果你愿意，你可以用Perf跟踪一个web浏览器的启动，观察这个过程中发生了什么。

接下来，你可以“放大”这些函数中的任何一个，它将展示一个带有对应性能热图的反汇编代码。下面是query的汇编代码示例：

      │20: → call   rand@plt
      │      mov    %r12,%rsi
      │      mov    %eax,%edi
      │      mov    $0xf4240,%eax
      │      nop    
      │30:   test   %rax,%rax
 4.57 │    ↓ jle    52
      │35:   mov    %rax,%rdx
 0.52 │      sar    %rdx
 0.33 │      lea    (%rsi,%rdx,4),%rcx
 4.30 │      cmp    (%rcx),%edi
65.39 │    ↓ jle    b0
 0.07 │      sub    %rdx,%rax
 9.32 │      lea    0x4(%rcx),%rsi
 0.06 │      dec    %rax
 1.37 │      test   %rax,%rax
 1.11 │    ↑ jg     35
      │52:   sub    %r12,%rsi
 2.22 │      sar    $0x2,%rsi
 0.33 │      add    %esi,%ebp
 0.20 │      dec    %ebx
      │    ↑ jne    20