在 Linux 上使用 Perf 做效能分析(入門篇)
¶ 簡介
透過效能分析工具 (Profiler)，我們可以得知更多關於軟體的運行資訊，像是花了多少記憶體、多少 CPU Cycles、多少 Cache Misses、I/O 處理時間等等，這些資訊對我們去找到程式效能瓶頸很有幫助。想辦法找到那裡讓程式變慢，進而最大化效能，便是我們做效能分析的最大目的。
本文將介紹 Linux 上的 perf 效能分析工具，藉由一個簡單的程式範例，示範如何使用 perf 去分析一隻程式，我們將會發現使用分析工具時能更輕易的發現問題根源。本文參考 Gabriel Krisman Bertaz 寫的 Performance analysis in Linux。
本文可以搭配我的教學影片：
¶ 一個 Branch Prediction 的範例
Stack Overflow 上有一個很火的問題「Why is processing a sorted array faster than processing an unsorted array?」。
問題的 Code 如下：
test.cc：
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// 測試用陣列
const int arr_len = 32768;
int data[arr_len];
for (int c = 0; c < arr_len; ++c)
data[c] = std::rand() % 256;
// std::sort(data, data + arr_len); // 是否排序
long long sum = 0;
for (int i = 0; i < 30000; ++i)
{
for (int c = 0; c < arr_len; ++c)
{
if (data[c] >= 128) { // 故意選 256 一半
sum += data[c];
}
}
}
std::cout << "sum = " << sum << std::endl;
}
首先我們先編譯未排序版本：
$ g++ test.cc -o unsort
接著我們把 sort 那行取消註解，再編譯一次：
$ g++ test.cc -o sort
先來看看執行時間：
$ time ./unsort
real 0m5.671s
$ time ./sort
real 0m1.932s
問題大意是說 data 如果排列過後，上面這段程式碼反而更快，如同我們實驗結果。我們知道排序的複雜度是 $O(NlogN)$，所以應該會比沒排直接跑的 $O(N)$ 還慢，但結果是排序後反而更快。
就結論來說，我們知道這個結果是因為 CPU 會做 Branch Prediction。白話來說就是上次如果 if 是 true，下次就先猜也是 true，CPU 可以藉由先猜來偷跑，猜對了的話就可以跑更快；但相對的猜錯的話偷跑的東西通通要丟掉，反而更浪費時間，稱為 Branch Miss(詳細原理可以參考「計算機組織」)。所以 Branch Prediction 算是一種雙面刃，如果可以一直讓條件判斷有相同結果就可以進而加速程式，反之判斷一直反覆不定就會導致一直「猜測」錯誤而變慢，因此在上面程式碼中排列過的版本反而比較快，因為猜測錯誤只會發生一次，就是在 data 剛好在 128 附近的位置，在那之前全部會是 false，而後都會是 true。
¶ Perf 效能分析工具
想要找到一段程式碼的問題通常不容易，就以上面的程式範例來說，假設我們朝演算法去分析就會走錯路，實際問題其實在計算機組織的原理。光是一段簡單的程式碼就讓我們可能找不到原因，更甭說碰到一個大的程式，裡面有各種問題存在，可能是演算法、記憶體快取、CPU 指令、網路連線、I/O 等等，這時我們需要一個分析程式來幫助我們。
Linux 上其實有很多工具可以使用：
不過本文將針對 perf 做介紹，並用上面程式來示範假設我們還不知道問題是因為 Branch Miss，如何用 perf 找到問題。
你可以用下面指令在 Ubuntu 上裝 perf：
$ sudo apt install linux-tools-$(uname -r) linux-tools-generic
或是你也可以考慮自己從 Linux Kernel 編譯 perf 來用：
$ sudo apt install flex bison libelf-dev libunwind-dev libaudit-dev libslang2-dev libdw-dev
$ git clone https://github.com/torvalds/linux --depth=1
$ cd linux/tools/perf/
$ make
$ make install
$ sudo cp perf /usr/bin
$ perf
安裝完 perf 後，你可能會需要設定系統權限，預設應該會使 perf 權限不足：
$ sudo su # As Root
$ sysctl -w kernel.perf_event_paranoid=-1
$ echo 0 > /proc/sys/kernel/kptr_restrict
$ exit
¶ 使用 perf
接著我們要測試的程式，為了讓 perf 能用，我們要加上 -g3 參數開啟除錯模式。
一樣是編譯 test.cc，首先是沒排序：
$ g++ test.cc -g3 -o unsort
接著是編譯有排序版本：
$ g++ test.cc -g3 -o sort
¶ Perf Record
我們現在想要知道為甚麼 ./unsort 跑得比較慢，我們可以透過 perf record 來記錄程式執行的資訊。
$ perf record ./unsort
這樣 perf 會將 ./unsort 跑的資料記錄在 perf.data 中，perf 其他指令可以用來讀取這個紀錄檔。
¶ Perf Annotate
我們可以用 perf annotate 來看結果：
$ perf annotate
perf 會自動跳到花費比較多的區塊，如上圖所示，左邊是執行時間比例，右邊是程式碼對照的 Assembly Code。你可以用上下方向鍵移動，或用 h 來看操作說明。
其實從這個 Assembly 時間比例就可以看出端倪，通常我們會去看哪邊花最多時間，然後去研究背後原因。這邊的關鍵是 d8 和 cf 這兩行，addl 其實就是在做 sum += data[c]，所以這兩行分別代表 Branch Prediction 猜對和猜錯的路徑。
這張圖「箭頭」標註的是 Branch Prediction 猜對的路徑，可以看到 d8 行占比幾乎是 0.0%。
這張圖「箭頭」標註的是 Branch Prediction 猜錯的路徑，可以看到 cf 行占比幾乎是 27.7%。
所以其實就可以發現整隻程式因為 Branch Misses 浪費很多時間。
這邊我們可以偷偷看一下 ./sort 的結果：
$ perf record ./sort && perf annotate
因為不會有 Branch Miss，可以觀察到 ee 和 f7 的 addl 基本上沒占多少時間。
¶ Perf Stat
直接看 Assembly 其實滿花時間的，如果想要直接「掌握大局」，可以考慮用 perf stat。
# 未排序版本
$ perf stat ./unsort
sum = 94479480000
Performance counter stats for './unsort':
5,671.51 msec task-clock # 1.000 CPUs utilized
24 context-switches # 0.004 K/sec
0 cpu-migrations # 0.000 K/sec
147 page-faults # 0.026 K/sec
20,366,870,320 cycles # 3.591 GHz
11,328,534,095 instructions # 0.56 insn per cycle
2,951,455,487 branches # 520.401 M/sec
467,676,925 branch-misses # 15.85% of all branches
5.671777216 seconds time elapsed
5.671781000 seconds user
0.000000000 seconds sys
# 排序版本
$ perf stat ./sort
sum = 94479480000
Performance counter stats for './sort':
1,927.09 msec task-clock # 1.000 CPUs utilized
6 context-switches # 0.003 K/sec
0 cpu-migrations # 0.000 K/sec
146 page-faults # 0.076 K/sec
6,917,745,957 cycles # 3.590 GHz
11,345,543,927 instructions # 1.64 insn per cycle
2,954,388,946 branches # 1533.084 M/sec
268,192 branch-misses # 0.01% of all branches
1.927654198 seconds time elapsed
1.927349000 seconds user
0.000000000 seconds sys
perf stat 可以直接看到統計資料，如果有很高的 Context Switch、Page Fault、Branch Miss 都代表程式本身效能有待優化。
以 unsort 為例可以看到 Branch Miss 特別高 (排序版本會幾乎是 0)，這時我們就可以去看原本的程式哪邊有條件判斷，然後根據 Annotate 的時間比例，就可以快速找到問題點。另外從 Cycle 上我們也可以發現兩個版本差了三倍之多。
更多 perf 的用法可以參考 Brendan Gregg 的「perf Examples」。另外這個 HackMD 的筆記也挺不錯的。
¶ 結論
本文介紹 perf 的簡單用法，用簡單的範例程式示範如何去觀察效能並找出可能的問題原因。
我們常常因為程式效能不佳而需要分析效能，但找到問題的過程往往不容易，一段程式碼效能不佳可能是演算法與資料結構的問題，可能是作業系統 System Call 導致，也可能是因為處理器架構的關係。如同本文的程式範例，說明了演算法的複雜度不代表真實跑出來的速度，往往還需要去考慮作業系統或是硬體架構。善用效能分析工具才能讓我們更快找到問題點。
