# 練習41：將 Cachegrind 和 Callgrind 用于性能調優 > 原文：[Exercise 41: Using Cachegrind And Callgrind For Performance Tuning](http://c.learncodethehardway.org/book/ex41.html) > 譯者：[飛龍](https://github.com/wizardforcel) 這個練習中，我打算上一節速成課，內容是使用`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`，之后得到了這個信息： ```sh $ 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`對每一行做注解。你可以通過運行下面的命令來得到注解后的源文件： ```sh $ 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](http://kcachegrind.sourceforge.net/html/Home.html)的神奇的GUI工具，用于分析`callgrind` 和 `cachegrind`的輸出。我使用Linux或BSD電腦上工作時幾乎都會使用它，并且我實際上為了使用`KCachegrind`而切換到Linux來編寫代碼。 教會你如何使用是這個練習之外的內容，你需要在這個練習之后自己學習如何用它。輸出幾乎是相同的，除了`KCachegrind`可以讓你做這些： + 圖形化地瀏覽源碼和執行次數，并使用各種排序來搜索可優化的東西。 + 分析不同的圖表，來可視化地觀察什么占據了大多數時間，以及它調用了什么。 + 查看真實的匯編機器碼輸出，使你能夠看到實際的指令，給你更多的線索。 + 可視化地顯示源碼中的循環和分支的跳躍方式，便于你更容易地找到優化代碼的方法。 你應該在獲取、安裝和玩轉`KCachegrind`上花一些時間。 ## 附加題 + 閱讀[ callgrind 手冊頁](http://valgrind.org/docs/manual/cl-manual.html)并且嘗試一些高級選項。 + 閱讀[ cachegrind 手冊頁](http://valgrind.org/docs/manual/cg-manual.html)并且也嘗試一些高級選項。 + 在所有單元測試上使用`callgrind` 和 `cachegrind`，看看你能否找到可優化的地方。你找到一些預料之外的事情了嗎？如果沒有，你可能觀察地不夠仔細。 + 使用 KCachegrind 并且觀察它和我這里的輸出有什么不同。 + 現在使用這些工具來完成練習40的附加題和改進部分。