こんにちは、todeskingです。
ScalaMatsuri 2016将軍スポンサーが合同で開催した「Scala将軍達の後の祭り」 というイベントで、バイトコードの実行時最適化について発表してきました。
抽象化によってオーバヘッドが存在するコードを実行時にバイトコードレベルで最適化すれば、抽象化とパフォーマンスが両立出来てお得、という夢のある話です。
以下、補足など。
なぜ実行時に最適化するのか
これにはいくつか理由があって、
- 安全性
- クラスの解決は実行時に行われるため、コンパイル時と実行時で見えているクラスが違うということがありえます。 そのため、静的に大域的な最適化をする場合は、実行時にクラスパスが変化しないことを保証する必要が出てくる
- 解析が楽
- 実際に構築されたインスタンスを元に最適化できるので、フィールドの値に基づく最適化が楽
- 柔軟性
- 実行時になるまでインスタンスの内容が確定しない場合(外部入力に依存していたり、遺伝的プログラミングのように動的に作成される場合) でも最適化が可能
などです。
このような最適化をマクロで実現できないか
コンパイル時にやる場合は局所的な最適化しかできないので、処理が分散している場合は限定的な効果しか ないのではないでしょうか。メソッドのインライン展開はできても、関数合成の最適化は難易度が高いように思います。
「Arrowの構築に伴う関数合成を最適化したい」というように、目的を限定したDSLを作ってマクロでバリバリやったらいけるかもしれない。
ちなみにマクロによって抽象化のオーバヘッドをゼロにする試みとしては、implicit parameterを使用した演算子呼び出しを最適化する machinistプロジェクトなどがあるようです。
また、HaskellではRewriteRuleという機構で、コンパイル時に式を書き換えて最適化する仕組みがあります。
Android環境でオーバヘッド削減できると嬉しいのでは
確かにリソースの少ない環境のほうがオーバヘッド削減の恩恵は受けやすそうです。
ただしそのような環境だと、実行時よりもアプリケーションのパッケージ時(実行時に使うライブラリが確定した状態)に大域最適化をかけるような 手法のほうがいいかも?
バイトコード最適化手法については、静的に行う手法のほうが事例が多そうなので、掘ったら何か出てくるかもしれません。
データフロー解析について
力尽きて資料に書き忘れたんですが、メソッド開始時のフレームを用意→バイトコードごとにフレームの更新を計算、 制御フローの合流が発生した場合はフレームをマージして再計算、というのを収束するまでやっています。
JVMが使用しているメソッドの型検証アルゴリズム(JVMS8 4.10.2.2)を参考にして、型だけでなく値も計算しています。
この情報があると、特定のインスタンスに対するメソッド呼び出しのみ選択したりできるので便利。
実用性について
まとめに書いたように、用途はかなり限定されます。 普通は他の部分(IOなど)がボトルネックだし、あくまでも不用な処理を削減するだけなので効率的なコードに対してはそれほど効果がない。
CPUがボトルネックだったりレイテンシを極限まで減らしたい場合で、しかも抽象化は捨てたくないというニッチな需要に有効です。
最初に出てきたモジュラーシンセ作る話はどうなったのか
バイトコード操作に必死だったので進捗がない
ソースコード
- arrow_builder
- Chapter 2で紹介した、forでArrow作るやつです
- fast_function_composer
- Chapter 5で紹介した、クラスの動的生成やMethodHandleを使用して関数合成の高速化をこころみたものです
- Unveil
- Chapter 6で紹介した、クラスの変形によって汎用的な手法でさらなる高速化を目指したものです
参考文献とか
今回の実装には無関係なものもありますが、せっかくなのでまとめておきます
モジュラーシンセ関係
- シンセサイザーがわかる本、 達人と作る アナログシンセサイザー自作入門、 Make: Analog Synthesizers
- Giorgidze, George. Modular Synthesizer Programming in Haskell. Diss. MSc Dissertation, Department of Computer Science and Engineering, Division of Computing Science, Chalmers University of Technology and The University of Gothenburg, Gothenburg, Sweden, 2008.
ArrowとFRP関係
- Hughes, John. "Generalising monads to arrows." Science of computer programming 37.1 (2000): 67-111.
- Nilsson, Henrik. "Dynamic optimization for functional reactive programming using generalized algebraic data types." ICFP. Vol. 5. 2005.
- Liu, Hai, Eric Cheng, and Paul Hudak. "Causal commutative arrows and their optimization." ACM Sigplan Notices. Vol. 44. No. 9. ACM, 2009.
- 特殊なlawを満たすAllowLoopであるCausal Commutative Arrowを使うことで、変形による最適化がしやすくなるという話。
今回の領域だとArrowの変形による最適化はぜんぜん助けにならないという印象なんですが(Scalaにおいてはそもそも関数合成が重い)、 バイトコードの変換と併用した場合は何か有効な結果が出るのかもしれません。
JVMバイトコード関係
- Java Virtual Machine Specification, Java SE 8 Edition
- これを読めばJVMの仕様はすべてわかるすごいドキュメント。 とは言っても実装側の都合で書かれているので、知りたい情報がどこにあるか探すのはけっこう骨だったりする。
- Section 4-6をじゅくどくすればだいじょうぶです(多い)。
- 石崎一明, "Java Just-In-Time コンパイラ", PPL Summer School 2004, 2004
- Bosboom, Jeffrey. StreamJIT: A Commensal Compiler for High-Performance Stream Programming. Diss. Massachusetts Institute of Technology, 2014.およびStreamJITプロジェクト
- Koopman, Philip. "A preliminary exploration of optimized stack code generation." (1995).および Bailey, Chris. "Inter-boundary scheduling of stack operands: A preliminary study." Procedings of EuroForth 2000 (2000): 3-11.
- JVM Backend and Optimizer in Scala 2.12