はじめに
Rustでマルチスレッドプログラミングを行うとデータがスレッド間で競合するところはMutex型のtraitでくるまないと型エラーになるので安全であるという話を良く聞きます。これはとても優れたデザインなんですが、そこまでやるのであれば競合するところに勝手にMutexを入れてほしいと思うのです。
ちょっと考えてみたら抽象解釈を利用すればそれが可能であることに気づいて、mmcにマルチスレッド対応の機能を入れてみました。これは競合するオブジェクトをレシーバーとするメソッド呼び出しやインスタンス変数のアクセスに自動的に排他制御が入るというものです。
mmc
mmcのマルチスレッド化のために簡単にmmcの説明を行います。詳しくはを参照してください。
mmcは抽象解釈という技術を使って型解析やエスケープ解析を行い、mrubyのバイトコードを高速なC言語に変換するトランスレータです。抽象解釈では通常のインタープリテーションと同様にmrubyのバイトコードを実行していきます。ただし、通常のmrubyの処理系と違い値ではなく型情報レベルで実行します。抽象解釈で型情報があたかも値の様に伝搬していくことで変数・オブジェクト・メソッドの戻り値などの型が推定できます。同時に値がどこに格納されるかを記録することでエスケープ解析を行うことも出来ます。
mmcでは大きく2つの部分からなります。一つは抽象解釈の部分で一旦プログラム全体を型レベルで実行します。型レベルではループなどは繰り返さないので実際に実行するのに比べれば短時間で実行できます。これをPASS 1と呼ぶことにします。
もうひとつはCへの変換です。PASS 1で得た型の情報やエスケープの情報を使用してC言語に変換します。この中で gen_type_conversion というメソッドが大きな働きをします。これはsrcの型, dstの型を渡して、srcの型からdstの型へ型変換するコードを生成するメソッドです。ロックを掛ける処理はこのメソッドが型変換の一貫として生成します。これをPASS 2と呼びことにします。
オリジナルのmmcではこの２つからなる(正確にはバイトコード列を作る処理があるが今回は割愛)だけだが、スレッド対応にはPASS 1とPASS 2の間に処理が入る。これをPASS 1.5と呼ぶことにする。
mmcのマルチスレッド対応
競合するオブジェクトの検出
競合するオブジェクトを検出するためには複数のスレッドから呼び出されているメソッドを検出することで行います。複数のスレッドから呼ばれているメソッドが分かれば次の節で説明するeffect解析の結果を用いることでどのオブジェクトが競合しているかわかる。effect解析はそのメソッドがどのような副作用を持っているかを解析するもので、オブジェクトの生成やインスタンス変数の読み書きなどの情報を使用する。
PASS 1で抽象解釈中にメソッド呼び出しをした場合、どのメソッドからどのメソッドに呼び出したかを記録していきます。あるメソッドがどのメソッドを呼ぶかの一覧は一見簡単に得られそうですが、Rubyの場合はポリフォリズムやsendメソッドなどのために見た目ほどには簡単ではありません。静的に型を決める必要があります。
PASS 1で得られたメソッドごとにどのメソッドを呼び出したかの情報をPASS 1.5でつなぎ合わせてグラフの形にします。再帰呼び出しを行うと循環ができますので循環にひっかからないようにする必要があります。
effect解析
effect解析はJuliaやOCamlなどで行われている副作用の解析です。mmcでもPASS 1でバイトコードをトラバースする際に副作用の情報を集めるようにしました。副作用としては次のようなものがあります。