Go中對(duì)棧中函數(shù)進(jìn)行內(nèi)聯(lián)
上一篇文章中我論述了葉子內(nèi)聯(lián)是怎樣讓 Go 編譯器減少函數(shù)調(diào)用的開(kāi)銷(xiāo)的，以及延伸出了跨函數(shù)邊界的優(yōu)化的機(jī)會(huì)。本文中，我要論述內(nèi)聯(lián)的限制以及葉子內(nèi)聯(lián)與棧中內(nèi)聯(lián)的對(duì)比。
內(nèi)聯(lián)的限制
把函數(shù)內(nèi)聯(lián)到它的調(diào)用處消除了調(diào)用的開(kāi)銷(xiāo)，為編譯器進(jìn)行其他的優(yōu)化提供了更好的機(jī)會(huì)，那么問(wèn)題來(lái)了，既然內(nèi)聯(lián)這么好，內(nèi)聯(lián)得越多開(kāi)銷(xiāo)就越少，為什么不盡可能多地內(nèi)聯(lián)呢？
內(nèi)聯(lián)可能會(huì)以增加程序大小換來(lái)更快的執(zhí)行時(shí)間。限制內(nèi)聯(lián)的最主要原因是，創(chuàng)建許多函數(shù)的內(nèi)聯(lián)副本會(huì)增加編譯時(shí)間，并導(dǎo)致生成更大的二進(jìn)制文件的邊際效應(yīng)。即使把內(nèi)聯(lián)帶來(lái)的進(jìn)一步的優(yōu)化機(jī)會(huì)考慮在內(nèi)，太激進(jìn)的內(nèi)聯(lián)也可能會(huì)增加生成的二進(jìn)制文件的大小和編譯時(shí)間。
內(nèi)聯(lián)收益最大的是小函數(shù)，相對(duì)于調(diào)用它們的開(kāi)銷(xiāo)來(lái)說(shuō)，這些函數(shù)做很少的工作。隨著函數(shù)大小的增長(zhǎng)，函數(shù)內(nèi)部做的工作與函數(shù)調(diào)用的開(kāi)銷(xiāo)相比省下的時(shí)間越來(lái)越少。函數(shù)越大通常越復(fù)雜，因此優(yōu)化其內(nèi)聯(lián)形式相對(duì)于原地優(yōu)化的好處會(huì)減少。
內(nèi)聯(lián)預(yù)算
在編譯過(guò)程中，每個(gè)函數(shù)的內(nèi)聯(lián)能力是用內(nèi)聯(lián)預(yù)算計(jì)算的 1。開(kāi)銷(xiāo)的計(jì)算過(guò)程可以巧妙地內(nèi)化，像一元和二元等簡(jiǎn)單操作，在抽象語(yǔ)法數(shù)（AST）中通常是每個(gè)節(jié)點(diǎn)一個(gè)單位，更復(fù)雜的操作如 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 參數(shù)編譯這個(gè)函數(shù)能讓我們看到編譯器分配給每個(gè)函數(shù)的開(kāi)銷(xiāo)：
% 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 }
編譯器根據(jù)函數(shù) func small() 的開(kāi)銷(xiāo)（7）決定可以對(duì)它內(nèi)聯(lián)，而 func large() 的開(kāi)銷(xiāo)太大，編譯器決定不進(jìn)行內(nèi)聯(lián)。func main() 被標(biāo)記為適合內(nèi)聯(lián)的，分配了 68 的開(kāi)銷(xiāo)；其中 small 占用 7，調(diào)用 small 函數(shù)占用 57，剩余的（4）是它自己的開(kāi)銷(xiāo)。
可以用 -gcflag=-l 參數(shù)控制內(nèi)聯(lián)預(yù)算的等級(jí)。下面是可使用的值：
-gcflags=-l=0默認(rèn)的內(nèi)聯(lián)等級(jí)。-gcflags=-l（或-gcflags=-l=1）取消內(nèi)聯(lián)。-gcflags=-l=2和-gcflags=-l=3現(xiàn)在已經(jīng)不使用了。和-gcflags=-l=0相比沒(méi)有區(qū)別。-gcflags=-l=4減少非葉子函數(shù)和通過(guò)接口調(diào)用的函數(shù)的開(kāi)銷(xiāo)。2
不確定語(yǔ)句的優(yōu)化
一些函數(shù)雖然內(nèi)聯(lián)的開(kāi)銷(xiāo)很小，但由于太復(fù)雜它們?nèi)圆贿m合進(jìn)行內(nèi)聯(lián)。這就是函數(shù)的不確定性，因?yàn)橐恍┎僮鞯恼Z(yǔ)義在內(nèi)聯(lián)后很難去推導(dǎo)，如 recover、break。其他的操作，如 select 和 go 涉及運(yùn)行時(shí)的協(xié)調(diào)，因此內(nèi)聯(lián)后引入的額外的開(kāi)銷(xiāo)不能抵消內(nèi)聯(lián)帶來(lái)的收益。
不確定的語(yǔ)句也包括 for 和 range，這些語(yǔ)句不一定開(kāi)銷(xiāo)很大，但目前為止還沒(méi)有對(duì)它們進(jìn)行優(yōu)化。
棧中函數(shù)優(yōu)化
在過(guò)去，Go 編譯器只對(duì)葉子函數(shù)進(jìn)行內(nèi)聯(lián) —— 只有那些不調(diào)用其他函數(shù)的函數(shù)才有資格。在上一段不確定的語(yǔ)句的探討內(nèi)容中，一次函數(shù)調(diào)用就會(huì)讓這個(gè)函數(shù)失去內(nèi)聯(lián)的資格。
進(jìn)入棧中進(jìn)行內(nèi)聯(lián)，就像它的名字一樣，能內(nèi)聯(lián)在函數(shù)調(diào)用棧中間的函數(shù)，不需要先讓它下面的所有的函數(shù)都被標(biāo)記為有資格內(nèi)聯(lián)的。棧中內(nèi)聯(lián)是 David Lazar 在 Go 1.9 中引入的，并在隨后的版本中做了改進(jìn)。這篇文稿深入探究了保留棧追蹤行為和被深度內(nèi)聯(lián)后的代碼路徑里的 runtime.Callers 的難點(diǎn)。
在前面的例子中我們看到了棧中函數(shù)內(nèi)聯(lián)。內(nèi)聯(lián)后，func main() 包含了 func small() 的函數(shù)體和對(duì) func large() 的一次調(diào)用，因此它被判定為非葉子函數(shù)。在過(guò)去，這會(huì)阻止它被繼續(xù)內(nèi)聯(lián)，雖然它的聯(lián)合開(kāi)銷(xiāo)小于內(nèi)聯(lián)預(yù)算。
棧中內(nèi)聯(lián)的最主要的應(yīng)用案例就是減少貫穿函數(shù)調(diào)用棧的開(kāi)銷(xiāo)?？紤]下面的例子：
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 Rectanglefmt.Println(r.Area())}
在這個(gè)例子中， r.Area() 是個(gè)簡(jiǎn)單的函數(shù)，調(diào)用了兩個(gè)函數(shù)。r.Width() 可以被內(nèi)聯(lián)，r.Height() 這里用 //go:noinline 指令標(biāo)注了，不能被內(nèi)聯(lián)。3
% 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() 中的乘法與調(diào)用它的開(kāi)銷(xiāo)相比并不大，因此內(nèi)聯(lián)它的表達(dá)式是純收益，即使它的調(diào)用的下游 r.Height() 仍是沒(méi)有內(nèi)聯(lián)資格的。
快速路徑內(nèi)聯(lián)
關(guān)于棧中內(nèi)聯(lián)的效果最令人吃驚的例子是 2019 年 Carlo Alberto Ferraris 通過(guò)允許把 sync.Mutex.Lock() 的快速路徑（非競(jìng)爭(zhēng)的情況）內(nèi)聯(lián)到它的調(diào)用方來(lái)提升它的性能。在這個(gè)修改之前，sync.Mutex.Lock() 是個(gè)很大的函數(shù)，包含很多難以理解的條件，使得它沒(méi)有資格被內(nèi)聯(lián)。即使鎖可用時(shí)，調(diào)用者也要付出調(diào)用 sync.Mutex.Lock() 的代價(jià)。
Carlo 把 sync.Mutex.Lock() 分成了兩個(gè)函數(shù)（他自己稱(chēng)為外聯(lián)）。外部的 sync.Mutex.Lock() 方法現(xiàn)在調(diào)用 sync/atomic.CompareAndSwapInt32() 且如果 CAS（比較并交換）成功了之后立即返回給調(diào)用者。如果 CAS 失敗，函數(shù)會(huì)走到 sync.Mutex.lockSlow() 慢速路徑，需要對(duì)鎖進(jìn)行注冊(cè)，暫停 goroutine。4
% 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() }
通過(guò)把函數(shù)分割成一個(gè)簡(jiǎn)單的不能再被分割的外部函數(shù)，和（如果沒(méi)走到外部函數(shù)就走到的）一個(gè)處理慢速路徑的復(fù)雜的內(nèi)部函數(shù)，Carlo 組合了棧中函數(shù)內(nèi)聯(lián)和編譯器對(duì)基礎(chǔ)操作的支持，減少了非競(jìng)爭(zhēng)鎖 14% 的開(kāi)銷(xiāo)。之后他在 sync.RWMutex.Unlock() 重復(fù)這個(gè)技巧，節(jié)省了另外 9% 的開(kāi)銷(xiāo)。
