簡介

透過效能分析工具 (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。白話來說就是上次如果 iftrue,下次就先猜也是 true,CPU 可以藉由先猜來偷跑,猜對了的話就可以跑更快;但相對的猜錯的話偷跑的東西通通要丟掉,反而更浪費時間,稱為 Branch Miss(詳細原理可以參考「計算機組織」)。所以 Branch Prediction 算是一種雙面刃,如果可以一直讓條件判斷有相同結果就可以進而加速程式,反之判斷一直反覆不定就會導致一直「猜測」錯誤而變慢,因此在上面程式碼中排列過的版本反而比較快,因為猜測錯誤只會發生一次,就是在 data 剛好在 128 附近的位置,在那之前全部會是 false,而後都會是 true

Perf 效能分析工具

想要找到一段程式碼的問題通常不容易,就以上面的程式範例來說,假設我們朝演算法去分析就會走錯路,實際問題其實在計算機組織的原理。光是一段簡單的程式碼就讓我們可能找不到原因,更甭說碰到一個大的程式,裡面有各種問題存在,可能是演算法、記憶體快取、CPU 指令、網路連線、I/O 等等,這時我們需要一個分析程式來幫助我們。

Linux 上其實有很多工具可以使用:

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 annotate

perf 會自動跳到花費比較多的區塊,如上圖所示,左邊是執行時間比例,右邊是程式碼對照的 Assembly Code。你可以用上下方向鍵移動,或用 h 來看操作說明。

其實從這個 Assembly 時間比例就可以看出端倪,通常我們會去看哪邊花最多時間,然後去研究背後原因。這邊的關鍵是 d8cf 這兩行,addl 其實就是在做 sum += data[c],所以這兩行分別代表 Branch Prediction 猜對和猜錯的路徑。

這張圖「箭頭」標註的是 Branch Prediction 猜對的路徑,可以看到 d8 行占比幾乎是 0.0%。
branch prediction 猜對

這張圖「箭頭」標註的是 Branch Prediction 猜對的路徑,可以看到 cf 行占比幾乎是 27.7%。
branch prediction 猜錯

所以其實就可以發現整隻程式因為 Branch Misses 浪費很多時間。

這邊我們可以偷偷看一下 ./sort 的結果:

$ perf record ./sort && perf annotate
sort version's branch prediction

因為不會有 Branch Miss,可以觀察到 eef7addl 基本上沒占多少時間。

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 導致,也可能是因為處理器架構的關係。如同本文的程式範例,說明了演算法的複雜度不代表真實跑出來的速度,往往還需要去考慮作業系統或是硬體架構。善用效能分析工具才能讓我們更快找到問題點。