Rust のコンパイルが妙に遅くなったので原因を調べた話

# Rust のコンパイルが妙に遅くなったので原因を調べた話

この記事は2021年限界開発鯖アドベントカレンダー 13日目の記事です。

RustでHTTPサーバーアプリケーションを書いていたとき、色々遊んでいるとコンパイルが極端に遅くなる現象が発生しました。その原因を調べるため、rustcのソースコードを読んでみたのでその記録を残しておこうと思います。なにかの参考になれば幸いです。

## TL;DR
- 大きなコードから読みたいところを探すときには`ripgrep`や`hgrep`が早くて便利
- 極端に型引数が複雑な型は、トレイト境界チェックに膨大な時間がかかることがある

この記事の最後のrustcにパッチを当てて検証する過程で気づいたのですが、この膨大な時間がかかる問題が最新のrustcのHEADでは修正されたかもしれません。後述する2分かかる処理が、HEADでは2秒程度で終了するのを確認しました。


## 経緯
（本題に入るまでが長い & 寄り道するので、お急ぎの方は先の段落に飛ばしてください）

`warp`というRustのHTTPサーバー構築ライブラリがあります。warp上でリクエストを処理するコードはこのように書けます。

```rust
use warp::Filter;

#[tokio::main]
async fn main() {
    let route = warp::path!("v1" / "myapi")
        .and(warp::header::optional("Name"))
        .map(|n: Option<String>| format!("Hello {}!", n.as_deref().unwrap_or("名無しさん")))
        .with(warp::trace::request());

    warp::serve(route).bind(([127, 0, 0, 1], 3000)).await
}
```

大体の意味はなんとなくわかっていただけると思います。ここで、`route`変数の型は何でしょうか？幸い、`std::any::type_name`という関数で正確に知ることができます。実行した結果がこちらです。

