练习40：二叉搜索树
练习42：栈和队列

笨办法学C (Learn C The Hard Way)

练习41：将 Cachegrind 和 Callgrind 用于性能调优

原文：Exercise 41: Using Cachegrind And Callgrind For Performance Tuning

译者：飞龙

这个练习中，我打算上一节速成课，内容是使用Valgrind的两个工具callgrind和cachegrind。这两个工具会分析你程序的执行，并且告诉你哪一部分运行缓慢。这些结果非常精确，因为Valgrind的工作方式有助于你解决一些问题，比如执行过多的代码行，热点，内容访问问题，甚至是CPU的缓存未命中。

为了做这个练习，我打算使用bstree_tests单元测试，你之前用于寻找能提升算法的地方。你需要确保你这些程序的版本没有任何valgrind错误，并且和我的代码非常相似，因为我会使用我的代码的转储来谈论cachegrind和callgrind如何工作。

运行 Callgrind

为了运行Callgrind，你需要向valgrind传入--tool=callgrind选项，之后它会产生callgrind.out.PID文件（其中PID为所运行程序的进程PID）。一旦你这样运行了，你就可以使用一个叫做callgrind_annotate的工具分析callgrind.out文件，它会告诉你哪个函数运行中使用了最多的指令。下面是个例子，我在bstree_tests上运行了callgrind，之后得到了这个信息：

$ valgrind --dsymutil=yes --tool=callgrind tests/bstree_tests
...
$ callgrind_annotate callgrind.out.1232
--------------------------------------------------------------------------------
Profile data file 'callgrind.out.1232' (creator: callgrind-3.7.0.SVN)
--------------------------------------------------------------------------------
I1 cache:
D1 cache:
LL cache:
Timerange: Basic block 0 - 1098689
Trigger: Program termination
Profiled target:  tests/bstree_tests (PID 1232, part 1)
Events recorded:  Ir
Events shown:     Ir
Event sort order: Ir
Thresholds:       99
Include dirs:     
User annotated:   
Auto-annotation:  off

--------------------------------------------------------------------------------
       Ir
--------------------------------------------------------------------------------
4,605,808  PROGRAM TOTALS

--------------------------------------------------------------------------------
       Ir  file:function
--------------------------------------------------------------------------------
  670,486  src/lcthw/bstrlib.c:bstrcmp [tests/bstree_tests]
  194,377  src/lcthw/bstree.c:BSTree_get [tests/bstree_tests]
   65,580  src/lcthw/bstree.c:default_compare [tests/bstree_tests]
   16,338  src/lcthw/bstree.c:BSTree_delete [tests/bstree_tests]
   13,000  src/lcthw/bstrlib.c:bformat [tests/bstree_tests]
   11,000  src/lcthw/bstrlib.c:bfromcstralloc [tests/bstree_tests]
    7,774  src/lcthw/bstree.c:BSTree_set [tests/bstree_tests]
    5,800  src/lcthw/bstrlib.c:bdestroy [tests/bstree_tests]
    2,323  src/lcthw/bstree.c:BSTreeNode_create [tests/bstree_tests]
    1,183  /private/tmp/pkg-build/coregrind//vg_preloaded.c:vg_cleanup_env [/usr/local/lib/valgrind/vgpreload_core-amd64-darwin.so]

$

我已经移除了单元测试和valgrind输出，因为它们对这个练习没有用。你应该看到了callgrind_anotate输出，它向你展示了每个函数所运行的指令数量（valgrind中叫做Ir），由高到低排序。你通常可以忽略头文件的数据，直接跳到函数列表。

注

如果你获取到一堆“???:Image”的行，并且它们不是你程序中的东西，那么你读到的是OS的垃圾。只需要在末尾添加| grep -v "???"来过滤掉它们。

