「私には夢がある。それは、いつの日か、私の４人の幼い子どもたちが、静的型の有無によってではなく、機能そのものによって評価されるプログラミング言語を使うという夢である。」
https://americancenterjapan.com/aboutusa/translations/2368/
私には4人の子供どころか配偶者もいないですが、まあそんなことはどうでもいい話でしたね。
さて、この夢の実現のために動的型付け言語で静的型に負けない処理系を日夜夢見たり実際に作ったりしています。特にRubyというとても最適化が難しい言語仕様だが、なぜか処理系がいっぱいある言語を主にターゲットにしています。実装が難しい言語をみんなが工夫して優れた処理系を生み出していて楽しいです。
さて今のところ一番大きな成果は抽象解釈(Abstract Interpretation)と言う技法を使ってコンパイル時に型を推定したりエスケープ解析をしたりするプログラムを作ったことです。抽象解釈はとても強力な技法で多くのRubyプログラムに静的に型をつけることが出来、静的型付け言語の特権だった高速な実行速度やコンパイル時のエラーチェックなどを享受できるめどをつけることが出来ました。
しかし、うまくいかないのが世の常というものです。抽象解釈による型の推定はプログラムがサイズやプログラムの性質によっては非常に遅くなり許容できない実行時間になることもたびたびです。特に解析精度を上げるために抽象度を下げた抽象解釈を行うと許容できない実行時間になる確率も上がります。
そういうわけでmrubyで作成した抽象解釈を用いた処理系(Rubyプログラムを静的に型付けしてC言語に変換する、以下mmcと呼びます)はあっさりと限界に当たってしまいました。
そこで、新しく高速な抽象解釈を行うRubyの型推定エンジンを作ることにしました。今回は私の作るプログラムに珍しく最初から名前があります。インドにカルカッタという都市がありますが 軽い 型 のしゃれからこの名前を頂きました。ただ、カルカッタは今では現地の言葉でKolkataと呼ばれているのでそちらを使わせてもらうことにします。
kolkataはここにあります。今の所mruby(しかもとても古いバージョン)のパッチだけです。 https://github.com/miura1729/mruby1
これ、mrubyじゃんって思われるかもしれませんが、コミットログを見てもらえるとなにかやっていることが分かると思います。こんな感じでまだほとんどコードはありません。
Kolkataの概要
Kolkataではmmcの失敗を反省して次のような方針を立てました
- Rubyではなくもっと低レイヤの言語を使う
- データフロー解析を高速化するために工夫する
- 型を表現するデータ構造・アルゴリズムを工夫する
最初の低レイヤの言語を使うと言うことはRubyが遅いから静的型付け言語で高度な最適化を行えば速くなるみたいなことを考えたのかな？と考える方もいるかもしれませんが全くこういう考えもないわけではないですが大部分は違います。
mmcを自作のmrubyのJITで動かしたら2倍ちょっとしか速くならなかったのです。なんだmrubyのJITとやらが遅いだけじゃんと思うと思いますが、確かに遅いのですがベンチマークによっては10倍以上速くなるのです。これはどういう意味かと言いますとmmcの多くがCで書かれたメモリ管理を含むライブラリで実行時間が費やされているということです。
つまりアルゴリズムやデータ構造をそのままにどんな言語で書いたとしても余り速くならないのです。アルゴリズムはデータ構造に従って変わってきますから先ずは高速なデータ構造を考えることが何より大切になります。そして狂ったように高速なデータ構造は多くの場合低レイヤな処理、たとえばビット演算がSIMDな命令の使用など低レイヤの言語が得意な処理になります。
他の2つはいろいろ伝えたい話があるので章を変えてお話します。
データフロー解析の高速化
データフロー解析は最適化などのためにプログラム中のデータの流れを解析する処理です。データフロー解析によってある命令でセットしたVMレジスタの値がどこで参照されているかなどを知ることが出来ます。最適化の際には沢山使われていたり寿命の長いVMレジスタをCPUレジスタに割り当てるみたいな最適化を行ったりするわけです。データフロー解析は高速化にも役立ちます。例えばレジスタに代入するけど以後全く使われない値に型をつける必要はないわけです。Rubyの場合、メソッドの返り値を捨てるなどで実は結構あります。
データフロー解析そのものは無茶苦茶重い処理というわけではないですが、抽象解釈の場合は何度も何度も繰り返します。そういうわけで速ければそれに越したことはないのです。
また、将来高速な型推定が可能になったらこれを利用して高速なインタープリタを作りたいと考えています。この場合はデータフロー解析も実行時間の一部になりますのでなおさら速度が要求されます。
データフロー解析のためにKolkataではビット演算を使用することにしました。
ビット演算によるデータフロー解析
データーフロー解析において色々な登場人物が現れます。例えば、
- 基本ブロック
- レジスタ(の読み書き)
これらのバイトコード列上の位置をビットマップとして表現します。
例えば、
000 OP_PHI R0 000 (0)
001 OP_ENTER 0:0:0:0:0:0:1
002 OP_PHI R0 002 (0)
003 OP_LOADSELF R3
004 OP_SEND R3 :size 0
005 OP_MOVE R2 R3
006 OP_LOADI R4 1
007 OP_GT R3 :> 1
008 OP_JMPNOT R3 017 (9)
009 OP_PHI R0 008 (-1)
010 OP_PHI R0 010 (0)
011 OP_LOADSELF R3
012 OP_LOADI R4 0
013 OP_MOVE R5 R2
014 OP_SUBI R5 :- 1
015 OP_MOVE R6 R1
016 OP_SENDB R3 :__sort_sub__ 2
017 OP_PHI R0 008 (-9)
018 OP_LOADSELF R3
019 OP_RETURN R3 normal
のようなバイトコードがあったとします。ここでOP_PHIという見慣れない命令がありますが、これはジャンプ命令の飛び先を意味しています。基本ブロックの境界になりますし、その直前の命令を見ることで制御が合流しているのか判定することも出来ます。SSA(静的単一代入)におけるPHI命令の様なイメージです。
ビットマップとしてPHI命令の位置に1を立てた物を用意します。これをnormal.phiと名付けます。normalがあると言うことはnormalじゃない物もあるのか？と思いますがこのビットマップを逆順にしたreverse.phiも用意します。なぜ必要なのかは後で説明します。
そうすると、normal.phiは次のようなビットマップになります。実際には縦の命令列を64bitのワードの中に詰め込んで表現します。normalは0番地の命令のビットが0ビット目になります。64命令以上ある場合はワードが複数になります。
PHI
000 OP_PHI R0 000 (0) 1
001 OP_ENTER 0:0:0:0:0:0:1 0
002 OP_PHI R0 002 (0) 1
003 OP_LOADSELF R3 0
004 OP_SEND R3 :size 0 0
005 OP_MOVE R2 R3 0
006 OP_LOADI R4 1 0
007 OP_GT R3 :> 1 0
008 OP_JMPNOT R3 017 (9) 0
009 OP_PHI R0 008 (-1) 1
010 OP_PHI R0 010 (0) 1
011 OP_LOADSELF R3 0
012 OP_LOADI R4 0 0
013 OP_MOVE R5 R2 0
014 OP_SUBI R5 :- 1 0
015 OP_MOVE R6 R1 0
016 OP_SENDB R3 :__sort_sub__ 2 0
017 OP_PHI R0 008 (-9) 1
018 OP_LOADSELF R3 0
019 OP_RETURN R3 normal 0
データーフロー解析においては基本ブロック内と基本ブロックを跨ぐ解析は全然異なった処理を行う必要があります。そのため、基本ブロックを何とかして切りだす必要があります。通常はDAGと呼ばれるグラフ構造を作ったりするわけですが、余分なメモリ割り当てや書きこみが必要になります。しかし、normal.phiビットマップがあれば、引き算とxor命令などの論理演算数個でビットマスクを作ってandを取ることで基本ブロックを切りだすことが出来ます。もちろん、命令の情報がビットマップで表現されている必要がありますが、全てのレジスタについて読み書きの位置を表したビットマップを用意しています。
normal.dst[3] normal.src[3]
000 OP_PHI R0 000 (0) 0 0
001 OP_ENTER 0:0:0:0:0:0:1 0 0
002 OP_PHI R0 002 (0) 0 0
003 OP_LOADSELF R3 1 0
004 OP_SEND R3 :size 0 1 1
005 OP_MOVE R2 R3 0 1
006 OP_LOADI R4 1 0 0
007 OP_GT R3 :> 1 0 0
008 OP_JMPNOT R3 017 (9) 0 1
009 OP_PHI R0 008 (-1) 0 0
010 OP_PHI R0 010 (0) 0 0
011 OP_LOADSELF R3 1 0
012 OP_LOADI R4 0 0 0
013 OP_MOVE R5 R2 0 0
014 OP_SUBI R5 :- 1 0 0
015 OP_MOVE R6 R1 0 0
016 OP_SENDB R3 :__sort_sub__ 2 1 1
017 OP_PHI R0 008 (-9) 0 0
018 OP_LOADSELF R3 1 0
019 OP_RETURN R3 normal 0 1
例えば、R3の書き・読みのビットマップ(normal.dst[3], normal.src[3])は次のようになります。
normal.dst[3]を先ほど説明したnormal.phiで求めた基本ブロックのマスクとandを取ることで基本ブロック内でR3をどこで書きこんだかのビットマップが出来ます。1の立っている位置ごとにマスクを作ってnormal.src[3]とandを取ることであるR3への書き込みがどこで使われたのかのリストが得られます。
また、基本ブロック内で他の基本ブロックからやってきた値を参照している場所を知りたい場合があります。このような場合は基本ブロック内でレジスタが書きこまれる前に参照している場合なわけですが、これはビットマップをあたかも2進数の値として比較することで判定できます。ただし、ビットマップの位置が命令のアドレスが若いほど上位にあるような配列である必要があります。このようにビットマップの操作はビットの並びの向きで出来ることが対照ではないので、命令アドレスが若いほどビット位置が下位であるビットマップnormalとビット位置が上位であるビットマップreverseを用意しています。
基本ブロックを跨いだデータフロー解析はかなり複雑なので今も検討中なのですが、IntelなどのBMI2拡張命令を使えると何とかなりそう。速いCPUのPC欲しいなー
ビットマップを用いたデータフロー解析のためのアイデアをまとめた物です。アイデアの殴り書きなので読みにくいし一部古い情報もあります。何かに使えるかもしれないのであえて消していません。 https://docs.google.com/presentation/d/1mAgbPzW62nc0JO-760SPkXDx2wF4ZIB-_IZq6QWPe6c/edit#slide=id.g13e11d566e0_0_10
型を表現するオブジェクト
抽象解釈による型推定においては、その地点でレジスタが取りうる型を求めるのに複数のルートからの実行した結果をマージする必要があります。
例えば次のようなプログラムを考えてみます。
この場合、制御が合流するところではxの型はFixnum | Floatというユニオン型になります。
このマージにおいて2つの型が同じであることを判定する処理が必要になります。2つの型が同じならユニオン型を作る必要が無いからです。そして、この2つの型が同じであるかどうかの判定は多くの場合でプログラム全体で一番時間がかかる処理なのです。もちろん、ユニオン型を作る処理も型の比較ほど沢山あるわけでないので目立たないですが、さらに重い処理です。
また、flow-senstiveな解析と言う物も沢山使うのでこれも考慮する必要があります。flow-senstiveな解析はこんな感じです。
このように一時的に型に関する条件を重ねたり取り外したり出来るように出来る必要があります。Kolkataではnil?/is_a?のような型に関するものだけではなく、Fixnum#<のような値に関するものもサポートしたいと思っています。
そんなこんなで、型を表現するオブジェクトは次のような条件を満たすものであると言えます。
- 同一性を高速に判定できること
- 高速に生成出来ること
- 型や値に関する制限を指定することが出来(篩型みたいな感じ)、一時的に付加・取り外しが出来ること。
mmcでは型を制限も含めてでっかい1つのオブジェクトで表していましたが、Kolkataでは複数の要素の組み合わせとして表現することを考えていますが、まだ固まっていません。C言語で実装するのでメモリ管理の方法も考える必要があります。とりあえずは参照カウントかなと思っています。今の所循環参照は無いでしょうし。
おわりに
ちょうど去年の12月13日このような記事を投稿しています。
https://qiita.com/miura1729/items/9b932933c673a0b4f34e
まさにこの続きの話だったわけですが、書き始めた時は進捗ないなー、と思いました。しかし、書き始めるとこの辺のバイトコードの仕様は今は亡き愛犬の散歩で考えたなとか、ビットマップによるデータフロー解析の詳細は夏の地元の祭りに参加中に山車の後ろを歩きながら考えたなとかプログラミング以外の生活とも結び付けて思いだされます。進捗に追われないでゆっくり考えることが出来ることが趣味のプログラミングの醍醐味ですので来年もゆっくり考えることでしょう。
来年の12月13日も可能ならここでお会いしたいです。どういった内容になるかは今は誰もわかりません。