Compiler/JIT optimizations & escape analysis

コンパイラ・JIT が行っている各種の最適化や JIT の振る舞い(の一部)を概説し、
その背景にある Escape Analysis についても軽く解説します。

Transcript

1. いまどきのコンパイラ・JIT の最適化と Escape Analysis M3 Tech Talk - July 5 2019 Seiya Yazaki 1
2. Escape Analysis？ -> オブジェクトのスコープ(⽣存区間)を⾃動判定すること 現代的なコンパイラ最適化や JIT の振る舞いを知る上で有⽤な概念。 今回は各種の最適化や JIT の振る舞いを概説し、 その背景にある Escape Analysis についても触れる。 2
3. オブジェクトのスコープ？ オブジェクトのスコープ と 変数のスコープ は違う 3
4. オブジェクトのスコープが変数と⼀致する例 何かの関数 () { val something = new Object(); return; } 変数のスコープ: 宣⾔から関数の終わりまで オブジェクトのスコープ: 宣⾔から関数の終わりまで 4
5. スコープが⼀致しない例 val グローバル変数; 何かの関数 () { val something = new Object(); グローバル変数 = something; return something; } 変数のスコープ: 宣⾔から関数の終わりまで オブジェクトのスコープ: new してからずっと⽣存 ( escape している) 5
6. オブジェクトのスコープの判定 変数のスコープはプログラム⾔語の仕様として明確。 オブジェクトのスコープは必ずしも⾃明ではない。 オブジェクトが関数やクラスの外側から参照されうる(escape している)かを判定するのが Escape Analysis。 6
7. 1: 最適化における Escape Analysis の必要性 7
8. 最適化の前提としての Escape Analysis オブジェクトが escape しないことを前提とする最適化⼿法がいっぱいある: オブジェクトの展開 (スタック割付け, Scalar replacement) オブジェクトのインライン化 キャッシュ write back の省略 ロック・Atomic メモリ操作の省略 ラムダ式のクロージャーの最適化 ... この章では、これらの最適化について概説。 8
9. 現代的 CPU・メモリの階層型アーキテクチャ CPU はメモリを直接読み書きするのではない。 演算対象の値は register に格納し、L1/L2/L3 cache 経由でメモリと同期する。 さらに CPU コア・ソケット間では同期操作も必要である。 図の引⽤元: CPU Cache Flushing Fallacy 9
10. メモリ上のオブジェクトの読み書きは遅い メモリ(DRAM)の読み書きは register の 50〜100 倍遅い。 しかし、近代的なプログラミング⾔語は オブジェクトがメモリに割り当てられる前提の⾔語仕様。 さらにメモリ上のオブジェクトの読み書きには各種オーバーヘッドがある: メモリアロケーター, ロック, 参照カウント, GC, キャッシュの write back, ... なので極⼒メモリの読み書きを最⼩化したい。 10
11. オブジェクトのインライン化 (スタックへの割当て) オブジェクトをスタック上の変数で実現してしまう最適化: class Hoge { val value: int } val hoge = new Hoge(123); ↓ スタック割付け最適化 val hoge のvalue: int = 123; // hoge.value の読み書きはこれを使う リスト等のイテレーターの最適化 等で無意識にかなりの恩恵を受けている。 11
12. インライン化の前提としての Escape Analysis オブジェクトとしての操作が必要な場合、インライン化はできない。 参照の⽐較、型情報の取得、動的プログラミング (リフレクション) など...。 関数の外部にオブジェクトが露出してしまう (escape する) と上記の保証が不可能。 よって、インライン化は escape していないことが前提になる。 12
13. ⼊れ⼦オブジェクトのインライン化 (Scalar replacement) 同様に、オブジェクトの中のオブジェクトを展開する最適化もある: class SomethingId { val raw: int } class MyObject { private val id: SomethingId } ↓ インライン化 class MyObject { private val id のraw: int // SomethingId#raw の読み書きはこれを使う } Value object (プリミティブ型のラッパー)やタプル的な型( RGB や Vector2D など)で恩恵を 受けていることがあったりする。 13
14. オブジェクトの可視性 ⾔語によっては、スレッドをまたぐオブジェクト受け渡しに⼀定の保証がある (JVM の safe publication , Golang の channel , Apple の GCD など)。 例: サーバーサイドや GUI の実装でありがちな処理: 1. new Something() する 2. それをキューに⼊れる 3. 別スレッドが上記オブジェクトを参照する 1 のオブジェクトへの書き込みが 3 のスレッドから⾒えることが保証されてほしい。 14
15. メモリモデルとキャッシュのトレードオフ ⼀般にメモリへの書き込みは register や L1/L2/L3 cache に貯めてから書き込む。 しかしそれでは new Something() によるメモリ書き込み(の⼀部)が別スレッドに⾒えない といった事象が発⽣しうる。 したがって、メモリモデルの保証を満たすためには cache からの write back や、CPU コア間 の同期(MESIF, MOESI といった同期プロトコル)の通信が発⽣する。 15
16. 他スレッドから⾒えないオブジェクトの最適化 他スレッドから⾒えないならば、register や L1/L2/L3 cache からメモリに書き戻す必要はな い。 オブジェクトを CPU コア間で同期する必要もない。 なので escape しないオブジェクトについてはメモリ書き込み処理を⾼速化できる。 ( ついでに swift の ARC のような参照カウントも省略出来る ) 16
17. ラムダ式のクロージャーに起因するキャプチャー function something() { val x = 123; function lambda() { x = 456; } } ラムダ式は外側の変数を読み書きする事ができる (モダンな⾔語なら)。 上記の例における x 変数は something 関数のローカル変数だが、 もし lambda インスタンスが escape するならば、 x も something 関数のスコープを超 えて参照される (キャプチャー)。なので x がメモリ上に配置される。 escape しないと断定できると、変数をスタック上に置いたままにできるのでかなり⾼速にな る。 17
18. まとめ: Escape Analysis と最適化の関係 オブジェクトの展開 (スタック割付け, Scalar replacement) オブジェクトのインライン化 キャッシュ write back の省略 ロック・Atomic メモリ操作の省略 ラムダ式のクロージャーの最適化 ... これらの最適化は escape しないことが前提。 なのでコンパイラ・JIT は Escape Analysis する必要がある。 18
19. 2: Escape Analysis と⾔語機能の関係 19
20. Escape するかどうかは⾃明ではない 何らかの関数 () { val something = new Something(); something.foobar(); return; } something は関数のスコープから escape するか？ 20
21. メソッド・プロパティの実装に依存 何らかの関数 () { val something = new Something(); something.foobar(); return; } class Something { foobar() { baz.onClick = () => { // ラムダ式 alert("Hello World!"); } } } この場合 something は escape しない。 21
22. メソッド・プロパティの実装に依存 何かの関数 () { val something = new Something(); something.foobar(); return; } class Something { foobar() { baz.onClick = () => { // ラムダ式 this.barbaz(); // ここが something を参照 } } } この場合は escape する (onClick に⼊れた lambda が this 経由で Object を escape)。 22
23. Escape Analysis とメソッドの実装依存 メソッドの呼び出し先のメソッドの ... 経由で escape する といった可能性があるので厄介。 どうやって escape しないと断定するか？ 23
24. 構造体 (struct) の活⽤ C, C++, C#, Swift 等の構造体( struct )は Escape Analysis に優しい。 これらの⾔語の struct の寿命は変数のスコープと常に⼀致するため、呼び出し先のメソッ ドの実装云々に関係なく escape しないことを断定できる。 ( なお Golang の struct は escape 可能であり、このようなメリットはない ) なお、 struct は変数間の代⼊でコピー渡しのオーバーヘッドが発⽣しうることもあり、 class などの⾔語機能より常に優先して使うべきということではない。 24
25. コンパイル時の情報に基づく解析 C, C++, Swift, golang のように機械語へコンパイルする⾔語では、 当然ながらコンパイル時の情報のみで Escape Analysis する。 たいては以下のような判定をしている: コンパイル時に呼び出し先が確定しない関数の引数に渡しているならば NG その関数の中で escape するかもしれない 当該オブジェクトの参照をグローバル変数・インスタンス変数などに⼊れていれば NG なお、golang ならば -gcflags='-m' で Escape Analysis とインライン化の結果が分かりや すく出⼒される。 25
26. Compiler directive ⼀部の⾔語には Escape Analysis を助けるための⾔語機能がある: C, C++ における noescape や clang::noescape 属性 Go の //go:noescape これらを明⽰することで Escape しないことをコンパイラに伝えられる。 ただし使い⽅が間違っていると何がおきてもおかしくないので、⾃⼰責任で。 26
27. コンパイル時の解析を妨げる、ありがちな⾔語機能 呼び出し先の関数が確定しないケースで、どうにもならなくなりがち: ポリモフィズム・オーバーライド オーバーライドできる = 引数を escape する実装になっているかもしれない ラムダ式や関数ポインタ ラムダを呼び出す側にはラムダの実装がわからない = 引数を escape しうる これらがあると、escape するものと想定せざるをえず、各種最適化ができない (ことが多い)。 27
28. 実⾏時情報に基づく最適化 (JIT) JIT であれば、実⾏時の情報を使うことでさらなる最適化が可能。 こういった場合に、呼び出し先の関数の実装が⼀意に確定する: 継承やオーバーライドが可能だが実際にはされていないメソッド 中⾝が常に決め打ちのラムダ式や関数ポインタ なので呼び出し先の関数の実装内容に依存した Escape Analysis ができる。 少なくとも JVM や V8 はこのような最適化をしている (後述の参考資料を参照)。 28
29. Deoptimization (脱最適化) 実⾏時の挙動によって、最適化の前提が崩れることがある: 後からロードされた class によるオーバーライド JVM は class を遅延ロードする仕様 動的コード⽣成によるオーバーライド Aspect Oriented Programing (トランザクション制御など) シリアライザや O/R mapper 等 関数の実装の動的な差し替え mock ライブラリ等 ⾼度な⾃⼰書き換え型プログラムなど JIT はこういったケースを検知し、最適化の前提が崩れているケースでは最適化前のコードに 戻すことで正しく動作する (deoptimization)。 Deoptimization による性能低下は micro benchmark では⾒逃されがちな要素。 29
30. "早すぎる最適化は諸悪の根源" -- ドナルド・クヌース 性能・最適化の議論で⼀般に陥りがちな過ちに対する警句。 性能・最適化の議論をするときは必ず⼼に留めておくべき。 30
31. とはいえ、スコープは⼩さくすると良い 「スコープを⼩さくする」のはプログラミングのベストプラクティス。 Escape analysis や最適化関係とは独⽴に、オブジェクトの⽣存区間を不必要に⼤きくしない コーディングには意味がある。 「変数のスコープを⼩さくする」だけでなく「オブジェクトのスコープを⼩さくする」のもメ ンテナンス性・バグ予防・読みやすさに効く。 31
32. Appendix: Escape Analysis 参考資料 いろいろな⾔語処理系の公式情報: JVM (HotSpot): EscapeAnalysis - OpenJDK wiki JVM (Java, Kotlin/JVM, Scala) の JIT における Escape Analysis Escape Analysis に限らず、JVM (HotSopt) の JIT はとっても強い V8 (JS): Escape Analysis in V8 GraalVM: Under the hood of GraalVM JIT optimizations Golang: Go Escape Analysis Flaws Swift: github.com/apple/swift の EscapeAnalysis.cpp PyPy: Escape Analysis in PyPy's JIT CPython はおそらく Escape Analysis していない CRuby: Ruby 2.6 JIT - Progress and Future CRuby は Escape Analysis をまだ実装していない ※ 処理系の進歩が資料に反映されていない可能性が⼤いにある 32
33. Appendix: Happens(-ed) Before 並列処理をきちんと考慮しているプログラミング⾔語では Memory Model が仕様として定義 されている。 Memory model 仕様が定義されている⾔語の例: Java (>= 5), C++11, C11, C#, Golang 最近の model は Happens Before という概念で構成されていることが多い。 Happens Before はプログラム上の操作の半順序関係 (全順序ではない)。 順序が定義されない 2 操作が同じオブジェクト・メモリを操作してるとスレッドセーフでな い。 33