Go 中的內聯優化

2020-05-02 22:22:00

本文討論 Go 編譯器是如何實現內聯的,以及這種優化方法如何影響你的 Go 程式碼。

請注意:本文重點討論 gc,這是來自 golang.org 的事實標準的 Go 編譯器。討論到的概念可以廣泛適用於其它 Go 編譯器,如 gccgo 和 llgo,但它們在實現方式和功效上可能有所差異。

內聯是什麼?

內聯inlining就是把簡短的函數在呼叫它的地方展開。在計算機發展歷程的早期,這個優化是由程式設計師手動實現的。現在,內聯已經成為編譯過程中自動實現的基本優化過程的其中一步。

為什麼內聯很重要?

有兩個原因。第一個是它消除了函數呼叫本身的開銷。第二個是它使得編譯器能更高效地執行其他的優化策略。

函數呼叫的開銷

在任何語言中,呼叫一個函數 1 都會有消耗。把引數編組進暫存器或放入棧中(取決於 ABI),在返回結果時的逆反過程都會有開銷。引入一次函數呼叫會導致程式計數器從指令流的一點跳到另一點,這可能導致管道滯後。函數內部通常有前置處理preamble,需要為函數執行準備新的棧幀,還有與前置相似的後續處理epilogue,需要在返回給呼叫方之前釋放棧幀空間。

在 Go 中函數呼叫會消耗額外的資源來支援棧的動態增長。在進入函數時,goroutine 可用的棧空間與函數需要的空間大小進行比較。如果可用空間不同,前置處理就會跳到執行時runtime的邏輯中,通過把資料複製到一塊新的、更大的空間的來增長棧空間。當這個複製完成後,執行時就會跳回到原來的函數入口,再執行棧空間檢查,現在通過了檢查,函數呼叫繼續執行。這種方式下,goroutine 開始時可以申請很小的棧空間,在有需要時再申請更大的空間。2

這個檢查消耗很小,只有幾個指令,而且由於 goroutine 的棧是成幾何級數增長的,因此這個檢查很少失敗。這樣,現代處理器的分支預測單元可以通過假定檢查肯定會成功來隱藏棧空間檢查的消耗。當處理器預測錯了棧空間檢查,不得不放棄它在推測性執行所做的操作時,與為了增加 goroutine 的棧空間執行時所需的操作消耗的資源相比,管道滯後的代價更小。

雖然現代處理器可以用預測性執行技術優化每次函數呼叫中的泛型和 Go 特定的元素的開銷,但那些開銷不能被完全消除,因此在每次函數呼叫執行必要的工作過程中都會有效能消耗。一次函數呼叫本身的開銷是固定的,與更大的函數相比,呼叫小函數的代價更大,因為在每次呼叫過程中它們做的有用的工作更少。

因此,消除這些開銷的方法必須是要消除函數呼叫本身,Go 的編譯器就是這麼做的,在某些條件下通過用函數的內容來替換函數呼叫來實現。這個過程被稱為內聯,因為它在函數呼叫處把函數體展開了。

改進的優化機會

Cliff Click 博士把內聯描述為現代編譯器做的優化措施,像常數傳播(LCTT 譯註:此處作者筆誤,原文為 constant proportion,修正為 constant propagation)和死程式碼消除一樣,都是編譯器的基本優化方法。實際上,內聯可以讓編譯器看得更深,使編譯器可以觀察呼叫的特定函數的上下文內容,可以看到能繼續簡化或徹底消除的邏輯。由於可以遞回地執行內聯,因此不僅可以在每個獨立的函數上下文處進行這種優化決策,也可以在整個函數呼叫鏈中進行。

實踐中的內聯

下面這個例子可以演示內聯的影響:

package mainimport "testing"//go:noinlinefunc max(a, b int) int {    if a > b {        return a    }    return b}var Result intfunc BenchmarkMax(b *testing.B) {    var r int    for i := 0; i < b.N; i++ {        r = max(-1, i)    }    Result = r}

執行這個基準,會得到如下結果:3

% go test -bench=. BenchmarkMax-4   530687617         2.24 ns/op

在我的 2015 MacBook Air 上 max(-1, i) 的耗時約為 2.24 納秒。現在去掉 //go:noinline 編譯指令,再看下結果:

% go test -bench=. BenchmarkMax-4   1000000000         0.514 ns/op

從 2.24 納秒降到了 0.51 納秒,或者從 benchstat 的結果可以看出,有 78% 的提升。