我现在可以对这个输出做个简短的分解，来找出下一步观察什么：

  • 每一行都列出了Ir序号和执行它们的file:function。Ir是指令数量，并且如果它越少就越快。这里有些复杂，但是首先要着眼于Ir。
  • 解决这个程序的方式是观察最上面的函数，之后看看你首先可以改进哪一个。这里，我可以改进bstrcmp或者BStree_get。可能以BStree_get开始更容易些。
  • 这些函数的一部分由单元测试调用，所以我可以忽略它们。类似bformat，bfromcstralloc和 bdestroy就是这样的函数。
  • 我也可以找到我可以简单地避免调用的函数。例如，或许我可以假设BSTree仅仅处理bstring键，之后我可以不使用回调系统，并且完全移除default_compare。

到目前为止，我只知道我打算改进BSTree_get，并且不是因为BSTree_get执行慢。这是分析的第二阶段。

Callgrind 注解源文件

下一步我使用callgrind_annotate输出bstree.c文件，并且使用所带有的Ir对每一行做注解。你可以通过运行下面的命令来得到注解后的源文件：

$ callgrind_annotate callgrind.out.1232 src/lcthw/bstree.c
...

你的输出会是这个源文件的一个较大的转储，但是我会将它们剪切成包含BSTree_get和BSTree_getnode的部分：

--------------------------------------------------------------------------------
-- User-annotated source: src/lcthw/bstree.c
--------------------------------------------------------------------------------
    Ir


 2,453  static inline BSTreeNode *BSTree_getnode(BSTree *map, BSTreeNode *node, void *key)
     .  {
61,853      int cmp = map->compare(node->key, key);
663,908  => src/lcthw/bstree.c:default_compare (14850x)
     .
14,850      if(cmp == 0) {
     .          return node;
24,794      } else if(cmp < 0) {
30,623          if(node->left) {
     .              return BSTree_getnode(map, node->left, key);
     .          } else {
     .              return NULL;
     .          }
     .      } else {
13,146          if(node->right) {
     .              return BSTree_getnode(map, node->right, key);
     .          } else {
     .              return NULL;
     .          }
     .      }
     .  }
     .
     .  void *BSTree_get(BSTree *map, void *key)
 4,912  {
24,557      if(map->root == NULL) {
14,736          return NULL;
     .      } else {
     .          BSTreeNode *node = BSTree_getnode(map, map->root, key);
 2,453          return node == NULL ? NULL : node->data;
     .      }
     .  }

每一行都显示它的Ir（指令）数量，或者一个点（.）来表示它并不重要。我所要找的就是一些热点，或者带有巨大数值的Ir的行，它能够被优化掉。这里，第十行的输出表明，BSTree_getnode开销非常大的原因是它调用了default_comapre，它又调用了bstrcmp。我已经知道了bstrcmp是性能最差的函数，所以如果我想要改进BSTree_getnode的速度，我应该首先解决掉它。

之后我以相同方式查看bstrcmp：

 98,370  int bstrcmp (const_bstring b0, const_bstring b1) {
      .  int i, v, n;
      .
196,740     if (b0 == NULL || b1 == NULL || b0->data == NULL || b1->data == NULL ||
 32,790             b0->slen < 0 || b1->slen < 0) return SHRT_MIN;
 65,580     n = b0->slen; if (n > b1->slen) n = b1->slen;
 89,449     if (b0->slen == b1->slen && (b0->data == b1->data || b0->slen == 0))
      .             return BSTR_OK;
      .
 23,915     for (i = 0; i < n; i ++) {
163,642             v = ((char) b0->data[i]) - ((char) b1->data[i]);
      .             if (v != 0) return v;
      .             if (b0->data[i] == (unsigned char) '\0') return BSTR_OK;
      .     }
      .
      .     if (b0->slen > n) return 1;
      .     if (b1->slen > n) return -1;
      .     return BSTR_OK;
      .  }

