一人一党党

一人一人の、一人一人による、一人一人のための政治制度を!

累積レジスタ割付による仮想マシンの高速化

この記事は
言語実装 Advent Calendar 2019 - Qiita
https://qiita.com/advent-calendar/2019/lang_dev
の5日目のために書いた。

言語実装に興味のある人ならコンパイラにも興味があるはずで、コンパイラに興味のある人なら、一度はコンパイラを実装しようとして、コンパイル先命令セットの選択に悩むはず。
スマートフォンの枠を越えてWindowsにまでARMが進出を始めている上に、大学発の命令セットとしてRISC-VがMIPS再来の如く台頭する中、x86ベッタリのコードは恐い。
PA-RISC,Alpha,IA-64(Itanium)…、物理マシンの命令セットは製造元の都合で将来性を絶たれてしまう。
この時、JavaやInfernoのように仮想マシン命令セットに行き着くのは、言語実装に興味のある人ならよくあること。

そんな用途に最も向いていると現在私が考える仮想マシンが、「累積レジスタ割付」を前提とするレジスタマシンだ。
「累積レジスタマシン」とでも呼ぼうか。
レジスタの数に上限のない仮想レジスタマシンの一種なのだが、レジスタの性能に偏りがあり、番号の若いものほど性能が高くなるように仮想レジスタが並んでいる。
これにより、言語処理系を実行時(JIT)コンパイラと事前(AOT)コンパイラに分ける場合に、性能劣化を大きく抑えることができる。

普通の仮想レジスタマシンでは、たとえ仮想レジスタの数に上限がなくとも、どの仮想レジスタも性能が等しいという建前になっている。
このため、変数に割り付ける仮想レジスタの選択に事前コンパイラは悩まずに済む。
使用頻度が高いなどの重要な変数を置くのに、どの仮想レジスタを選んでも性能に違いは生じないからだ。
勿論、物理レジスタの数には上限があるから、全ての仮想レジスタに物理レジスタを割り付けることはできず、物理レジスタを割り付けるものとメモリで済ますものに分ける必要がある。
物理レジスタの数は物理マシンによって異なるから、仮想マシンの仕様しか知らない事前コンパイラでは物理レジスタの割付を行えず、実行時コンパイラですることになる。
が、実行時コンパイラでは、どの仮想レジスタに重要な変数が置かれているか知ることが難しい。
仮想レジスタの選択を事前コンパイラは悩まないので、デタラメに行うからだ。
実行時コンパイラの重さは事前コンパイル済みプログラムの実行時間に加算されるので、実行時コンパイルされたコードの性能向上による実行時間短縮効果を打ち消してしまいかねず、あまり強力な解析を実行時コンパイラはできない。
結果、普通の仮想レジスタマシンでは物理レジスタの活用が難しい。

これに対して累積レジスタマシンでは、仮想レジスタの性能に偏りがあるので、変数の重要性に応じた性能の仮想レジスタを割り付けることで、事前コンパイラ仮想マシン向けコードの性能を高めることができる。
2018年6月17日のブログで触れた論文は、そのようなマシンでのレジスタ割付アルゴリズムを「cumulative register allocation」と呼び4種類ほど紹介している。
"Combining Offline and Online Optimizations: Register Allocation and Method Inlining" by Hiroshi Yamauchi and Jan Vitek
https://pdfs.semanticscholar.org/9a4a/d55afd9159f037aa163cbf4a5a770a49999c.pdf
直訳すれば「累積レジスタ割付」となるだろうか。
実行時コンパイラからすれば、仮想レジスタの番号順に、重要性の高い変数が置かれているように見える。
このため、仮想レジスタへの物理レジスタ割付は簡単で、番号の若い仮想レジスタから順番に物理レジスタを割り付ければ良い。
レジスタ割付が済んでいるので、仮想命令の前後関係を考えずに命令単位でコンパイルするだけで良く、実行時コンパイラが簡単・高速になる。
事前コンパイラは重くなるが、事前コンパイルされたプログラムの実行時間には加算されないので、あまり問題にならない。

問題は、仮想マシンを介してコンパイル・実行されるコードの性能だ。
物理マシンの命令セットへ直接コンパイルする場合は、物理レジスタの数についての知識を事前コンパイラは使うことができるが、仮想マシンへの場合はそうではない。
物理レジスタ数が分かっている状態で行う通常のレジスタ割付アルゴリズムと比べて、累積レジスタ割付の出力するコードの性能はどれくらい落ちているのだろう?
先の論文では、先ほどの4種類の累積レジスタ割付アルゴリズムと、仮想マシン内の物理レジスタ数を知らされた通常のレジスタ割付でベンチマークを採っている。
それらのベンチマークを平均すると、通常のレジスタ割付に対する累積レジスタ割付の性能差は4%以内。
ベンチマークの種目によっては-6%から+10%まで幅がある。
驚くべきことに「-6%」、つまり、物理レジスタ数を分かっている通常アルゴリズムの吐いたコードよりも6%速い結果が観測されたらしい。
ベンチマークのデータ品質が悪いからとも言えるが、4%の差は誤差の範囲だろう。

先に述べたように、仮想累積レジスタマシンでの実行時コンパイラは、実行時コンパイラとしては簡単な方だ。
しかし、移植性が高くてラクチンな、純粋なインタプリタ仮想マシンを実装したいこともあるだろう。
その場合の速度はどうだろう?
結論から言えば、累積レジスタマシンはレジスタマシンの一種だから、最も高速な部類に入る。
"Virtual Machine Showdown: Stack versus Registers" by Yunhe Shi
https://scss.tcd.ie/publications/tech-reports/reports.07/TCD-CS-2007-49.pdf
勿論、レジスタ数に上限がないので、厳密には各仮想命令のoperand fieldは可変長になり、単純なインタプリタ実装では速度は得られない。
しかし、ここでも普通のレジスタマシンとの違いが効いてくる。
累積レジスタ割付により若い番号のレジスタの使用率が上がるので、大きな番号のレジスタを使う頻度は普通のレジスタマシンよりずっと少ない。
ならば、大きなレジスタを扱う仮想命令は動作の確保に留め、効率の追求は若い番号のレジスタしか扱わない仮想命令でのみ行う設計にすればどうだろうか。
例えば、同じ演算を行う仮想命令を二つずつ、若い番号のレジスタしか扱わないoperand fieldが固定長のものと、レジスタ番号に上限はないが効率の悪いものを用意するとか。
累積レジスタ割付により殆どの仮想命令は効率的な方のが使えるので、性能は殆ど落ちないだろう。

このように、コンパイル先に選ぶ仮想マシンとして累積レジスタマシンは最適だと私は考えている。
この記事がコンパイラ作成に挑戦する人の参考になれば幸いだ。