🧶

Quartz v2.0.0のリリース: GCの実装

2023/08/20に公開

コンパイラ

tech

前回の記事の続き。

Quartzはセルフホストを達成した段階でv1.0.0としてリリースし、その後開発を続けてGCが動くところまできたのでキリよくv2.0.0としてリリースした。
v1-v2の間に行った開発について大体順を追って書く。

WASIの導入: v1.1くらい

v1以前は全てをRustのruntimeに頼っていた。
具体的には、Wasmer RuntimeだとFFIとしてRustで定義した関数をWASM側から呼べるので、この機能を利用してFile IOや標準入出力へのアクセスはRust側でラップした関数をWASM側から呼んでいた。

これだと場合によってはかなり非効率になってしまうことなどがあり、一部の関数をWASIに移行した。
具体的にはファイル読み出しや標準出力へのprintあたりをWASIのsyscallを使った実装に切り替えた。

実装に際して、情報がなさすぎて結構苦しみながら実装していたし、いまだに一部の関数は仕様がよくわかっていない。WASIの情報増えて欲しいけど、見ている限りあんまりユーザーがいなさそう(というか、多くのユーザーはWASMを直接書かずに各種ツールを使っているので、積極的にWASIの細かい部分を追うことはなさそう)なので難しいかもしれない。

ちょうどこの作業をやっていた前後でWasmerがWASIXを発表していて、結構タイムリーだった。

LSP関連機能をRustからQuartz側に移植: v1.2-v1.3くらい

コンパイラ自体は元々Rustで書いていたので、「RustでQuartzコンパイラを書く(v0)」から「Quartz v0でQuartzコンパイラを書く(v1)」を達成した時点では、LSPに関する機能、例えばある式についての型表示、定義ジャンプ、フォーマッターなどの機能は全てRustでしか実装していなかった。

するとどうなるかというと、Quartz側に新機能を入れてQuartz v2を作ったとしても、フォーマッターが対応していないのでRust側のv0コンパイラのコードにも手を入れて同様の機能を実装する必要がある。

多くの機能についてRustとQuartzで2回実装する必要があり不毛すぎたので、Rustに残っているランタイム以外の全ての機能をQuartz側に移植した。
基本的にはRustコードを見ながら同じ実装を書くだけだが、一部エラーの表示だったり、ASTにソースコード上の位置を乗せる作業などセルフホスト時にサボった部分を実装する必要があった。

v1.3.7で完全に機能が揃ったため、LSPの実装もRustではなくQuartz側のコンパイラに切り替えてRustのコンパイラのコードを完全に削除した。
当然だがQuartzの方がずっとパフォーマンスが悪いので、LSPの反応はそれなりに悪くなった。

StackとHeapの実装: v1.3くらい

WASMはいわゆる「関数」が言語機能にそもそもあり、さらにローカル変数を自由に好きなだけ利用できるなどの仕組み上、単に関数を書いて実行するだけならスタックの管理などを自前でする必要はない。

また、v1の頃はGCもなかったのでメモリを先頭(低位のアドレス)から雑にallocateしてどんどん高位アドレスに確保していく感じでよく、ヘッダーなどもなくただデータを置くだけでよかった。

v2でGCを入れたいという目論見があったので、この辺りをv1.3前後で整備していた。

具体的には、例えばmark&sweep GCであればスタック上にある値から出発してメモリ上のアドレスをどんどん辿っていく必要がある。
ところがWASMではこのようなスタック上にある値を端から走査するような方法はない。その辺りのruntimeのメモリに手を入れるようなことは覆い隠されていて、ユーザー側では方法が提供されていない。

そうなるとGCが実行できないため、若干効率が悪いが「メモリをallocateするっぽいコードがあるとその値をstackにpushする」みたいな操作を挿入することにした。

例えば

let k = make[vec[i32]](1,2,3,4);

みたいなvectorを宣言するコードがあった時に、それを以下のようにコンパイルすることにした。(疑似コード)

let v = make_vec(4);
push_to_stack(v); // vの値をスタックにpushする
v[0] = 1;
v[1] = 2;
v[2] = 3;
v[3] = 4;

ポインタを確保している時にスタックにpushするだけだが、とりあえずこれでGCに使う値をスタックに乗せることはできた。

よく考えるとこれはWASM側で管理するローカル変数と値がダブっているので無駄なのだが、他にいい方法が思いつかなかったのでこのようにすることにした。
この無駄を嫌って本当にちゃんとやるのであればそもそもWASM側の見えない"スタック"が邪魔なので、関数やローカル変数を使うのをやめた方がいいのだがWASM側でそこまでprimitiveな操作が提供されていないので他に方法はないかなと思った次第。

