「LLVM lld」「mold」が解決した、リンクが遅い問題　間違った思い込みの解消に必要だったのは“クレイジーな人”

1個の本質的な問題を解いてしまうほうが細かいことを考えるよりも簡単

植山類氏：では始めます。本日、機会をいただいて講演をすることになった植山と申します。この講演の内容は「大きな問題のほうが小さな問題より解くのは簡単だ」というタイトルです。

どういう趣旨かというと、常に簡単だというわけではないのですが、いろいろな場面で、1個の本質的な問題をドッカンと解いてしまうほうが、いろいろな細かいことを考えるよりも簡単なことが多いという話です。

そういうソリューションが往々にして見逃されがちということがけっこうあって、そういうことにどうやって挑戦していくのかという気持ちの話を、僕がそういう大きな問題を解決した経験を踏まえて話をしていきたいと思います。

「LLVM lld」と「mold」が解決した問題

僕が何を作ったかというと、リンカと言われるプログラムです。「LLVM lld」というリンカと、「mold」という2つのリンカを作りました。

リンカが何なのかを説明したほうがいいと思うのですが、リンカというのは、CやC++やRustみたいな、コンパイルする言語のプログラムで必要なプログラムで、プログラムをビルドする時に使われるものです。

CやC++やRustといった種類の言語では、まずソースコードがコンパイラによってオブジェクトファイルといわれるファイルに変換されます。オブジェクトファイルは拡張子が.oのファイルで、ビルドしたあと、makeなどを走らせた後のディレクトリにたくさん.oというファイルができているのを見たことがある人も多いと思います。

オブジェクトファイルには、ソースコードをコンパイルした結果が入っているわけです。そこにはマシンコードや、例えば文字列みたいなデータがそのまま入っているわけです。ただ、オブジェクトファイルは単体では実行可能なプログラムではありません。

というのも、コンパイラは一つひとつこのソースファイルをコンパイルしているわけで、1個のソースファイルにすべてのプログラムのコードが書かれているわけではありません。なので必然的にコンパイラの出力であるオブジェクトファイルは、ソース一つひとつに対応したプログラムの断片しか入っていないわけです。だから、それ単体では実行可能じゃないんですよね。

なので、誰かがオブジェクトファイルを全部1個のファイルにがっちゃんこして、それで実行できるような形式にしてやらないといけないわけですよね。それをするのがリンカといわれるプログラムです。

なので、コンパイルするタイプの言語でプログラムを書いている限りは、意識しているかしていないかに関わらず、リンカは必ずビルドの最終ステップに走っていて、リンカによって実行ファイルなりシェアードオブジェクトファイルなりが作られることになります。

僕がmoldやlldのリンカを書いてどういう問題を解決したかというと、そのプログラムのビルド、リンクが遅い問題を解決しました。これは長らく問題になっていたのですが、解決しちゃったんですよね。

エンジニアリングというものはトレードオフであって、いろいろな要素を鑑みた上でベストな方法を選んで、いろいろな日常のエンジニアリングをしていくわけなんです。だけど往々にして小さな問題を解くことにフォーカスをしてしまって、大きな本質的な問題を解くんじゃなくて、それを回避するとか、ワークアラウンドを実装するとか、そういうことに走りがちな傾向にあります。

ど真ん中で正面から突破するみたいなことは往々にして避けられがちです。必要以上に避けられがちだと思うんですよね。なので、大きな問題を解決していこうよというのが、この講演の趣旨です。

lldやmoldが解決した問題というのは、リンクによるビルドの遅さでした。どういうことかというと、リンカはそもそもプログラムのビルドのボトルネックになりがちなんですよね。コンパイラだったら、ソースファイルの数だけプロセスを同時に立ち上げられます。そうすればCPUのコアの個数分だけは並列性があって、同時にコンパイルを進めることができるわけなんです。

ただ、リンクの最後のステップで複数のファイルを全部1個に合わせるところは、複数のプロセスで分けて分割できるような仕事ではありません。なのでその部分はシリアルにやるしかなくて、そうするとリンクそのものが遅いと、そのままの時間がかかっちゃうんですよね。

