最近、自作言語のパーサをパーサコンビネータから手書きの再帰降下法に書き換えているのだけど、あまり手が進んでいない。このパーサの書き換えが終わったら仕様の追加とともにVMの高速化も進めていきたい。ここのはそのVM高速化の手法案を少しメモっとく。
なお、僕は一般的なVMの高速化方法であるjitコンパイルを採用する予定はない。環境依存なコードは極力書きたくないからである。全部普通のRustで書いておけば、環境の違いは全部Rustが吸収してくれるはずなので、どこでも動く言語ができるはずである。
以降高速化方法の案
少ない引数の関数呼び出しの最適化
関数の引数はVecで取り扱ってる。1~3くらいまでは配列で特殊化してアロケーションを回避したら速くなるかな？測定が必要。
1命令のサイズを小さくする。
僕の言語は全ての命令が同じ大きさ (enum) で実装されてる。現状LoadStringとCallMethodが大きいせいで1命令の大きさが32byteになってる。この2つを除けば16byteにできる。頑張れば多分8byteにできる。どうにかしたい。
1つの案としては、アセンブリ言語のように、textエリアだけじゃなくて、データを格納するエリアを設けること。つまり、vmのexecute関数に渡す引数が命令列だけじゃなくて、データも渡す。で、LoadStringではそのデータのアドレスを指すこととする。
これには色々問題があって、文字で書くには少し面倒なんだけど、データ領域に格納できるのを文字列だけに限定して仕舞えば、意外と面倒ではない可能性がある。
文字列専用のデータ領域があれば、CallMethod(Cow<'static, str>, u8)の命令を、CallMethodStatic('static str, u8), CallMethod(データアドレス, u8)の2つに分割することで、命令サイズを24byteに減らせる。CallMethodStaticなくせば16byteになる。
文字列専用にしなければ、静的なArrayとかTableとか↓での命令列とかもデータ領域に保存できるから便利かな？ってなるけど、ちょっとこれはだいぶ複雑になる気がするので考えなきゃいけない。
関数オブジェクトのキャッシュ
関数オブジェクトは命令列をVecで保存している。そのため関数オブジェクトを生成するとき、命令列の数だけヒープアロケーションが発生している。関数オブジェクト内の命令列については不変であるから、キャッシュして再利用したい。
これはヒープアロケーション回避以外の理由でもいい。現在、関数オブジェクトはBeginFuncCreation命令とEndFuncCreation命令に挟まれた命令をコピーして、関数オブジェクトのVecに取り込んでる。このコピーのための命令列の走査もなくせる。
これの実装方法は、キャッシュ領域をランタイムに設ける＋命令列の動的な書き換えで実装できる。
BeginFuncCreation(u8)とかにして、u8の初期値は0。0の時はキャッシュされていない。関数オブジェクトを初めて生成した時、その命令列をキャッシュして、u8の値をキャッシュした場所のアドレス(0以上のであるとする）とすればいい。u8が0じゃなければ、キャッシュから復元して、その命令列の長さの分だけJumpすればEndFuncCreationに飛べるはず。
関数オブジェクトの生成にはキャプチャの生成とかがあるんだけど、これらはキャッシュが難しいから毎回やる。だからほんとは↑に書いたようなキャッシュの復元→Jumpではないんだけど、まあ、そんな感じでできるはず。
ハッシュ計算のキャッシュ
AHashアルゴリズムを使うならキャッシュ＋命令列の動的書き換えで高速化できるはず。
AHashは、実行単位が同じなら(1つのプログラム内なら)、同じバイト列に対して同じハッシュを生成する。BeginFuncCreationの時と同様、GetItemとかSetItem命令に加えて、GetItemStr(文字列)を追加して、GetItemStr命令をを動的にGetItemHash(u64)に書き換えれば2回目以降はハッシュの計算をスキップできる。