Link Time Optimization 小記

Preface

最近一直在鼓搗 Python3 的手動編譯，偶然發現這篇文章介紹 LTO 的文章蠻有趣的，網址在 https://johnysswlab.com/link-time-optimizations-new-way-to-do-compiler-optimizations/ 算是 compiler LTO 概念的入門文章，一開始先跟你說了 compiler 針對一個蠻小的 code snippet 可以做些什麼 optimization，像是 inlining 和 loop merging，以下面這個簡單的程式來說:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int find_min(const int* array, const int len) {
    int min = a[0];
    for (int i = 1; i < len; i++) {
        if (a[i] < min) { min = a[i]; }
    }
    return min;
}
int find_max(const int* array, const int len) {
    int max = a[0];
    for (int i = 1; i < len; i++) {
        if (a[i] > max) { max = a[i]; }
    }
    return max;
}
void main() {
    int* array, len, min, max;
    initialize_array(array, &len);
    min = find_min(array, len);
    max = find_max(array, len);
    ...
}

1. 第一個能做的就是 inlining, 基本上我們透過 inline，可以減少 function call overhead，也就是把 code body 直接展開擺在呼叫他的地方。
2. 接下來是 loop merging，可以看到 find_min & find_max 的長相很像，我們可以把他們合成一個 loop, 這樣可以減少 cpu 的工作量還可以提升 data cache 的 utilization。

1
2
3
4
5
6
7
8
9
10

void main() {
    int* array, len, min, max;
    initialize_array(array, &len);
    min = a[0]; max = a[0];  // compiler inlined find_min and find_max
    for (int i = 0; i < len; i++) {  // compiler merged two loops int one
        if (a[i] < min) { min = a[i]; }
        if (a[i] > max) { max = a[i]; }
    }
    ...
}

但這些 optimization 都有前提就是，他們必須是要在同一個 compliation unit 下面，而 C & C++ 的 compliation unit 是一個一個 file，所以當 find_max & find_min 放在 find.c，而 main 放在 main.c 這些套路就無法被 apply。

Link Time Optimization

Link Time Optimization 是在 linking 後，去看看能不能將這些 optimization 用上，比較常被用上的 optimization 是 inlining & code locality improvements，inlining 前文就提到過了，透過 inlining 後，還可以去做其他的 optimization。

而一般來說，compiler 會嘗試去分析哪些 function 比較常被呼叫，哪些比較少被用，所以他們可以透過這個分析，將 function 擺近一點去改善 code locality，例如 function A 經常呼叫 function B，把他們放靠近一點，是可以有效改善 page faults。

而通常來說做了 LTO 後，程式應該會快一點點，binary size 也會小一點點，這對一些 performance sensitive 的程式算是蠻大的幫助。但缺點也很明顯，用了 LTO 後，整個 compilation 的時間會多蠻多的，也需要用到更多的記憶體，所以 LTO 也不是被很多專案使用。

How to enable LTO

原來 GCC 4.7 就開始支援 LTO 了，基本上只要加上參數 -flto 就可以使用。

Conclusion

作者在文末也做了一些實驗，基本上是可以看到他自己的程式 runtime 提升了 10%，但是整個編譯的時間也暴增，而拿來用在 ffmpeg 上面則是看不到什麼好處，所以對於不同的專案還是 case by case。

LTO & PGO 現在常常被提起，我是感覺大家應該要把這些放進自己的工具箱，如果真的遇到 performance sensitive 的程式，可以拿來重編看看有沒有辦法近一步改善效率。

• Next Post →