これは、ソースツリーがフレッシュな状態、クリーンな状態でビルドをするんだったらそんなには目立たちません。というのは、その時にはそもそもコンパイルが遅いので、最後のリンクが時間かかってもそれほど気にはなりません。

ただ現実的には、ソースファイルをちょこっと変更をして、ビルドして、動作を見てみて、デバッグして、またソースをちょっと変更して、ビルドしてとやっています。

いわゆる普通の開発をしていると、ソースのビルドの遅さはすごく気になってきます。コンパイラが1回だけ走って、1プロセスだけ走ってリンクが走ることになるので、リンクの遅さがすごく目立つんですね。そして、リンクの遅さは作業効率の遅さに直結するわけです。

どれぐらい直結するかというと、現代のプログラムはかなり大きいので、例えばプログラムをビルドした結果、デバッグ情報を含めると、実行ファイルが1GBを超えるものも珍しくはないんですね。そういうプログラムは、かつてはリンクするのに何十秒とか、何分とか、あるいは何十分もかかることが普通にあったんですよ。猛烈に遅いわけですよね。

30秒かかる場合でも、30秒黙って端末の前で待っていられないので、タスクをスイッチしちゃいますよね。そうすると、そこで集中力が切れてしまうわけなんですよ。場合によっては「X」を見始めるとか、Webサーフィンを始めるとかで何をやっているか忘れちゃう。30秒遅いというのは、単に30秒失うわけじゃなくてフローを失うことになるので、すごく悪い状態なんですよね。

問題が解決される前にもいろいろなアイデアが試されていた

これは問題なので、リンクを速くするためのアイデアをみんながいろいろ考えてきました。僕が自作リンカを作る前、いろいろと話を聞いていました。

僕が聞いた1つのアイデアでは、こんなものがありました。コンパイラとリンカの両方に手を入れて、コンパイラがオブジェクトファイルというかたちでマシンコードをファイルに出力するのではなくて、関数単位とかでコードをコンパイルして、データベースにしまって、データベースからリンカがコードを呼んできて出力するというアイデアを聞いたこともあります。

あるいは、2回目以降のリンクでは前回に作成した実行ファイルに、ある意味バイナリパッチを充てるようにして、前回の入力から変更された部分だけを前回の出力にアプライして、リンクの時間を短縮するようなアイデアもありました。

実際にそのアイデアが実装されたことがあって、「インクリメンタルリンク」と呼ばれています。インクリメンタルリンクを実装しているリンカは、実際にいくつもあります。

インクリメンタルリンクは良いアイデアに聞こえますが、実際には実装がすごく複雑になるし、その複雑さによってその機能そのものに実行時間のコストがかかるので、よりリンクの時間が延びたりして、良さそうに思えるけど、実際にはリンク時間を短縮することはあまりできなかったんですよね。

それ以外にもいろいろなリンクの最適化の高速化のアイデアはあったのですが、僕が見る限り、どのアイデアも根本的な理解としては「リンクは時間のかかる処理だ」ということが前提になっていたと思うんですよ。その前提は果たして本当に正しかったんでしょうか。リンクというのはそもそもそんなに重いんですか。本当にそうなんですか？

僕が書いたリンカは既存のものに比べてすごく速くて、インクリメンタルリンクもしていません。僕が考えていたのは、「インクリメンタルリンク自体が複雑だから、インクリメンタルリンクをしたいと思うこともなくなるぐらい速いものを単に作ってしまえばいいんじゃないのか」ということだったんですね。僕の書いたリンカはすごく速くて、1GBの実行ファイルでも手元のマシンだと1秒ぐらいで作れます。

僕の手元のマシンで1GBのファイルをcpコマンドでコピーすると0.5秒ぐらいかかるんですよね。ファイルをコピーするのと比べて、単純に2倍ぐらいの時間しかかからないので、ものすごく速いんですよね。

