Go 中對棧中函數進行內聯

中我論述了葉子內聯leaf inlining是怎樣讓 Go 編譯器減少函數呼叫的開銷的，以及延伸出了跨函數邊界的優化的機會。本文中，我要論述內聯的限制以及葉子內聯與棧中內聯mid-stack inlining的對比。

內聯的限制

把函數內聯到它的呼叫處消除了呼叫的開銷，為編譯器進行其他的優化提供了更好的機會，那麼問題來了，既然內聯這麼好，內聯得越多開銷就越少，為什麼不盡可能多地內聯呢？

內聯可能會以增加程式大小換來更快的執行時間。限制內聯的最主要原因是，建立許多函數的內聯副本會增加編譯時間，並導致生成更大的二進位制檔案的邊際效應。即使把內聯帶來的進一步的優化機會考慮在內，太激進的內聯也可能會增加生成的二進位制檔案的大小和編譯時間。

內聯收益最大的是小函數，相對於呼叫它們的開銷來說，這些函數做很少的工作。隨著函數大小的增長，函數內部做的工作與函數呼叫的開銷相比省下的時間越來越少。函數越大通常越複雜，因此優化其內聯形式相對於原地優化的好處會減少。

內聯預算

在編譯過程中，每個函數的內聯能力是用內聯預算計算的 ¹。開銷的計算過程可以巧妙地內化，像一元和二元等簡單操作，在抽象語法數Abstract Syntax Tree（AST）中通常是每個節點一個單位，更複雜的操作如 make 可能單位更多。考慮下面的例子：

package mainfunc small() string {    s := "hello, " + "world!"    return s}func large() string {    s := "a"    s += "b"    s += "c"    s += "d"    s += "e"    s += "f"    s += "g"    s += "h"    s += "i"    s += "j"    s += "k"    s += "l"    s += "m"    s += "n"    s += "o"    s += "p"    s += "q"    s += "r"    s += "s"    s += "t"    s += "u"    s += "v"    s += "w"    s += "x"    s += "y"    s += "z"    return s}func main() {    small()    large()}

使用 -gcflags=-m=2 引數編譯這個函數能讓我們看到編譯器分配給每個函數的開銷：

% go build -gcflags=-m=2 inl.go# command-line-arguments./inl.go:3:6: can inline small with cost 7 as: func() string { s := "hello, world!"; return s }./inl.go:8:6: cannot inline large: function too complex: cost 82 exceeds budget 80./inl.go:38:6: can inline main with cost 68 as: func() { small(); large() }./inl.go:39:7: inlining call to small func() string { s := "hello, world!"; return s }

編譯器根據函數 func small() 的開銷（7）決定可以對它內聯，而 func large() 的開銷太大，編譯器決定不進行內聯。func main() 被標記為適合內聯的，分配了 68 的開銷；其中 small 占用 7，呼叫 small 函數占用 57，剩餘的（4）是它自己的開銷。

可以用 -gcflag=-l 引數控制內聯預算的等級。下面是可使用的值：

-gcflags=-l=0 預設的內聯等級。
-gcflags=-l（或 -gcflags=-l=1）取消內聯。
-gcflags=-l=2 和 -gcflags=-l=3 現在已經不使用了。和 -gcflags=-l=0 相比沒有區別。
-gcflags=-l=4 減少非葉子函數和通過介面呼叫的函數的開銷。²

不確定語句的優化

一些函數雖然內聯的開銷很小，但由於太複雜它們仍不適合進行內聯。這就是函數的不確定性，因為一些操作的語意在內聯後很難去推導，如 recover、break。其他的操作，如 select 和 go 涉及執行時的協調，因此內聯後引入的額外的開銷不能抵消內聯帶來的收益。

不確定的語句也包括 for 和 range，這些語句不一定開銷很大，但目前為止還沒有對它們進行優化。

棧中函數優化

在過去，Go 編譯器只對葉子函數進行內聯 —— 只有那些不呼叫其他函數的函數才有資格。在上一段不確定的語句的探討內容中，一次函數呼叫就會讓這個函數失去內聯的資格。

