Goコンパイラのお勉強（2）~高階関数のためのインライン展開とエスケープ解析~

はじめに
インライン展開
エスケープ解析
- エスケープ解析とは
- 高階関数のパフォーマンスが落ちる例
さいごに
参考文献

はじめに

先々月にも Go コンパイラの最適化に関するブログ記事を書いたのですが、多くのブックマークを頂けて感謝です！ SRE の izzii です。

上のドキュメントを参考にしつつ Go コンパイラの最適化に関する記事を連載していきます。本記事は 2 本目です。

[第 1 回] Goコンパイラのお勉強（1）~ゼロ幅の型によるメモリ利用の最適化と未定義動作~
[本記事] Goコンパイラのお勉強（2）~高階関数のためのインライン展開とエスケープ解析~
[第 3 回] Goコンパイラのお勉強（3）~配列の効率的な操作に関する最適化~

文字数の関係でタイトルでは高階関数という言葉を使いましたが、私が言及したいのは 1.21.0 で追加された slices パッケージや、こちらのプロポーザルで盛り上がっている Map、Reduce、Filter といったイディオマティックな高階関数のことです。こうしたイディオムは便利である反面、使い方によっては for 文よりもパフォーマンスが悪化します。本記事では「インライン展開」と「エスケープ解析」に関する、 Go コンパイラの最適化に関する理解が、高階関数を適切に利用する上でも重要であることを実験を通してみていきます。

インライン展開

インライン展開とは

インライン展開とは関数の実装を呼び出し元に展開することで、関数呼び出しのオーバーヘッドを削減する手法です。インライン展開 - Wikipedia に具体的な例が載っているので私の説明で分かりづらい場合はご覧ください。Go コンパイラはよしなに判断して関数をインライン展開してくれます。

では以下のコードでインライン展開の効果を体験してみましょう。NoInline 関数は //go:noline ディレクティブによって、インライン展開が無効化されていることに注意です。

package main

import (
    "fmt"
    "time"
)

func YesInline() any {
    return struct{}{}
}

//go:noinline
func NoInline() any {
    return struct{}{}
}

func main() {
    var start time.Time
    var elapsed time.Duration
　　　　N := int(10e8)

    // インライン展開される場合
    start = time.Now()
    for i := 0; i < N; i++ {
        YesInline()
    }
    elapsed = time.Since(start)
    fmt.Println("YesInline() took", elapsed)

    // インライン展開されない場合
    start = time.Now()
    for i := 0; i < N; i++ {
        NoInline()
    }
    elapsed = time.Since(start)
    fmt.Println("NoInline()  took", elapsed)
}

まずはビルドオプション -gcflags="-m -m" をつけてビルド時の最適化の挙動を見てみます。

# go version go1.21.0 darwin/arm64

go build -gcflags="-m -m" sample1.go
./sample.go:8:6: can inline YesInline with cost 3 as: func() any { return struct {}{} }
./sample.go:13:6: cannot inline NoInline: marked go:noinline
./sample.go:17:6: cannot inline main: function too complex: cost 507 exceeds budget 80
./sample.go:25:12: inlining call to YesInline
./sample.go:28:13: inlining call to fmt.Println
./sample.go:36:13: inlining call to fmt.Println
...
略
...

./sample.go:8:6: inlining call to YesInline... とあるので Yesinline 関数がインライン展開されることがわかります。一方 ./sample.go:13:6: cannot inline NoInline: marked go:noinline とあるのでNoinline 関数はインライン展開されません。

では実行してみましょう。

# go version go1.21.0 darwin/arm64

% go run sample.go
YesInline() took 317.732291ms
NoInline()  took 2.073789375s

インライン展開が有効な Yesinline の方が高速です。一方、 Noinline は 10⁸ 回も関数が呼び出されるため、遅くなっています。

逆にインライン展開によるデメリットも存在します。たとえばコード内部の多くの場所で呼ばれる関数がインライン化されることで、バイナリが大きくなってしまうことなどが挙げられます。一般にはこうしたデメリットは意識することなく、Go コンパイラの判断にお任せで問題はないでしょう。

高階関数のパフォーマンスが落ちる例

せっかくなので Go 1.21.0 で追加された slices パッケージで実験してみたいところですが、現在実装されている関数はすべて条件分岐を含むもので、 CPU の実行時最適化への影響によってインライン展開の効果がぼやけてしまいます。なので今回は lo ライブラリの Reduce を使ってみます。

package main

import (
    "fmt"
    "time"

    "github.com/samber/lo"
)

func YesInline(a, b, _ int) int {
    return a + b
}

//go:noinline
func NoInline(a, b, _ int) int {
    return a + b
}

