Go Compilerのインライン展開についてまとめた

## はじめに

Go は末尾再帰が最適化されない。というかあえて最適化しない、という選択を採用しているようです。

[Goで再帰使うと遅くなりますがそれが何だ](https://ymotongpoo.hatenablog.com/entry/2015/02/23/165341)

そもそも私はあまりコンパイラの気持ちになったことがなく、関数呼び出しのときにインライン展開されるということがどういうことかわかりませんでした。

本記事では以下の 3 点についてまとめてみます。

- 関数のインライン展開とはどういうことか
- Go Compiler がどのような動作をするのか
- インライン展開されることでどのような効果があるのか

## 関数のインライン展開とはどういうことか

### インライン展開とは 

> インライン展開（インラインてんかい、英: inline expansion または 英: inlining）とは、コンパイラによる最適化手法の1つで、関数を呼び出す側に呼び出される関数のコードを展開し、関数への制御転送をしないようにする手法。これにより関数呼び出しに伴うオーバーヘッドを削減する。特に小さくて頻繁に呼ばれる関数では効果的であり、呼び出し側にそのコードを展開することで定数畳み込みなどのさらなる最適化を施せる可能性が生じる。問題点はバイナリコードが一般に肥大化する結果を招く点であり、参照の局所性を損なうほどだったり、リソースの限界を超えると性能がかえって悪化することになる。

「[インライン展開](https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%B3%E3%83%A9%E3%82%A4%E3%83%B3%E5%B1%95%E9%96%8B)」より引用

端的に言って、**関数呼び出しのコードを呼び出し元に展開することで、関数呼び出しのオーバヘッドを削減し高速化する**、という最適化手法のようです。

## Go Compiler がどのような動作をするのか

Go で関数がインライン展開されたときとそうでないときで、コンパイラ結果にどのような違いがあるのか確認してみます。

Go では `go:noinline` という pragma を用いることができ、この pragma を用いることで関数をインライン展開しないようにコンパイルします。[^2] `go:noinline` はテストを目的とした pragma です。[^3]

[^2]: [lex.go](https://github.com/golang/go/blob/master/src/cmd/compile/internal/gc/lex.go#L64)
[^3]: [cmd/compile: add a go:noinline directive](https://github.com/golang/go/issues/12312)

pragma を用いて、インライン展開するコードとそうでないコードで、それぞれコンパイル後の実行ファイルを逆アセンブリして確認します。逆アセンブリには Go に標準で備わっている [objdump](https://golang.org/cmd/objdump/) を用います。`objdump` を用いると実行ファイルのバイナリからテキストシンボルの逆アセンブリを出力することができます。

#### サンプル実装

- インライン展開する場合

```go:hello.go
package hello

//go:noinline
func HelloNoInline() interface{} {
	return struct{}{}
}

func Hello() interface{} {
	return struct{}{}
}
```

```go:main.go
package main

import "github.com/d-tsuji/go-sandbox/opt/hello"

func main() {
	hello.Hello()
}
```

```console
go build main.go
go tool objdump main.exe > dump.txt
```

- インライン展開しない場合

```go:main.go
package main

func main() {
	hello.HelloNoInline()
}
```

```console
go build main.go
go tool objdump main.exe > dump_noinline.txt
```

#### 出力結果の比較

ダンプした結果の main 関数のテキストセグメントを抜粋します。

- インライン展開する場合

```
...

TEXT main.main(SB) C:/Users/dramt/go/src/github.com/d-tsuji/go-sandbox/opt/hello/cmd/main.go
  main.go:5		0x451e30		c3			RET			
  :0			0x451e31		cc			INT $0x3		
  :0			0x451e32		cc			INT $0x3		
  :0			0x451e33		cc			INT $0x3		
  :0			0x451e34		cc			INT $0x3		
  :0			0x451e35		cc			INT $0x3		
  :0			0x451e36		cc			INT $0x3		
  :0			0x451e37		cc			INT $0x3		
  :0			0x451e38		cc			INT $0x3		
  :0			0x451e39		cc			INT $0x3		
  :0			0x451e3a		cc			INT $0x3		
  :0			0x451e3b		cc			INT $0x3		
  :0			0x451e3c		cc			INT $0x3		
  :0			0x451e3d		cc			INT $0x3		
  :0			0x451e3e		cc			INT $0x3		
  :0			0x451e3f		cc			INT $0x3		

...
```

- インライン展開しない場合

```
...

TEXT github.com/d-tsuji/go-sandbox/opt/hello.HelloNoInline(SB) C:/Users/dramt/go/src/github.com/d-tsuji/go-sandbox/opt/hello/hello.go
  hello.go:5		0x451e30		488d0549ec0000		LEAQ runtime.rodata+60032(SB), AX	
  hello.go:5		0x451e37		4889442408		MOVQ AX, 0x8(SP)			
  hello.go:5		0x451e3c		488d058d6d0800		LEAQ runtime.zerobase(SB), AX		
  hello.go:5		0x451e43		4889442410		MOVQ AX, 0x10(SP)			
  hello.go:5		0x451e48		c3			RET					
  :-1			0x451e49		cc			INT $0x3				
  :-1			0x451e4a		cc			INT $0x3				
  :-1			0x451e4b		cc			INT $0x3				
  :-1			0x451e4c		cc			INT $0x3				
  :-1			0x451e4d		cc			INT $0x3				
  :-1			0x451e4e		cc			INT $0x3				
  :-1			0x451e4f		cc			INT $0x3				

TEXT main.main(SB) C:/Users/dramt/go/src/github.com/d-tsuji/go-sandbox/opt/hello/cmd/main.go
  main.go:5		0x451e50		65488b0c2528000000	MOVQ GS:0x28, CX						
  main.go:5		0x451e59		488b8900000000		MOVQ 0(CX), CX							
  main.go:5		0x451e60		483b6110		CMPQ 0x10(CX), SP						
  main.go:5		0x451e64		761d			JBE 0x451e83							
  main.go:5		0x451e66		4883ec18		SUBQ $0x18, SP							
  main.go:5		0x451e6a		48896c2410		MOVQ BP, 0x10(SP)						
  main.go:5		0x451e6f		488d6c2410		LEAQ 0x10(SP), BP						
  main.go:6		0x451e74		e8b7ffffff		CALL github.com/d-tsuji/go-sandbox/opt/hello.HelloNoInline(SB)	
  main.go:7		0x451e79		488b6c2410		MOVQ 0x10(SP), BP						
  main.go:7		0x451e7e		4883c418		ADDQ $0x18, SP							
  main.go:7		0x451e82		c3			RET								
  main.go:5		0x451e83		e8487effff		CALL runtime.morestack_noctxt(SB)				
  main.go:5		0x451e88		ebc6			JMP main.main(SB)						


...
```

インライン展開した場合は、実行ファイルから hello.Hello 関数の呼び出しが消えています。インライン展開された結果です。一方でインライン展開しない場合は、実行ファイルに hello.HelloNoInline 関数が存在し、main 関数から hello.HelloNoInline 関数を CALL していることが分かります。
サンプルの実装例は、何もしない関数を定義しているため極端ですが、インライン展開される場合とそうでない場合でコンパイルされた結果がどのように異なるか確認できました。

実行ファイルから詳細を確認するために `go tool objdump` を用いましたが、コンパイラがどのような最適化をしているかは逆アセンブリをせずとも、`go build -gcflags -m` で確認することができます。`go build -gcflags -m` を用いて最適化の結果も確認してみます。

```console:-gcflagsのオプション一覧
go build -gcflags --help

...
  -m    print optimization decisions
...
```

- インライン展開する場合

```console
go build -gcflags -m main.go
# github.com/d-tsuji/go-sandbox/opt/hello/cmd
.\main.go:5:6: can inline main
.\main.go:6:13: inlining call to hello.Hello
.\main.go:6:13: main (interface {})(struct {} literal) does not escape
```

実際にインライン展開された場合は `inlining call to` のように表示されます。`can inline` はインライン展開の条件を満たしているがインライン展開はされてない、ということを示しています。`does not escape` というのは変数が関数内でしか使用されていないためにヒープにエスケープされない(スタックに積める)ことを示しています。

`go build -gcflags "-m -m"` とするとより詳細な結果を知ることができます。

```console
go build -gcflags "-m -m" main.go
# command-line-arguments
.\main.go:5:6: can inline main as: func() { hello.Hello() }
.\main.go:6:13: inlining call to hello.Hello func() interface {} { return (interface {})(struct {} literal) }
.\main.go:6:13: main (interface {})(struct {} literal) does not escape
```

- インライン展開しない場合

```console
go build -gcflags -m main.go
# github.com/d-tsuji/go-sandbox/opt/hello/cmd
.\main.go:5:6: can inline main
```

逆アセンブリしてテキストシンボルの内容を確認したときと同様に、インライン展開する場合は `inlining call to hello.Hello` が存在し、されない場合は `inlining call to hello.HelloNoline` の最適化結果が出力されていません。

## インライン展開されることでどのような効果があるのか

実行時間にどの程度影響があるのか、ベンチマークをとってみます。サンプルの関数の実装は先ほどの例の実装と同様です。

```go:hello.go
package hello

//go:noinline
func HelloNoInline() interface{} {
	return struct{}{}
}

func Hello() interface{} {
	return struct{}{}
}
```

```go:hello_test.go
package hello

import "testing"

func BenchmarkHello(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Hello()
	}
}

func BenchmarkHelloNoInline(b *testing.B) {
	for i := 0; i < b.N; i++ {
		HelloNoInline()
	}
}
```

```
> go test -bench . -benchmem
goos: windows
goarch: amd64
pkg: github.com/d-tsuji/go-sandbox/opt/hello
BenchmarkHello-8                2000000000               0.34 ns/op            0 B/op          0 allocs/op
BenchmarkHelloNoInline-8        2000000000               1.51 ns/op            0 B/op          0 allocs/op
PASS
ok      github.com/d-tsuji/go-sandbox/opt/hello 4.295s
```

関数は空構造体を返しているだけで、メモリはアロケートしておらず、どちらも 0 B/op で想定通りです。一方で実行時間はインライン展開している場合は、そうでない場合と比較して約 1/5 倍の実行時間になっている結果が得られました[^1]。
インライン展開されないことによって関数呼び出しのオーバーヘッドの影響がどのように実行時間に影響するか確認できました。

## まとめ

インライン展開する場合とそうでない場合で Go のコンパイラがどのような実行ファイルを生成するか確認しました。またインライン展開の高速化の効果を確認しました。

Go のコンパイラがどのような最適化を実施するかは [Compiler And Runtime Optimizations](https://github.com/golang/go/wiki/CompilerOptimizations) のページが参考になります。
関数のインライン展開する条件も記載されています。要件は結構厳しくて、以下を満たす必要があります。

- 関数に含まれる式が 40 個未満
- 関数呼出し・ループ・クロージャー・`panic`・`recover`・`select`・`switch` といった複雑なものを含まない

> Only short and simple functions are inlined. To be inlined a function must contain less than ~40 expressions and does not contain complex things like function calls, loops, labels, closures, panic's, recover's, select's, switch'es, etc

[^1]: 関数の中身が小さい(今回の場合は、ない)ために、よりオーバーヘッドの影響が強調されています。