進入棧中進行內聯，就像它的名字一樣，能內聯在函數呼叫棧中間的函數，不需要先讓它下面的所有的函數都被標記為有資格內聯的。棧中內聯是 David Lazar 在 Go 1.9 中引入的，並在隨後的版本中做了改進。這篇文稿深入探究了保留棧追蹤行為和被深度內聯後的程式碼路徑裡的 runtime.Callers 的難點。

在前面的例子中我們看到了棧中函數內聯。內聯後，func main() 包含了 func small() 的函數體和對 func large() 的一次呼叫，因此它被判定為非葉子函數。在過去，這會阻止它被繼續內聯，雖然它的聯合開銷小於內聯預算。

棧中內聯的最主要的應用案例就是減少貫穿函數呼叫棧的開銷。考慮下面的例子：

package mainimport (    "fmt"    "strconv")type Rectangle struct {}//go:noinlinefunc (r *Rectangle) Height() int {    h, _ := strconv.ParseInt("7", 10, 0)    return int(h)}func (r *Rectangle) Width() int {    return 6}func (r *Rectangle) Area() int { return r.Height() * r.Width() }func main() {    var r Rectangle    fmt.Println(r.Area())}

在這個例子中， r.Area() 是個簡單的函數，呼叫了兩個函數。r.Width() 可以被內聯，r.Height() 這裡用 //go:noinline 指令標註了，不能被內聯。³

% go build -gcflags='-m=2' square.go                                                                                                          # command-line-arguments./square.go:12:6: cannot inline (*Rectangle).Height: marked go:noinline                                                                               ./square.go:17:6: can inline (*Rectangle).Width with cost 2 as: method(*Rectangle) func() int { return 6 }./square.go:21:6: can inline (*Rectangle).Area with cost 67 as: method(*Rectangle) func() int { return r.Height() * r.Width() }                       ./square.go:21:61: inlining call to (*Rectangle).Width method(*Rectangle) func() int { return 6 }                                                     ./square.go:23:6: cannot inline main: function too complex: cost 150 exceeds budget 80                        ./square.go:25:20: inlining call to (*Rectangle).Area method(*Rectangle) func() int { return r.Height() * r.Width() }./square.go:25:20: inlining call to (*Rectangle).Width method(*Rectangle) func() int { return 6 }

由於 r.Area() 中的乘法與呼叫它的開銷相比並不大，因此內聯它的表示式是純收益，即使它的呼叫的下游 r.Height() 仍是沒有內聯資格的。

快速路徑內聯

關於棧中內聯的效果最令人吃驚的例子是 2019 年 Carlo Alberto Ferraris 通過允許把 sync.Mutex.Lock() 的快速路徑（非競爭的情況）內聯到它的呼叫方來提升它的效能。在這個修改之前，sync.Mutex.Lock() 是個很大的函數，包含很多難以理解的條件，使得它沒有資格被內聯。即使鎖可用時，呼叫者也要付出呼叫 sync.Mutex.Lock() 的代價。

Carlo 把 sync.Mutex.Lock() 分成了兩個函數（他自己稱為外聯outlining）。外部的 sync.Mutex.Lock() 方法現在呼叫 sync/atomic.CompareAndSwapInt32() 且如果 CAS（比較並交換Compare and Swap）成功了之後立即返回給呼叫者。如果 CAS 失敗，函數會走到 sync.Mutex.lockSlow() 慢速路徑，需要對鎖進行註冊，暫停 goroutine。⁴

% go build -gcflags='-m=2 -l=0' sync 2>&1 | grep '(*Mutex).Lock'../go/src/sync/mutex.go:72:6: can inline (*Mutex).Lock with cost 69 as: method(*Mutex) func() { if "sync/atomic".CompareAndSwapInt32(&m.state, 0, mutexLocked) { if race.Enabled {  }; return  }; m.lockSlow() }

通過把函數分割成一個簡單的不能再被分割的外部函數，和（如果沒走到外部函數就走到的）一個處理慢速路徑的複雜的內部函數，Carlo 組合了棧中函數內聯和編譯器對基礎操作的支援，減少了非競爭鎖 14% 的開銷。之後他在 sync.RWMutex.Unlock() 重複這個技巧，節省了另外 9% 的開銷。