func main() {
    var start time.Time
    var elapsed time.Duration
    N := int(10e8)

    items := make([]int, N, N)
    for i := 0; i < N; i++ {
        items[i] = i
    }

    // for 文
    start = time.Now()
    sum := 0
    for _, item := range items {
        sum += item
    }
    elapsed = time.Since(start)
    fmt.Println("for         took", elapsed)

    // インライン展開される場合
    start = time.Now()
    _ = lo.Reduce(items, YesInline, 0)
    elapsed = time.Since(start)
    fmt.Println("YesInline() took", elapsed)

    // インライン展開されない場合
    start = time.Now()
    _ = lo.Reduce(items, NoInline, 0)
    elapsed = time.Since(start)
    fmt.Println("NoInline()  took", elapsed)
}

実行結果は以下です。

# go version go1.21.0 darwin/arm64

% go run sample.go
for         took 312.769459ms
YesInline() took 313.664083ms
NoInline()  took 6.693548083s

高階関数を使う場合でも、インライン展開されない場合はコレクションのサイズのぶんだけ関数呼び出しが発生します。ちなみに以下が lo の Reduce 実装です。slices パッケージの実装もほぼ一緒で、中身は for 文です。

// https://github.com/samber/lo/blob/3ae362dbb60ff6a2a1cb226a35079ea182c5f7c2/slice.go#L67C3-L67C3

// Reduce reduces collection to a value which is the accumulated result of running each element in collection
// through accumulator, where each successive invocation is supplied the return value of the previous.
// Play: https://go.dev/play/p/R4UHXZNaaUG
func Reduce[T any, R any](collection []T, accumulator func(agg R, item T, index int) R, initial R) R {
    for i, item := range collection {
        initial = accumulator(initial, item, i)
    }

    return initial
}

コンパイラがインライン展開を最適化してくれるからこそ、大抵の場合はオーバーヘッドを気にせず高階関数を使えますが、チューニングしたい時は for 文に書き換えた方が見通しがよいかもしれません。

インライン展開の制約

すべての関数がインライン展開されるわけではありません。（先述しましたがインライン展開によるデメリットもあります） CompilerOptimizations · golang/go Wiki · GitHub によると以下のすべての条件を満たす場合にインライン展開されることになります。

関数が短くシンプルであること。 具体的には、関数が作成する AST（抽象構文木と呼ばれるプログラムの構造を表すデータ構造）のノード数が 80 以下であることです。
関数が複雑な要素を含まないこと。 関数がクロージャ、defer、recover、select などの複雑な要素を含んでいないことです。
関数に go:noinline ディレクティブがついていないこと。 そのためのディレクティブですからね。
関数に go:uintptrescapes ディレクティブがついていないこと。 自分の Go 力では https://pkg.go.dev/cmd/compile を、よりわかりやすく説明できません。低レベルのシステムコールの実装以外では使用が非推奨のようです。
関数が Body を持っていること。 逆に関数の中身が Go で実装されていない場合は Body を持たないことがあります。
その他。 その他ってなんやねん！全部知りたい！と思われた方はこちらのコードを読んでみてもよいかもしれません。（私は途中で諦めました笑）https://github.com/golang/go/blob/go1.21.0/src/cmd/compile/internal/inline/inl.go

余談ですが上記に書かれない条件でいうと、例えば再帰関数はインライン展開されません。

package main

// 末尾再帰ですが普通の再帰でも結果は変わりません
func Fn(i int) int {
    if i == 0 {
        return 0
    }
    return Fn(i - 1)
}

func main() {
    Fn(100)
}

# go version go1.21.0 darwin/arm64

% go build -gcflags="-m -m" sample.go
./sample.go:3:6: cannot inline Fn: recursive
./sample.go:10:6: can inline main with cost 60 as: func() { Fn(100) }

さらに余談ですが、相互再帰の場合は片方だけがインライン展開されることがあります。

エスケープ解析

エスケープ解析とは

Go で「変数がエスケープする」とは変数へのポインタがスタック領域からヒープ領域に退避することを言います。エスケープする必要がなければエスケープしない方が変数のライフタイムを GC が管理する必要がないのでベターです。エスケープしない変数はスタックがポップされるタイミングで一緒に消せばよいからです。逆にある関数内で作られたポインタが関数を超えて利用されたりする場合は、エスケープする必要が出てきます。コンパイラによるエスケープ解析とは、変数をエスケープさせるかさせないかを判断することを言います。Go に限らなければエスケープ解析はもう少し広い意味を持ちます。（エスケープ解析 - Wikipedia） Go のエスケープ解析は、多くの場面では解析を諦めて変数をエスケープしているとみなすとのことです。またエスケープ解析のルールは非常に複雑なため、詳細な情報を確認する場合は、-mオプションをつけてコンパイラの出力をチェックするよう助言がされています。

Gc compiler does global escape analysis across function and package boundaries. However, there are lots of cases where it gives up. For example, anything assigned to any kind of indirection (*p = ...) is considered escaped. Other things that can inhibit analysis are: function calls, package boundaries, slice literals, subslicing and indexing, etc. Full rules are too complex to describe, so check the -m output.

（https://github.com/golang/go/wiki/CompilerOptimizations#escape-analysis）

