Crystalのコンパイルがなぜ遅いかについてのメモ

## はじめに

Crystal言語はコンパイルがとても遅いことで有名です。
ところで、Crystalのコンパイルで最も時間がかかっている場所はどこだと思いますか？

```mermaid
flowchart LR
style id1 fill:#fcf,stroke:#333,stroke-width:1px
    subgraph Lexer
      Token
    end
    subgraph Parser
      AST
    end
    subgraph コンパイラ
      Lexer
      Parser
      Token
      AST
      id1{Semantic}
      LLVM
    end
    subgraph LLVM
      LLVM_IR
      LLVM_IR --> アセンブリ
    end
    テキストファイル --> Token
    Token --> AST
    AST --> id1{Semantic?}
    id1{Semantic?} --> LLVM_IR
    アセンブリ --> 実行ファイル
``` 

## Crystalでコンパイル時間の統計を見る

いつでも役に立つわけではないのですが、Crystalでは、コンパイル時間についての統計をだしてくれるコマンドラインオプションがついています。

```
crystal build -s hoge.cr
```

しかし、今回はこれでは不十分です。
あえて問題の本質を考えるために[Printデバッグ](https://gist.github.com/kojix2/bf758a30ded3ea9aff9d3151df6a59c1)を利用して、コンパイル時間を調べてみましょう。

## Crystalのコンパイラ

Crystalのコンパイラで最も重要なコードは次のとおりです。

```cr
module Crystal
  class Compiler
    def compile(source : Source | Array(Source), output_filename : String) : Result
      source = [source] unless source.is_a?(Array)
      # 1 new_program
      program = new_program(source)

      # 2 parse
      node = parse program, source

      # 3 semantic
      node = program.semantic node, cleanup: !no_cleanup?

      # 4 codegen
      units = codegen program, node, source, output_filename unless @no_codegen

      # 5 cleanup
      # ... omission ...
      Result.new program, node
    end
  end
end
```

さらに、codegenの中で

- `LibLLVM.run_passes`
- `LibLLVM.target_machine_emit_to_file`

が呼び出されます。これについても実行時間を計測しましょう。
そのうえで、Crystalのコンパイラをコンパイルした結果は以下 [^1] のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144608/936f1825-7e57-dbd3-d2d8-be5aea008e9b.png)

これは、ほとんどの部分が

- `LibLLVM.run_passes`
- `LibLLVM.target_machine_emit_to_file`

により時間を費やしているということを意味します。`LibLLVM.run_passes` は実際には単純にコードの最適化、すなわちC言語のコンパイルオプションの `-O3` のようなことをしています。これは主に `--release` フラグを有効にした場合に発火します。つまり、実はコンパイル時間の大半はCrystalではなくLLVMが最適化したり、LLVM-IRから実行ファイルを作成している時間になるのです。少し意外な結果だったのではないでしょうか？

## なぜCrystal言語で、インクリメンタルコンパイルや、共有ライブラリの作成が成功していないのか

ここから先は、かなり主観が入り、また私のコンピュータやITに関する造形は必ずしも深いとは言えないので、誤っている部分があるかもしれませんので、話半分に聞いてください。

Crystal言語は、常に一つのモジュールで構成された、絵巻物のように長い一枚のLLVM-IRを出力します。これがCrystalのコンパイルが遅い理由の一つです。Rustなどの他のLLVMを用いる言語が分割コンパイルを行うのに対して、Crystalはライブラリを使う場合であっても決してLLVM-IRを分割してくれないので、並列コンパイルを行うことができないのです。

ではなぜCrystalは複数のLLVM-IRモジュールに分割して出力できないのでしょうか？

その理由は、Rubyの影響を受けたCrystal言語は型がとても柔軟であるため、型を決定するためには常にコード全体が必要になるからです。Crystalのコードはそれ自体では型が決定できません。静的言語であるにも関わらずダックタイピングを可能にするCrystal言語では、呼び出し元が型を決定します。だから、ライブラリとしているパッケージだけ事前にコンパイルしてあとから使うことはできないのです。（当然条件によってはできる場合もあるでしょう）

