LoginSignup
10
2

More than 3 years have passed since last update.

@tutuz(Tsuji Daishiro)inフューチャー株式会社

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

Last updated at Posted at 2019-11-12

はじめに

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

Goで再帰使うと遅くなりますがそれが何だ

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

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

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

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

インライン展開とは

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

「インライン展開」より引用

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

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

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

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

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

サンプル実装

  • インライン展開する場合
hello.go
package hello

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

func Hello() interface{} {
    return struct{}{}
}
main.go
package main

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

func main() {
    hello.Hello()
}

go build main.go
go tool objdump main.exe > dump.txt
  • インライン展開しない場合
main.go
package main

func main() {
    hello.HelloNoInline()
}

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 を用いて最適化の結果も確認してみます。

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

...
  -m    print optimization decisions
...
  • インライン展開する場合
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" とするとより詳細な結果を知ることができます。

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
  • インライン展開しない場合
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 の最適化結果が出力されていません。

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

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

hello.go
package hello

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

func Hello() interface{} {
    return struct{}{}
}
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 倍の実行時間になっている結果が得られました3。
インライン展開されないことによって関数呼び出しのオーバーヘッドの影響がどのように実行時間に影響するか確認できました。

まとめ

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

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

  • 関数に含まれる式が 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. lex.go ↩

  2. cmd/compile: add a go:noinline directive ↩

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

10
2
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
2