プログラミングの歴史の中で「リンクが遅い」というのは何十年も存在していた問題だったわけですが、これによってほとんど実質的に解決済みの問題になってしまったわけなんですよ。

足りなかったのは“クレイジーな人”

不思議な話ですが、実際にイチから作り直してみれば、「リンクが重い処理だということ自体が、なんとなくその業界で共有はされていたけれど間違いだった」と。間違った思い込みだったというわけなんです。

なぜこういうことが可能だったか。僕がスーパープログラマーだったから効率的な物が作れたのかというと、僕としては「そうだ」と言いたいところですが、実際には別にそういうわけではないと思います。

ある程度以上の技術力はいるのですが、僕より前にそういうことをやろうとした人がどのぐらいいたのかというと、ほとんどいなかったんですよね。なので何が足りなかったかというと、単に「イチから書き直してみよう」というクレイジーな人が足りなかっただけで、やってみればかなり多くの人ができることだったということは、たぶん間違いないと思うんですよ。

ずっと業界全体として悩まされていて、ただ、リンクというのはそもそも時間がかかるからと、なんとなく見過ごされていたわけです。本当のところは、20年ぐらい前に誰かが解決するべきだったのではないかというと、そうだったんだと思います。単に挑戦者がいなかっただけの話だと思うんですよ。

今ではlldやmoldも広く使われています。lldはGoogleで僕が仕事としてやっていたプロジェクトです。僕はアメリカのGoogleのC++コンパイラチームにいて、そこで仕事をしていました。Googleで仕事の一環としてlldを作っていました。Googleを辞めて、そのあとmoldを作りました。さらに速いリンカを目指した時、mold（を作った時）なんかは、単なる個人プロジェクトに過ぎないわけです。

ですが、moldも世の中に広く認知されています。例えばGCCコンパイラでも、-fuse-ld=moldを渡すとmoldが使えるみたいな、moldを使うための専用のオプションがあったりします。

なので、僕の自作リンカのためのオプションがGCCに特別に追加されているという、考えてみればなかなかすごい状態ですが、やったらできちゃったりするわけなんですよね。

僕の始めた競争が業界全体の改善に

他の人がやっているのを見ると自分もできるような気がしてくるというのは、大きな会社においても同じで、むしろ大きな会社のほうがやりやすいと思うんですよね。

というのも、マネージャーを説得して新しいプロジェクトをぶち上げようという時に、「他の人がすでにできているんだから、うちの会社も当然できるはず」と言うと、プロジェクトが立ち上げやすいわけです。何の実績もなくうまくいくかわからないものを立ち上げるよりは、はるかに簡単なわけです。

なので、僕がlldとmoldを書いたことによって、スピード競争が始まって、ある意味AppleやMicrosoftは恥ずかしい状態になってしまったわけなんです。MicrosoftやAppleの開発環境のリンクのステップが妙に遅いというのは、本当はそんなにかかるべきじゃないのにかかっているという状態になってしまったわけなんですよね。

なので、Appleはそれに対して実際にプロジェクトを立ち上げて、2023年のWWDCではAppleがイチから書き直したリンカが発表されて、この間出たXcodeにはそれが含まれています。なので、僕が始めたスピード競争が、Appleまで到達しているわけなんです。このプロジェクトをAppleサイドでやっていたのはDavide Italianoという人で、僕の友だちです。

ただ、さすがにAppleでやっている未発表のプロジェクトについて教えてくれるわけはないので、彼がやっているのは知らなかったのですが、まぁ狭い世界なわけです。

なので、このセッションを聞いている人の中に、Appleプラットフォームに向けてソフトウェアを書いている人はけっこうたくさんいると思うんですよね。macOSやiOS向けのアプリケーションを書いている人は、Xcodeのリンカを使っているわけです。

Xcodeの新しいバージョンからリンクが速くなっているので、プログラムによってはビルドが気づくぐらい速くなると思うんですよ。それは僕の始めた競争の結果なので、ある意味「業界全体が改善されて良かったね」という話になると思います。

（次回に続く）