![](https://imgur.com/St9IsBT.png)

...なんだかとても長い型名が出てきました。これは`warp`がrouteを`warp::Filter`と呼ばれるトレイトを用いて型レベルで表現していることが理由です。標準ライブラリのイテレータがそうしているように、途中のクロージャの型などを型引数として保持するので、最終的にとても長い型名になります。

また話は変わって、`juniper`というGraphQLを扱うライブラリがあります。また、`juniper`は`warp`と連携してGraphQLサーバーを構築することができます。コードはこんな感じです。

```rust
let route = warp::path!("v1" / "myapi")
    .and(juniper_warp::make_graphql_filter(schema, context.boxed()));
```

(`schema`と`context`は今回はあまり重要ではないため省略します。)

ここで私は「なんか複雑なことしてそうだから型名長くなるんだろうなぁ〜」と思い、わくわくしながら型名を調べたところ、以下のようになりました。

![](https://imgur.com/zQi4NuZ.png)

...あれ？なんでこんな短いの？僕の期待してたクソ長型名は？
原因は`warp::filter::boxed::BoxedFilter`にあります。この特殊なFilterは、本来のFilterの型引数をトレイトオブジェクトを使って隠蔽し、型名を短くする効果があります。`juniper_warp`はこの`BoxedFilter`を積極的に使っており、`context.boxed()`と書いたように、引数にも`BoxedFilter`を受け付けるようになっています。これでは型名が長くなりません。

**でも長い型名が見たい！！！！！！** ということで、ライブラリを改造して、`BoxedFilter`となっているところを、`impl Filter`等を使って、型名をそのまま残すように変更しました。その結果がこちら。

![](https://imgur.com/Cm85kIy.png)

うおおお！すっげぇ！長くなった長くなった！と興奮して、その勢いのまま当時開発していた個人的なプロジェクトに突っ込んだところ、非常にコンパイルが遅くなりました。リリースビルドをするのに、パッチを当てる前が3分なのに対し、当てた後は5分もかかるようになりました。

どうして約1.67倍も遅くなるのでしょうか。型名が長くなって文字列操作が遅くなった...とかでは流石にないでしょう。

## 原因を調べる
幸いなことにnightlyのrustcには`self-profile`と呼ばれる機能があり、コンパイルのどの過程に時間がかかっているのか調べることができるようになっています。早速やってみましょう。以下のコマンドを実行します。

```
$ cargo +nightly rustc --release -- -Zself-profile
```

すると、`.mm_profdata`という拡張子を持ったファイルが生成されます。これを加工すると実際に結果が見えるようになります。今回はChromeのデバッガを使って見る方法を使います。以下のコマンドで`crox`コマンドをインストールします。

```
$ cargo install --git https://github.com/rust-lang/measureme --branch stable crox
```

インストールできたら、以下のコマンドでChromeのデバッガが読み込める形式に変換します。

```
$ crox {生成されたファイルへのパス}
```

うまくいけば`chrome_profiler.json`というファイルが生成されます。次に、Chromeのデバッガを開き（どのページで開いても構いません）`Performance`タブを選びます。そして、以下の画像に示す赤丸で囲んだボタンを押して、開かれるダイアログで先程の`chrome_profiler.json`を選択します。

![](https://imgur.com/wBKOBqy.png)

今回の結果はこんな感じになりました。

![](https://imgur.com/cfzhre5.png)

`evaluate_obligation`処理が2分も使っています。これが原因そうですね。これがどのようなことをする処理なのか調べることにします。

（ちなみに、パッチ前のコードに対して同様のことをしたところ、この`evaluate_obligation`は20秒程度で終了していました）

## `evaluate_obligation`処理ってなんだ？

rustcは膨大なコードの上に構築されています。それを全部読んで完全に理解するのには相当な時間がかかるので、今回は関係のあるところだけ掻い摘んで読んでいくことにします。それにおすすめなツールを少しご紹介します。

- [ripgrep](https://github.com/BurntSushi/ripgrep): 検索が早くて見やすい。
- [hgrep](https://github.com/rhysd/hgrep): `ripgrep` + `bat` 早くてより見やすい（が、スペースを使う）
- Vim: ターミナルで動くテキストエディタ。動作が軽快。

とりあえず`evaluate_obligation`で`ripgrep`を走らせてみます。色々ヒットしますが、以下のコードが目に入りました。(クリックでコードへ飛べます）

[`compiler/rustc_middle/src/query/mod.rs`](https://github.com/rust-lang/rust/blob/6bda5b331cfe7e04e1fe348c58a928fc2b650f4f/compiler/rustc_middle/src/query/mod.rs#L1701)

どうやら `evaluate_obligation`は[クエリ](https://rustc-dev-guide.rust-lang.org/query.html)の名前のようです。コメントに「`infcx.predicate_may_hold()`を呼べ」と書いてあるので、この関数の定義を見てみます。`rg "fn predicate_may_hold"`とすると見つかりました。

[`compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs
`](https://github.com/rust-lang/rust/blob/6bda5b331cfe7e04e1fe348c58a928fc2b650f4f/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs#L35)

コメントに、「obligationが満たされるかどうかを評価する」とあるので、この`PredicateObligation`が気になります。`rg "(struct|enum|type) PredicateObligation"` とすると見つかりました。

[`compiler/rustc_infer/src/traits/mod.rs`](https://github.com/rust-lang/rust/blob/6bda5b331cfe7e04e1fe348c58a928fc2b650f4f/compiler/rustc_infer/src/traits/mod.rs#L55)

どうやら欲しい物が見つかったようです。コメントに、「`Obligation`は`i32: Eq`に対する`impl Eq for i32`のような、実装を見つけなければならないトレイトの参照を表します。実装を探す作業のことを`Obligation`を"resolve"すると呼びます。」と書かれています。

これで原因がわかりました。複雑すぎる型のせいでトレイト境界を満たしているのかの確認に大きな時間がかかっていたのです。この検証のあと、コンパイラにパッチを当てて具体的にどのトレイト境界の解決に時間がかかっていたのか確認したところ、とてつもなく型引数が肥大化した型が`std::future::Future`を実装しているかのチェックに2分近くを要していたようです。

## まとめ

型引数がとてつもなく複雑になることが予想され、かつそこまで速度が問題にならない場所では積極的にトレイトオブジェクトを使って型を単純化し、コンパイル速度を上げたほうがいいかもしれません。

`juniper_warp`がしていた`BoxedFilter`に包んで型を単純にする戦略は正しいと思います。