Rust で Erlang 処理系を実装してみている

今年の 9 月あたりから、 Rust で Erlang の処理系を実装してみています。まともに試せるほど進んでないんですが、気分的に年内に一区切りつけたいので公開しておきます。リポジトリはこちら。

https://github.com/szktty/starlight

みています、というのはもちろん思いつきだからです。なにぶん Erlang は適用分野がベリーハードなミッションクリティカルシステムしかなく、あらゆる性能やメリットが Erlang VM (BEAM) を超えなければ非公式処理系の用途はありません。 かといって最初から諦めてもいませんが、業務で Erlang に関わらなくなったら or 開発に疲れたら自然消滅すると思います。すでにわりと疲れている。

進捗状況

「速くなるのか？」「軽量プロセスは？」などの疑問に興味津々の皆様、すいません。全然ご期待に応えられません。本当に同梱のごく少数のサンプル程度しか動かせません。いやマジで。

Erlang の文法は構文解析するには非常に複雑で、 VM 以前にコンパイラの実装に苦労しています。 Erlang の lint (開発止まっちゃってますが) で用意した構文解析器が不完全ながらあったので流用しましたが、一から実装したらもっと時間がかかっているでしょう。加えて、後述しますが VM をレジスタマシンからスタックマシンに実装し直したので、全然進んだ気がしません。

動機

識者は Erlang は遅いと言います。私は Erlang アプリケーションやサービスの開発も運用もやってないのでどの程度遅いのかわからないんですが、少なくとも NIF の出番が多い程度には遅いようです。そのためか、 Erlang ユーザーは他の言語での開発も視野に入れているようです。

ただし、高速さだけでは候補になりません。 Erlang はとにかく VM が落ちません。 Erlang より高速かつ、 Erlang と同等またはそれ以上に堅牢な処理系が求められます。

そこで候補として期待される言語の一つが Rust です。期待される Rust の特徴はこんなところでしょう。

• 速い
• メモリ安全
• 型安全
• GC がない

「遅いが落ちにくくてスケールする」 Erlang アプリケーションが、 Rust で実装し直したら「速くて落ちにくくてスケールする」ようになるのかどうか。気になる人は多いと思います。

BEAM は十分に枯れていて、残る最適化方法は JIT くらいだと思います。すでに HiPE という事前ネイティブコンパイラがありますが、銀の弾丸とはいかないようです。また、 VM にコミットする人も企業もほとんどおらず、本家以外の処理系の実装にチャレンジしようとする人もほとんどおらず (有名どころに Java で実装された Erjang があります) 、だったら Erlang の処理系を Rust で実装してみたらどうか？と思っていました。もし Erlang VM 以上のパフォーマンスが出るなら、既存の資産を利用できます。

コンパイラについて

コンパイラは OCaml で実装しています。コンパイラのような非ランタイムのツールの実装言語まで Rust で統一する必要はないと思います。つまりは私にとって OCaml の生産性 ＞ Rust の生産性です。 VM よりコンパイラの実装で悩んだ時間のほうが多いので、 Rust だと個人的に厳しいですね。体感 8 割くらいはコンパイラに費やしている気がします。 Erlang の構文解析ライブラリを使うとか Core Erlang を解析するなどの方法もありますが、すべて自作できれば融通が利きますし、できれば依存したくなかったので。

幸い、作りかけの Erlang lint で用意した構文解析器が不完全ながらあったので流用できました。 Erlang の文法は解析するとなると非常に複雑で、 Rust で一から実装するのはしんどいです。ついでに言うと Erlang は仕様面でもトリッキーで、同時に複数のリストを生成できるリスト内包表記や、 case 式のパターンマッチで使われる変数がスコープ外でも残る変数スコープなど、実装しても達成感より徒労感のほうが強い or 強そうな仕様が多々あります。はっきり言って楽しくない。

もっとも、今なら割り切って Elixir をターゲットにすべきなのかもしれません。一応コンパイルのフェーズを 抽象構文木 -> 中間表現 -> バイトコード生成 の3段階に分けているので、 Elixir の構文解析器と中間表現へのコンパイラを実装すれば、バイトコード生成を気にしなくて済むようになっています。

実行速度について

Erlang は業務で使われている方々から遅い遅いと言われます。実際現場では苦労されているようです。ですが、 VM 命令の実行ループだけ見れば (非ネイティブコンパイル言語と比べると) 速い部類に入ります。それもかなり。

では Rust で実装したらどうなるか？ ぶっちゃけ普通に実装したら遅いです。それもかなり。素直に実装してみてわかった理由をいくつか挙げます。私の実装方法にも問題があるでしょうが、概ね共通するのではないかと思います。

ダイレクトスレッデッドコードが使えない

現時点の Rust (1.31.0) では、命令分岐を最適化するダイレクトスレッデッドコードという手法が使えません。列挙型を使うにせよ整数を使うにせよ、パターンマッチで命令を分岐するしかありません。

Erlang オブジェクトを 1 ワードに納めるのが難しい

