花より団Go
sei0o inoue @ 学生LT第10回
誰
Agenda
- 最近の処理系
- 最適化
- コンパイラの中を覗いてみる
最近の処理系
- コンパイル言語・スクリプト言語
- 分け方の一つであって、実装はどちらでもよい
- VMが多く用いられる
- Ruby → YARV
- PHP → HHVM (Hack)
最適化
- 高速化
- 省サイズ化
- 仕組みを見てみよう!
処理系はいろいろ...
- Python
- Ruby
- .NET (C#)
- JVM (Java, Kotlin)
- V8, Chakra (JavaScript)
- Go ← 今回はこれ
Go
Gopherくん
- Googleが開発
- 並列処理が得意
- Docker
- ソースコードが読みやすい
The Go gopher was designed by Renée French.
コンパイル
$ GOSSAFUNC=main go build- なんかいろいろ生成してくれる
最適化の全体像
- compile.goからスタート
- 43ステップ
{name: "early phielim", fn: phielim},
{name: "early copyelim", fn: copyelim},
{name: "early deadcode", fn: deadcode},
{name: "short circuit", fn: shortcircuit},
{name: "decompose user", fn: decomposeUser, required: true},
{name: "opt", fn: opt, required: true},
{name: "zero arg cse", fn: zcse, required: true},
{name: "opt deadcode", fn: deadcode, required: true},
{name: "generic cse", fn: cse},
{name: "phiopt", fn: phiopt},
{name: "nilcheckelim", fn: nilcheckelim},
{name: "prove", fn: prove},
...
最適化の例: opt
- opt ステップから呼び出されるgeneric.rules (1200行ぐらい)
- 実際はこの内容がGoのコードに変換されている(30000行)
// Convert x * 1 to x.
(Mul(8|16|32|64) (Const(8|16|32|64) [1]) x) -> x
// fold negation into comparison operators
(Not (Eq(64|32|16|8|B) x y)) -> (Neq(64|32|16|8|B) x y)
(Not (Neq(64|32|16|8|B) x y)) -> (Eq(64|32|16|8|B) x y)
最適化の例
- if文の省略
(If (Not cond) yes no) -> (If cond no yes)
(If (ConstBool [c]) yes no) && c == 1 -> (First nil yes no)
(If (ConstBool [c]) yes no) && c == 0 -> (First nil no yes)
最適化の例
- こんな記述が…
// strength reduction of divide by a constant.
// See ../magic.go for a detailed description of these algorithms.
- magic.goを見てみる
- 定数での除算を乗算に置き換える
- CPUの除算は乗算に比べて遅い
// Machine division instructions are slow, so we try to
// compute this division with a multiplication + a few
// other cheap instructions instead.
magic?
// ⎣x * m / 2^e⎦
// Which we want to be equal to ⎣x / c⎦ for 0 <= x < 2^n-1
// where n is the word size.
// Setting x = c gives us c * m >= 2^e.
// We'll chose m = ⎡2^e/c⎤ to satisfy that equation.
// What remains is to choose e.
// Let m = 2^e/c + delta, 0 <= delta < 1
// ⎣x * (2^e/c + delta) / 2^e⎦
// ⎣x / c + x * delta / 2^e⎦
// We must have x * delta / 2^e < 1/
- よく見るとただの式変形
最適化の例: Dead Code Elimination
- 絶対に実行されないコードを取り除く
func main() {
x := 3
if x > 10 {
fmt.Printf("X is greater than 10") // dead code
}
}
最適化の例: Dead Code Elimination
- deadcode.go
- コメントがていねい→読める!
- この例ではgeneric.rulesで自明な条件分岐を書き換えた後、DCEでいらない部分を除去している(→合わせ技！)
- BlockIf → BlockFirst
最適化の例
- ssa/gen/にはアーキテクチャ個々についての最適化も
- x86
- ARM
- MIPS
まとめ
- 最適化すごい
- コンパイラは案外読める!!
おしまい
花より団Go
sei0o inoue @ 学生LT第10回