这个练习中，我打算上一节速成课，内容是使用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.

--------------------------------------------------------------------------------

Profile data file 'callgrind.out.1232' (creator: callgrind-3.7..SVN)

--------------------------------------------------------------------------------

I1 cache:

D1 cache:

LL cache:

Timerange: Basic block  -

Trigger: Program termination

Profiled target:  tests/bstree_tests (PID , part )

Events recorded:  Ir

Events shown:     Ir

Event sort order: Ir

Thresholds:

Include dirs:

User annotated:

Auto-annotation:  off

--------------------------------------------------------------------------------

       Ir

--------------------------------------------------------------------------------

,,  PROGRAM TOTALS

--------------------------------------------------------------------------------

       Ir  file:function

--------------------------------------------------------------------------------

  ,  src/lcthw/bstrlib.c:bstrcmp [tests/bstree_tests]

  ,  src/lcthw/bstree.c:BSTree_get [tests/bstree_tests]

   ,  src/lcthw/bstree.c:default_compare [tests/bstree_tests]

   ,  src/lcthw/bstree.c:BSTree_delete [tests/bstree_tests]

   ,  src/lcthw/bstrlib.c:bformat [tests/bstree_tests]

   ,  src/lcthw/bstrlib.c:bfromcstralloc [tests/bstree_tests]

    ,  src/lcthw/bstree.c:BSTree_set [tests/bstree_tests]

    ,  src/lcthw/bstrlib.c:bdestroy [tests/bstree_tests]

    ,  src/lcthw/bstree.c:BSTreeNode_create [tests/bstree_tests]

    ,  /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. src/lcthw/bstree.c

...

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

--------------------------------------------------------------------------------

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

--------------------------------------------------------------------------------

    Ir

 ,  static inline BSTreeNode *BSTree_getnode(BSTree *map, BSTreeNode *node, void *key)

     .  {

,      int cmp = map->compare(node->key, key);

,  => src/lcthw/bstree.c:default_compare (14850x)

     .

,      if(cmp == ) {

     .          return node;

,      } else if(cmp < ) {

,          if(node->left) {

     .              return BSTree_getnode(map, node->left, key);

     .          } else {

     .              return NULL;

     .          }

     .      } else {

,          if(node->right) {

     .              return BSTree_getnode(map, node->right, key);

     .          } else {

     .              return NULL;

     .          }

     .      }

     .  }

     .

     .  void *BSTree_get(BSTree *map, void *key)

 ,  {

,      if(map->root == NULL) {

,          return NULL;

     .      } else {

     .          BSTreeNode *node = BSTree_getnode(map, map->root, key);

 ,          return node == NULL ? NULL : node->data;

     .      }

     .  }

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

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

 ,  int bstrcmp (const_bstring b0, const_bstring b1) {

      .  int i, v, n;

      .

,     if (b0 == NULL || b1 == NULL || b0->data == NULL || b1->data == NULL ||

 ,             b0->slen <  || b1->slen < ) return SHRT_MIN;

 ,     n = b0->slen; if (n > b1->slen) n = b1->slen;

 ,     if (b0->slen == b1->slen && (b0->data == b1->data || b0->slen == ))

      .             return BSTR_OK;

      .

 ,     for (i = ; i < n; i ++) {

,             v = ((char) b0->data[i]) - ((char) b1->data[i]);

      .             if (v != ) return v;

      .             if (b0->data[i] == (unsigned char) '\0') return BSTR_OK;

      .     }

      .

      .     if (b0->slen > n) return ;

      .     if (b1->slen > n) return -;

      .     return BSTR_OK;

      .  }