Go は変数管理を強力なガベージコレクションに任せることで、変数スコープについてプログラマが頑張る必要がないのが素敵な言語です。しかし変数管理に無頓着すぎると、悪いコードに気がつけません。まずは簡単な実験をしてみましょう。

Golang エスケープ解析 - Qiita を参考にしています。

package main

import (
    "fmt"
    "time"
)

//go:noinline
func YesEscape() *int {
    i := 1000 // 違いの見やすさのために変数 i としています
    return &i
}

//go:noinline
func NoEscape() int {
    j := 1000 // 違いの見やすさのために変数 j としています
    return j
}

func main() {
    var start time.Time
    var elapsed time.Duration

    // for 文
    start = time.Now()
    for i := 0; i < 10e8; i++ {
        k := 1000
        _ = k
    }
    elapsed = time.Since(start)
    fmt.Println("for         took", elapsed)

    // エスケープされない場合
    start = time.Now()
    for i := 0; i < 10e8; i++ {
        _ = NoEscape()
    }
    elapsed = time.Since(start)
    fmt.Println("NoEscape()  took", elapsed)

    // エスケープされる場合
    start = time.Now()
    for i := 0; i < 10e8; i++ {
        _ = YesEscape()
    }
    elapsed = time.Since(start)
    fmt.Println("YesEscape() took", elapsed)
}

インライン展開が有効だとエスケープされなくなる場合があるため、 //go:noinline ディレクティブを使いつつ、最適化の挙動をみてみましょう。変数 i はエスケープされて、変数 j はエスケープされていないのが見て取れます。

# go version go1.21.0 darwin/arm64

% go build -gcflags="-m" sample.go
./sample.go:31:13: inlining call to fmt.Println
./sample.go:39:13: inlining call to fmt.Println
./sample.go:47:13: inlining call to fmt.Println
./sample.go:10:2: moved to heap: i
...
略
...

以下が実行結果です。 for と NoEscape() の実行時間の差はインライン展開による違い、 NoEscape() と YesEscape() の実行時間の差は変数のエスケープによる違いになります。

# go version go1.21.0 darwin/arm64

% go run sample1.go
for 　　　　　　　　　　   took 320.203792ms
NoEscape()  took 2.075623625s
YesEscape() took 11.633245875s

高階関数のパフォーマンスが落ちる例

インライン展開と同様に lo ライブラリの Reduce 関数を用いて議論をします。

package main

import (
    "fmt"
    "time"

    "github.com/samber/lo"
)

//go:noinline
func YesEscape(ay *int, by int, _ int) *int {
    i := *ay + by // 違いの見やすさのために変数 i としています
    return &i
}

//go:noinline
func NoEscape(an, bn, _ int) int {
    j := an + bn // 違いの見やすさのために変数 j としています
    return j
}

func main() {
    var start time.Time
    var elapsed time.Duration
    var sum int
    N := int(10e8)

    items := make([]int, N, N)
    for i := 0; i < N; i++ {
        items[i] = 1
    }

    // for 文
    sum = 0
    start = time.Now()
    for _, v := range items {
        sum += v
    }
    elapsed = time.Since(start)
    fmt.Println("for         took", elapsed)

    // エスケープされない場合
    start = time.Now()
    _ = lo.Reduce(items, NoEscape, 0)
    elapsed = time.Since(start)
    fmt.Println("NoEscape()  took", elapsed)

    // エスケープされる場合
    sum = 0
    start = time.Now()
    _ = lo.Reduce(items, YesEscape, &sum)
    elapsed = time.Since(start)
    fmt.Println("YesEscape() took", elapsed)
}

実行結果は以下です。それぞれの実行時間の違いは前述の通りです。

for と NoEscape() の実行時間の差はインライン展開による違い、 NoEscape() と YesEscape() の実行時間の差は変数のエスケープによる違いになります。

# go version go1.21.0 darwin/arm64

% go run sample1.go
for         took 1.098197333s
NoEscape()  took 2.175875542s
YesEscape() took 18.416683584s

高階関数を使う場合もエスケープが発生する場合はコレクションのサイズのぶんだけヒープ領域にメモリを確保することになってパフォーマンスが悪化します。多少であれば「Go のガベージコレクションを信じよう！」で切り抜けて良いと思います。ただし、高階関数に限らずサイズの大きなデータを対象としたプログラムを書く場合は気を付けましょう。ちなみに本気で変数のスコープやライフタイムが管理されたコードを書きたい、という場合は Go ではなく Rust など他の言語を使う方がよいでしょう。

さいごに

インライン展開とエスケープ解析について、今後利用が拡大していく可能性のある Map, Reduce, Filter といった高階関数と絡めて調査してみました。本記事の内容を頭の片隅に置きつつ、便利な高階関数たちを適切に使っていきましょう。コンパイラにも限界があるので、for 文に直した方が早い！なんてことも往々にしてあるんじゃないかと思っています。以下でも Go コンパイラの最適化について記事にしているので興味があればご覧ください！

tech.techtouch.jp