% benchstat {old,new}.txtname   old time/op  new time/op  deltaMax-4  2.21ns ± 1%  0.49ns ± 6%  -77.96%  (p=0.000 n=18+19)

這個提升是從哪兒來的呢?

首先,移除掉函數呼叫以及與之關聯的前置處理 4 是主要因素。把 max 函數的函數體在呼叫處展開,減少了處理器執行的指令數量並且消除了一些分支。

現在由於編譯器優化了 BenchmarkMax,因此它可以看到 max 函數的內容,進而可以做更多的提升。當 max 被內聯後,BenchmarkMax 呈現給編譯器的樣子,看起來是這樣的:

func BenchmarkMax(b *testing.B) {    var r int    for i := 0; i < b.N; i++ {        if -1 > i {            r = -1        } else {            r = i        }    }    Result = r}

再執行一次基準,我們看一下手動內聯的版本和編譯器內聯的版本的表現:

% benchstat {old,new}.txtname   old time/op  new time/op  deltaMax-4  2.21ns ± 1%  0.48ns ± 3%  -78.14%  (p=0.000 n=18+18)

現在編譯器能看到在 BenchmarkMax 里內聯 max 的結果,可以執行以前不能執行的優化措施。例如,編譯器注意到 i 初始值為 0,僅做自增操作,因此所有與 i 的比較都可以假定 i 不是負值。這樣條件表示式 -1 > i 永遠不是 true5

證明了 -1 > i 永遠不為 true 後,編譯器可以把程式碼簡化為:

func BenchmarkMax(b *testing.B) {    var r int    for i := 0; i < b.N; i++ {        if false {            r = -1        } else {            r = i        }    }    Result = r}

並且因為分支裡是個常數,編譯器可以通過下面的方式移除不會走到的分支:

func BenchmarkMax(b *testing.B) {    var r int    for i := 0; i < b.N; i++ {        r = i    }    Result = r}

這樣,通過內聯和由內聯解鎖的優化過程,編譯器把表示式 r = max(-1, i)) 簡化為 r = i

內聯的限制

本文中我論述的內聯稱作葉子內聯leaf inlining:把函數呼叫棧中最底層的函數在呼叫它的函數處展開的行為。內聯是個遞迴的過程,當把函數內聯到呼叫它的函數 A 處後,編譯器會把內聯後的結果程式碼再內聯到 A 的呼叫方,這樣持續內聯下去。例如,下面的程式碼:

func BenchmarkMaxMaxMax(b *testing.B) {    var r int    for i := 0; i < b.N; i++ {        r = max(max(-1, i), max(0, i))    }    Result = r}

與之前的例子中的程式碼執行速度一樣快,因為編譯器可以對上面的程式碼重複地進行內聯,也把程式碼簡化到 r = i 表示式。

下一篇文章中,我會論述當 Go 編譯器想要行內函式呼叫棧中間的某個函數時選用的另一種內聯策略。最後我會論述編譯器為了內聯程式碼準備好要達到的極限,這個極限 Go 現在的能力還達不到。

相關文章:

  1. 使 Go 變快的 5 件事
  2. 為什麼 Goroutine 的棧空間會無限增長?
  3. Go 中怎麼寫基準測試
  4. Go 中隱藏的編譯指令

  1. 在 Go 中,一個方法就是一個有預先定義的形參和接受者的函數。假設這個方法不是通過介面呼叫的,呼叫一個無消耗的函數所消耗的代價與引入一個方法是相同的。 ?

  2. 在 Go 1.14 以前,棧檢查的前置處理也被垃圾回收器用於 STW,通過把所有活躍的 goroutine 棧空間設為 0,來強制它們切換為下一次函數呼叫時的執行時狀態。這個機制最近被替換為一種新機制,新機制下執行時可以不用等 goroutine 進行函數呼叫就可以暫停 goroutine。 ?

  3. 我用 //go:noinline 編譯指令來阻止編譯器內聯 max。這是因為我想把內聯 max 的影響與其他影響隔離開,而不是用 -gcflags='-l -N' 選項在全域性範圍內禁止優化。關於 //go: 注釋在這篇文章中詳細論述。 ?

  4. 你可以自己通過比較 go test -bench=. -gcflags=-S 有無 //go:noinline 註釋時的不同結果來驗證一下。 ?

  5. 你可以用 -gcflags=-d=ssa/prove/debug=on 選項來自己驗證一下。 ?