输出中让我预料之外的事情就是bstrcmp最糟糕的一行并不是我想象中的字符比较。对于内存访问，顶部的防御性if语句将所有可能的无效变量都检查了一遍。与第十七行比较字符的语句相比，这个if语句进行了多于两倍的内存访问。如果我要优化bstcmp，我会完全把它去掉，或者在其它一些地方来执行它。

另一种选择是将这个检查改为assert，它只在开发时的运行中存在，之后在发布时把它去掉。我没有足够的证明来表明这行代码不适于这个数据结构，所以我可以证明移除它是可行的。

然而，我并不想弱化这个函数的防御性，来得到一些性能。在真实的性能优化环境，我会简单地把它放到列表中，之后挖掘程序中能得到的其它收益。

调优之道

我们应该忽略微小的效率，对于97%的情况：过早优化是万恶之源。

-- 高德纳

在我看来，这个引述似乎忽略了一个关于性能调优的重点。在高德纳的话中，当你做性能调优时，如果你过早去做它，可能会导致各种问题。根据他的话，优化应该执行于“稍晚的某个时间”，或者这只是我的猜测。谁知道呢。

我打算澄清这个引述并不是完全错误，而是忽略了某些东西，并且我打算给出我的引述。你可以引用我的这段话：

使用证据来寻找最大的优化并花费最少的精力。

-- 泽德 A. 肖

你什么时候优化并不重要，但是你需要弄清楚你的优化是否真正能改进软件，以及需要投入多少精力来实现它。通过证据你就可以找到代码中的位置，用一点点精力就能取得最大的提升。通常这些地方都是一些愚蠢的决定，就像bstrcmp试图检查任何东西不为NULL一样。

在某个特定时间点上，代码中需要调优的地方只剩下极其微小的优化，比如重新组织if语句，或者类似达夫设备这样的特殊循环。这时候，你应该停止优化，因为这是一个好机会，你可以通过重新设计软件并且避免这些事情来获得更多收益。

这是一些只想做优化的程序员没有看到的事情。许多时候，把一件事情做快的最好方法就是寻找避免它们的办法。在上面的分析中，我不打算优化bstrcmp，我会寻找一个不使用它的方法。也许我可以使用一种哈希算法来执行可排序的哈希计算而不是始终使用bstrcmp。也许我可以通过首先尝试第一个字符，如果它们不匹配就没必要调用bstrcmp。

如果在此之后你根本不能重新设计，那么就开始寻找微小的优化，但是要始终确保它们能够提升速度。要记住目标是使用最少的精力尽可能得到最大的效果。

使用 KCachegrind

这个练习最后一部分就是向你介绍一个叫做KCachegrind的神奇的GUI工具，用于分析callgrind 和 cachegrind的输出。我使用Linux或BSD电脑上工作时几乎都会使用它，并且我实际上为了使用KCachegrind而切换到Linux来编写代码。

教会你如何使用是这个练习之外的内容，你需要在这个练习之后自己学习如何用它。输出几乎是相同的，除了KCachegrind可以让你做这些：

  • 图形化地浏览源码和执行次数，并使用各种排序来搜索可优化的东西。
  • 分析不同的图表，来可视化地观察什么占据了大多数时间，以及它调用了什么。
  • 查看真实的汇编机器码输出，使你能够看到实际的指令，给你更多的线索。
  • 可视化地显示源码中的循环和分支的跳跃方式，便于你更容易地找到优化代码的方法。

你应该在获取、安装和玩转KCachegrind上花一些时间。

附加题

  • 阅读 callgrind 手册页并且尝试一些高级选项。
  • 阅读 cachegrind 手册页并且也尝试一些高级选项。
  • 在所有单元测试上使用callgrind 和 cachegrind，看看你能否找到可优化的地方。你找到一些预料之外的事情了吗？如果没有，你可能观察地不够仔细。
  • 使用 KCachegrind 并且观察它和我这里的输出有什么不同。
  • 现在使用这些工具来完成练习40的附加题和改进部分。
书籍推荐