高效能 Golang 程式 — 編譯器優化
前言
近期看到了 high-performance-go-workshop 這篇文章，作者分享很多調教 golang 程式效能的方式，覺得這篇文章寫的很清楚就來翻譯成中文，我也會將文章分成幾個部分翻譯，這篇是翻譯第四章編譯器的優化（Compiler optimizations）
第二章效能比較（Benchmarking）的翻譯：高效能 Golang 程式 — 效能比較
第三章效能測量及分析（Performance Measurement and Profiling）的翻譯：高效能 Golang 程式 — 效能測量及分析
編譯器優化（Compiler Optimizations）
這個章節包含了部分 Go 編譯器優化，例如 Escape analysis、Inlining、Dead code elimination，這些都是在編譯器前端處理，而程式碼仍然是 AST 的格式，然後程式碼會給 SSA 編譯器進行進一步的優化
Go 編譯器的歷史
Go 編譯器大約在 2007 年時作為 Plan9 編譯器 tool chain 的分支開始，當時的編譯器與 Aho 和 Ullman 的 Dragon Book 非常相似
在 2015 年時，Go 的編譯器從 C 轉譯成 Go，想了解為什麼要用 Go 編譯 Go的可以看這份簡報
一年後，Go 1.7 加入了一個基於 SSA 的編譯器後端，以取代先前的 Plan9，新的 SSA 讓編譯器可以更優化程式碼
Escape analysis
在 Go spec 裡沒有提到 heap 和 stack，只在簡介中提到 Garbage Collection（GC），並沒有說明如何實作
Go 的實作可以都將記憶體分配給 heap，不過這將會對 GC 造成很大的負擔，而且也不是正確的做法，多年來 gccgo（go 的編譯器）對 escape analysis 支援有限，所以我們可以認為目前 Go 是在這樣的模式下運行
然而，goroutine 的 stack 是為了更有效儲存區域變數而存在，GC 也不需要回收存在 stack 的變數，因此放在 stack 裡的變數會更有效率
在像 C 和 C++ 的程式語言裡，開發者可以自己選擇變數要分配在 stack 或是 heap，要分配或回收 heap 的記憶體可以用 malloc 和 free，要分配 stack 的記憶體可以用 alloca，錯誤使用這些函數是導致記憶體損壞常見的原因
在 Go 裡，如果變數會在函數外面使用，編譯器會自動將變數移至 heap （escapes to heap）
type Foo struct {
a, b, c, d int
}
func NewFoo() *Foo {
return &Foo{a: 3, b: 1, c: 4, d: 7}
}這個範例 Foo 會在 NewFoo 函數裡分配並移至 heap，Foo 就能在 NewFoo 函數結束後仍能被其他的函數使用
Go 從一開始就會自動分配記憶體的位置，與其說是自動校正倒不如說是一種優化，而在 Go 裡是不可能回傳 stack 變數的記憶體位址
不過編譯器也可以將原先要分配到 heap 上的變數轉而分配到 stack 上，讓我們看這個範例
func Sum() int {
const count = 100
numbers := make([]int, count)
for i := range numbers {
numbers[i] = i + 1
}
var sum int
for _, i := range numbers {
sum += i
}
return sum
}
func main() {
answer := Sum()
fmt.Println(answer)
}呼叫 Sum 函數會回傳 1 到 100 的和
因為 numbers slice 只在 Sum 裡面使用，所以編譯器會將這 100 個正整數分配在 stack 上，stack 而 numbers 的記憶體也會在 Sum 回傳後就釋放
分配在 stack 的記憶體不需要 GC 回收，而分配在 heap 的記憶體則需要
我們可以用 -gcflags=”-m” 來看編譯器的結果
$ go build -gcflags="-m" sum.go
./sum.go:23:13: inlining call to fmt.Println
./sum.go:9:17: make([]int, count) does not escape
./sum.go:23:13: answer escapes to heap
./sum.go:23:13: []interface {} literal does not escape
<autogenerated>:1: .this does not escape第 9 行編譯器判斷 make([]int, count) 不需要移至 heap
第 23 行可以看到因為 answer 為 fmt.Println 的參數關係所以 answer 會移至 heap
fmt.Println 的參數是 []interface{} slice，answer 是會被轉成 interface，由於 Go 1.6 要求所有藉由 interface 傳遞得值都必須是指針，這邊編譯器看到的應該是：
var answer = Sum()
fmt.Println([]interface{&answer}...)我們可以用 -gcflags=”-m -m” 來確認
$ go build -gcflags="-m -m" sum.go 2>&1 | grep sum.go:23
./sum.go:23:13: inlining call to fmt.Println func(...interface {}) (int, error) { var fmt..autotmp_3 int; fmt..autotmp_3 = <N>; var fmt..autotmp_4 error; fmt..autotmp_4 = <N>; fmt..autotmp_3, fmt..autotmp_4 = fmt.Fprintln(io.Writer(os.Stdout), fmt.a...); return fmt..autotmp_3, fmt..autotmp_4 }
./sum.go:23:13: answer escapes to heap:
./sum.go:23:13: flow: ~arg0 = &{storage for answer}:
./sum.go:23:13: from answer (spill) at ./sum.go:23:13
./sum.go:23:13: from ~arg0 = <N> (assign-pair) at ./sum.go:23:13
./sum.go:23:13: flow: {storage for []interface {} literal} = ~arg0:
./sum.go:23:13: from []interface {} literal (slice-literal-element) at ./sum.go:23:13
./sum.go:23:13: flow: fmt.a = &{storage for []interface {} literal}:
./sum.go:23:13: from []interface {} literal (spill) at ./sum.go:23:13
./sum.go:23:13: from fmt.a = []interface {} literal (assign) at ./sum.go:23:13
./sum.go:23:13: flow: {heap} = *fmt.a:
./sum.go:23:13: from fmt.Fprintln(io.Writer(os.Stdout), fmt.a...) (call parameter) at ./sum.go:23:13
./sum.go:23:13: answer escapes to heap
./sum.go:23:13: []interface {} literal does not escape練習題
- 這種優化是否適用於任何的 count？
- 這種優化當 count 是變數而不是常數時是否適用？
- 這種優化當 count 為 Sum 函數的參數時是否適用？
接下來我們在看另一個範例
type Point struct{ X, Y int }
const Width = 640
const Height = 480
func Center(p *Point) {
p.X = Width / 2
p.Y = Height / 2
}
func NewPoint() {
p := new(Point)
Center(p)
fmt.Println(p.X, p.Y)
}NewPoint 函數會先產生一個 p *Point，接下來會呼叫 Center 把 p 移至螢幕的中間，最後在呼叫 fmt.Println 顯示 p.X 跟 p.Y
我們可以用 -gcflags=”-m” 來看編譯器的結果
$ go build -gcflags=-m ./center.go
# command-line-arguments
./center.go:12:6: can inline Center
./center.go:19:8: inlining call to Center
./center.go:20:13: inlining call to fmt.Println
./center.go:12:13: p does not escape
./center.go:18:10: new(Point) does not escape
./center.go:20:15: p.X escapes to heap
./center.go:20:20: p.Y escapes to heap
./center.go:20:13: []interface {} literal does not escape
<autogenerated>:1: .this does not escape
# command-line-arguments即使 p 是用 new 函數產生，p 還是沒有放在 heap
注意第 20 行，如果 p 沒有 escape，會是哪個值 escape to heap？
Inlining
一般來說呼叫函數都會有成本，而呼叫 Go 的函數當然也是，有這些固定的成本：stack 和 preemption checks
硬體分支預測器可以改善其中一些功能，但是函數大小跟時鐘週期這仍然會有影響
Inlining 是個避免這些成本的優化方式
直到 Go 1.11 inlining 只對 leaf 函數有用，leaf 函數裡不會呼叫其他函數，這麼做的原因：
- 如果某個函數做很多事情（很肥大），那麼前面提到的兩項佔比將會非常小
- 呼叫小的函數會有固定的成本，這種函數會是 inlining 優化的主要目標
最後一個原因是 heavy inlining 會使 stack traces 更難追尋，也就更難 debug
讓我們看看下面的範例
func Max(a, b int) int {
if a > b {
return a
}
return b
}
func F() {
const a, b = 100, 20
if Max(a, b) == b {
panic(b)
}
}我們可以用 -gcflags=-m 來看編譯器的結果
$ go build -gcflags=-m ./max.go
# command-line-arguments
./max.go:3:6: can inline Max
./max.go:10:6: can inline F
./max.go:12:8: inlining call to Max
# command-line-arguments編譯器：
- 第 3 行的 Max 函數可以被 inlined
- 第 10 行的 F 函數可以被 inlined
- 第 12 行 Max 被 inlined 到 F 函數
inlining 的結果看起來會是怎麼樣？
$ go build -gcflags=-S ./max.go 2>&1 | grep -A5 '"".F STEXT'
"".F STEXT nosplit size=1 args=0x0 locals=0x0
0x0000 00000 (/Users/peterlai/max.go:10) TEXT "".F(SB), NOSPLIT|ABIInternal, $0-0
0x0000 00000 (/Users/peterlai/max.go:10) FUNCDATA $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x0000 00000 (/Users/peterlai/max.go:10) FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
0x0000 00000 (/Users/peterlai/max.go:12) RET
0x0000 c3將剛剛的 max.go 後，可以看到 inlined 過後的 F 函數，裡面其實沒有做什麼事，只有最後的 RET 比較重要
F 函數再次經過編譯器優化後
func F() {
return
}什麼是 FUNCDATA 和 PCDATA？
-gcflags=-S 並不是最後執行的機械碼，在編譯成執行檔前連結器還需要處理
FUNCDATA 和 PCDATA 是 GC 的元數據，連結時會被移到其他地方，因為跟最後的執行檔無關，我們先忽略
討論
為什麼在 F 函數裡 a 和 b 是用 const 宣告？
如果將 a 和 b 改用 var 宣告會一樣嗎？如果將 a 和 b 做為 F 函數的參數會發生什麼事？
-gcflags=-S 並不會阻止產生 binary 檔案，如果執行後沒有顯示任何結果，可以刪除資料夾裡先前編譯後的檔案
調整 inlining 的層級
Go 編譯器可以使用 -gcflags -l 調整 inlining 的層級，這邊要注意的是單個 -l 會是停用 inlining，而兩個或三個 -l 則會啟用更激進的 inlining
- 預設為 regular inlining
- -gcflags=-l 停用 inlining
- -gcflags=’-l -l’ inlining 層級 2，可能會比較快，binary 檔案也可能比較大
- -gcflags=’-l -l -l’ inlining 層級 3，可能會比較快，binary 檔案會比較大，也可能會有很多 bug
- -gcflags=-l=4 在 Go 1.11 將會啟用實驗性的 mid-stack inlining
Mid Stack inlining
從 Go 1.12 開始啟用了 mid stack inlining（Go 1.11 要用 -gcflags=-l=4）
在前面的範例中，在 Go 1.11 F 因為呼叫了 Max 函數，所以不會是 leaf 函數
然而，由於 inlining 的改進，F 會因為這兩個原因被 inlined 到其他的函數裡：
- 當 Max 被 inlined 到 F 函數，F 沒有呼叫其他函數，因此如果尚未超過 complexity budget，F 函數將會是的 leaf 函數
- 因為 F 是個簡單的函數，inlining 和 dead code elimination 消除了許多 complexity budget
Mid stack inlining 可以用來 inline 函數的 fast path，Go 1.13 在 sync.RWMutex.Unlock() 使用了這個方法
延伸閱讀
- Mid-stack inlining in the Go compiler presentation by David Lazar
- Proposal: Mid-stack inlining in the Go compiler
Dead code elimination
為什麼 a 和 b 是常數很重要呢？
為了深入了解，先來看看一旦 Max inlined 到 F，我們就沒辦法簡單地從編譯器取得這兩個值
如果我們把 Max inlined 到 F：
func F() {
const a, b = 100, 20
var result int
if a > b {
result = a
} else {
result = b
}
if result == b {
panic(b)
}
}因為 a 和 b 是常數，所以編譯器可以在編譯的時候就知道 if-else 的結果
func F() {
const a, b = 100, 20
var result int
if true {
result = a
} else {
result = b
}
if result == b {
panic(b)
}
}result 其實編譯器也都知道，所以可以再優化（branch elimination）
func F() {
const a, b = 100, 20
const result = a
if false {
panic(b)
}
}然後可以再優化（branch elimination）
func F() {
const a, b = 100, 20
const result = a
}最後再優化就只剩
func F() {
}Branch elimination 是 dead code elimination 其中一種，編譯時使用靜態證明顯示一段程式碼永遠無法執行（dead code）
我們了解了 dead code elimination 如何和 inlining 一起減少無法執行的迴圈和分支來縮減程式碼
你也可以利用這點來實作 debugging
const debug = false結合 build tags 可能會更好
// +build debug
// debug function
func Debug(...args) {
// do something
}延伸閱讀
- Using // +build to switch between debug and release builds
- How to use conditional compilation with the go build tool
Compiler flags Exercises
前面練習的編譯器 flag 可以這樣帶入：
$ go build -gcflags=$FLAGS
- -S 顯示編譯後的組合語言 (Go flavoured)
- -l 調整 inliner; -l 停用 inlining， -l -l 為增加（more -l's increases the compiler’s appetite for inlining code）試試看不同的 inlining 的編譯時間、binary 程式大小以及執行時間會有什麼差
- -m 調整顯示編譯器優化的方式，像 inlining, escape analysis. -m -m 顯示更多編譯器的訊息
- -l -N 停用所有的優化（debugger 會需要用到）
如果執行完 go build 沒有顯示任何結果，試著刪除資料夾裡先前編譯好的執行檔
延伸閱讀
Codegen Inspection by Jaana Burcu Dogan
Bounds check elimination
Go 會檢查 array 以及 slice 的操作有沒有超出範圍，array 因為是固定大小會在編譯的時候就檢查，而 slice 則會在 runtime 時檢查
import(
"testing"
)
var v = make([]int, 9)
var A, B, C, D, E, F, G, H, I int
func BenchmarkBoundsCheckInOrder(b *testing.B) {
for n := 0; n < b.N; n++ {
A = v[0]
B = v[1]
C = v[2]
D = v[3]
E = v[4]
F = v[5]
G = v[6]
H = v[7]
I = v[8]
}
}用 -gcflags=-S 反編譯 BenchmarkBoundsCheckInOrder，每個迴圈執行多少次 bounds check?
func BenchmarkBoundsCheckOutOfOrder(b *testing.B) {
for n := 0; n < b.N; n++ {
I = v[8]
A = v[0]
B = v[1]
C = v[2]
D = v[3]
E = v[4]
F = v[5]
G = v[6]
H = v[7]
}
}調換 A 和 I 的位置會影響編譯結果嗎？
練習題
- 重新排列程式碼的順序會影響函數的執行速度或是大小嗎？
- 如果將 v 改在 Benchmark 函數裡面宣告，會影響編譯結果嗎？
- 如果 v 宣告成長度為 9 的 array，會影響編譯結果嗎？