現在の実装では Erlang オブジェクトを表すのに列挙型を使っています。この列挙型のメモリサイズを 1 ワード (64ビット=8バイトとする) に収めるのが難しいです。現在の実装では 16 バイトで、 BEAM と比べてメモリサイズとコピーの時間が 2 倍になってしまいます。

列挙型のメモリサイズはヴァリアントのフィールドが使用する最大メモリサイズになります。例えば、いずれかのヴァリアントが含むフィールドのメモリ表現に 16 バイトが必要であれば、すべてのヴァリアントのメモリサイズがそれに合わせられます。さらに、ヴァリアントを表すタグに 1 バイトを取られ、アラインメントが 8 バイトなので、最終的なヴァリアントのメモリサイズは 24 バイトになります。現在の実装では GC の実装をサボって Rc (参照カウント) を多用しているのですが、 Rc は 8 バイトを必要とするので、タグを考えると 16 バイトが必要になります。

仮に Rc を使わずにヴァリアントとオブジェクトを ID で紐付けするとしても、 ID のサイズを u64 にするとやっぱり 16 バイトが必要になります。オブジェクトをどうにか 8 バイトに納めるためには、ヴァリアントを使わずに ID: u64 の生の値のビットを調べてオブジェクトを判別するといった unsafe で面倒な実装が必要です。結局やることが C と変わらない。

スタックマシン vs レジスタマシン

みんな大好きこの話題。レジスタマシンはスタックマシンに比べて命令数が非常に少なく済むので、その分だけスタックマシンより速いと言われます。 BEAM はレジスタマシンです。他の言語だと、 Lua や Dalvik VM がレジスタマシンです。

結論から言うと、スタックマシンで実装しました。実は最初は無限レジスタ数のレジスタマシンで実装したんですが (レジスタの割り当てを気にする必要がないのでコンパイラの実装はシンプルです) 、いざ作ってみるとデバッグが大変でした。操作するレジスタが間違えている場合、バイトコード (正確にはワードコード) を逐次追ってレジスタの中身を確認する作業が辛い。その点スタックマシンなら、使用される値が順序よく積まれているので実行の流れを把握しやすいです。レジスタマシンと比べて命令数が倍以上に増えてしまいますが、どのみち Rust で高速な VM を作るのは難しいとわかったので気にしません。

ネイティブコンパイラの可能性

唯一 BEAM と差をつけられる可能性として、ネイティブコンパイルが考えられます。ネイティブコンパイルというか、 Rust へのトランスパイルですね。 Erlang のソースコードを NIF に変換します (NIF と言っても本家の BEAM と互換性はありません) 。本家の BEAM にも (HiPe を使ったりコンパイラを実装すれば) Erlang のソースコードを C の NIF にコンパイルすることはできますが、 C だと安全性の確保が難しいのが最大の欠点です。落ちないことが BEAM の最大の特徴なのに、 NIF にバグがあるとすべて台無しになります。

一方、 Rust であればメモリ安全な NIF を生成できるはずです。もちろんバイトコードを通さないので高速のはずです。ホットコードローディングも可能だと思います。もしかすると、この一点にのみ Erlang in Rust の意義があるのかもしれません。

Rust で困ったこと、困ること

所有権の静的検査の抜け穴を突く必要がある

VM のような副作用と状態の塊は、所有権との相性が非常に悪いです。 mutable な借用で綺麗に実装できるかと思ってましたが、命令分岐のループ内で参照も同時に使うし、借用も複数箇所で使うので、どうやってもコンパイルに引っかかる箇所があります。ですので静的な検査を諦めて、 RefCell を使った所有権の実行時検査に頼らざるを得ません。当然ながらコンパイル時にメモリ安全を保証できないコードが出てきます。

高速化のためには生の値を操作する必要がある

実行速度の節で触れましたが、 Erlang オブジェクトを列挙型で表すと、メモリ上で表されるオブジェクトが 1 ワードを超えてしまいます (詳しくは「プログラミング Rust 」などを読んでください)。 Erlang 処理系のコンパイルオプションに 32 ビットモードがありますよね。あれが 128 ビットモードになると考えてください。オブジェクトを 1 ワードに収めるには、生の値のビット操作が必要になります。当然ながら unsafe です。型安全などもってのほか。

軽量プロセスの実装をどうするのか

何も考えてません。カーネルレベルで実装されている libdispatch (iOS/macOS の GCD) を使ったら速いんじゃないかと考えていますが、問題が発生したときに追いにくそうです。

C NIf と互換性はない

これは Rust の事情ではないんですが (やろうと思えば C 向けのインターフェースを用意できる) 、 C NIF と互換性を保つには VM を BEAM の完全互換にする必要があります。あまりに大変なのでやる気になれないし、第一 C NIF を組み込んだらメモリ安全ではなくなって Rust を使う意味がなくなってしまいます。ですので、 NIF は全部書き直しになります。

まとめ

Erlang VM に限らず、 Rust で高速な VM を素直に実装するのは難しそうです。なかなか都合よくはいかないようです。