ついでにヒープ上のオブジェクトにはヘッダーをつけたこと、雑なheap allocatorの実装(フリーリストを使った実装)をやったのもこの辺り。

コンパイラアトリビュートの導入: v1.5

Quartzはセルフホストしているので、例えば今v1のコンパイラが手元にあり、新機能を実装してv2を作りたいとする。
そうすると、Quartzはコンパイラコードの中に標準ライブラリのコードが同梱されていないため、

v2のコード + 標準ライブラリ

↓ v1でコンパイル(このとき標準ライブラリのコードを参照する)

v2のコンパイラ

という図式になる。この時面倒なポイントとして、

v2のコードはv1でコンパイルするので、1つ前のバージョンと互換性を保ったコードを書く必要がある
標準ライブラリを書き換える場合、v2をコンパイルする時にそれが参照されてしまうのでv1コンパイラと互換性を保つ必要がある

特に後者はヘタをするとv2の標準ライブラリで新機能を入れたいがそれにはそれがコンパイルできるコンパイラが必要となってデッドロックしてしまう。

これでうまくいかないことが増えたので、compiler attributeを実装した。
簡単にいうと、

@[build_if(version == "1.0.0")]
fun something() {
  ...
}

のように宣言することで1.0.0のバージョンの時のみこの関数はコンパイルされ、それ以外のバージョンでは無視される。
(今回は、パースphaseと型チェックのphaseの間でattributeを処理する必要があったので、この間にpreprocessor phaseを挟んでそこで行った。どうするのが普通なのかはよくわからない)

これにより互換性に怯えながらコードを書く必要はなくなった。

GCの導入: v2.0

GCはmark&sweepで実装した。

実装は教科書通りで特にハマるというほどハマったことはなかったが、変なコードを書いて変な場所のbitを書き換えたりうっかりオブジェクトを解放するとメモリがめちゃくちゃになるのでデバッグは結構大変だった。

Quartzの場合、ランタイムで出てくる値は64bitが基本となっており、下位32bitが"型タグ"として機能する。下位32bitでその値が数値、アドレス、byte、boolのいずれかとわかるようになっているのでそこの値を見ながら頑張ってデバッグをしていた。
(こういうランタイム時にタグ情報のない言語で、保守的GCを入れるとなった時にうっかり変なバグを仕込んだ時のデバッグの大変さは上述の大変さとは比較にならないだろうなと思いながらデバッグしていた)

コンパイラのコードをコンパイルする際にGCを入れてみて計測したところ、stop the worldは1.75secくらいだった。STWは数秒単位でかかることがあると何かで読んだことがあるが、やはり何も考えずにコードを書くと秒単位でかかってしまうなあと実感した。

最後に、以下のようなコードでGCの動作を実際に検証した。
以下のコードでは、100万行の文字列をnew.outファイルに書き込んでいる。各行は、行のindexを100回繰り返した文字列(例えば、1234行目には"12341234..."と100回繰り返されている)が記録される。

new.outは最終的に600MB程度になるが、GCなしだと58万回程度でOutOfMemoryエラーになっていたが、GCを入れることで100万行の書き込みが成功していることを確認できた。

fun write_to(fd_n: i32, content: string) {
    let ciovec = make[ptr[byte]](8);
    set_ciovec(ciovec, content.data, content.length);

    let ptr_size = make[ptr[i32]](1);
    let err = _fd_write(fd_n, ciovec, ptr_size);
    if err != 0 {
        panic("[file_write] fd_write {}", err.to_string());
    }
}

fun repeat(n: i32, content: string): string {
    let builder = stringbuilder::new();
    for i in 0..n {
        builder.append(content);
    }

    return builder.to_string();
}

fun main() {
    let fd_n = file_open("new.out", 9, 1 << 6);

    for i in 0..1000000 {
        write_to(fd_n, repeat(100, i.to_string()));
        write_to(fd_n, "\n");
    }

    file_close(fd_n);
}

最後に: v2以降

v1をリリース時には、GCを優先してやろうと思っていて実際にGCの実装まで到達できたのでよかったと思う。
v2以降で今やろうと思っているのは、

ジェネリクスの実装(これはそこまで難しくはないが単にサボっているだけ)
Rust Runtimeに残っているFFI関数を頑張って剥がす
LSPが不安定なのをどうにかする
実際にWASMを使ってブラウザで動くものを作ってみる

特に最後のやつは、最近出たRustとWASMのゲーム本(以下)をちょうどこの前買ったので、それのQuartz移植などができたら楽しそうだなと思っている。