Crystalは型を解決するために、すべてのクラスに番号を割り当てます。コンパイルのたびにコード中に存在する全ての型に、おそらくアルファベット順に番号が割り当てられてられます。あるプロジェクトでは作成したLLVM-IRまたはオブジェクトでAというクラスに1という数字が割り当てられていても、別のプロジェクトではLLVM-IRまたはオブジェクトで１が別のクラスに割り当てられてしまいます。だから、普通にリンクしても型の不整合が起きて普通に失敗します。型に応じて正しい条件分岐が行われないからです。

## Crystal言語とは何なのか？

Crystalは非常に小さな開発チームでありながらも、Rubyのような簡潔な文法で、大手の開発する言語に匹敵する素晴らしいパフォーマンスを発揮する言語として知られています。しかし、このことを考えると、Crystalとは何者なのかがわかってくるような気がします。

たとえば、AppleがCrystalを開発するなら、事前にしっかりとABIを定義して、Crystal言語に適応した中間言語を作成するかもしれません。そうすることによって、LLVM-IRに翻訳する前に、まずは中間言語に翻訳し、中間言語の段階でモジュール同士を突き合わせることで、型の解決をはかり、それからLLVM-IRに変換するような言語を作成するかもしれません。（妄想の話をしているので、そういうことが可能かどうかはわかりません）

しかし、Crystal言語はそうではありません。ひたすら一枚岩の長大なLLVM-IRを吐き出します。そして全ての最適化をLLVMに委ねるのです。そう考えると、コンパイルが遅く、実行速度が早いというCrystalの特性は、むしろCrystalの開発チームの、個人的・少数精鋭的な考え方から発生しているということが見えてきませんか？それは、必ずしもCrystal言語そのものの特性ではないのかも知れません。大企業がCrystalを開発したら、もっと速度を犠牲にして互換性を重視していたでしょうし、Crystal以外の静的言語も、逐次的に長い絵巻物のようなLLVM-IRを出力させて、長時間をかけてそれを最適化させることでC言語に次ぐパフォーマンスを叩き出すという戦略を取ることはできたはずです。

個人的にはCrystal言語がWebプログラミングで活躍するために生まれた言語だとはどうしても思えないのです。それは単にRubyの愛好家の一部がCrystalに移住してきたために伝統的にWebアプリ開発者が多いというだけであって、この言語が本当に活躍するべき場所は別にあるのではないかという気がします。

Crystal言語では、ガベージコレクションもlibgc-devに依存しています。ほかにも特にファイルやIOの処理において libevent-dev にも依存しています。このように依存できるところは外部のライブラリに依存するという考え方なので、組み込みの分野では使いにくいと考えられます。もっともこれも、言語そのものと言うよりは、少数精鋭という環境から生まれた特性で、大企業が開発しているならば単にGCをCrystal言語で再実装してしまい、あまり問題になっていないかもしれません。

CrystalのためのABIや中間言語を設計する！というのは私には無理な話なので、もう少し簡単そうなところを趣味的に調べたいと思っています。出力されたLLVM-IRをなんとかして複数のモジュールに分割できないだろうかとか、関数やグローバル変数をマングリングするなどです。

この記事はややメモ的な考察を含むのであまりまとまりません。

以上です。

[^1]:

| Stage                          | Time (seconds)         |
|--------------------------------|------------------------|
| new_program                    | 0.000388207            |
| parse                          | 0.000065000            |
| semantic                       | 12.552620028           |
| codegen                        | 355.245409133          |
| - LibLLVM.run_passes           | 252.340241198          |
| - LibLLVM.target_machine_emit_to_file | 93.280652845   |
| cleanup                        | 0.000013180            |
| total                          | 367.798495548          |