Google製GNU gold以上の速さを実現　超高速リンカ「mold」を支えるテクニック

リンカが速いと何がうれしいのか

植山類氏（以下、植山）：リンカが速くなって何がうれしいのか。普通にうれしいです。プログラムを書いているとうれしいことがわかると思いますが、makeを実行すると、普通は自分が直前に変更したファイルしかビルドしないので、デバッグをしていると1つのファイルを編集してビルドすることになります。

コンパイラは1つだけのファイルをコンパイルするのはそこそこ速いですが、リンカは基本的には実行ファイルを丸ごと作ります。全体の入力を一気に受け取って出力するため、差分コンパイルであってもリンカの仕事はそんなに変わりません。遅くなりがちなリンカが速いのはうれしいです。

moldがどれくらい速いか。（スライドを指して）このチャートですが、GNU ldというのは大昔のものです。それを足すとグラフが長くなりすぎて他のものがわからない。たぶん1分などではなく1時間かかるので省きます。GNU goldと、LLVM lldは僕がオリジナルで作ったものなのですが、それと僕が2020年から作っているmoldの比較です。実行ファイルはデバッグ情報付きですが巨大で、2GBや1.6GBあります。こういうものをビルドしている人はgoldを使っていないと思うので、例えばChromeだとビルド時間が10秒かかりますが、moldだと2秒です。Firefoxでもやはり6秒と1.5秒くらいの差がついています。

これがどのくらい速いかというと、2GBのファイルをcpで別のファイルにコピーすると1秒くらいかかるので、単にcpの2倍遅いだけなんです。いろいろなことをやっているけれど結局、データを入力ファイルから出力ファイルにコピーして、それを約2倍の時間でやっているので、かなり速いといえます。

速さには、いくつか理由があります。1つは、lldもそうですが中間表現を作らずmmapしたファイルの内容を可能な限りそのまま使っているからです。（スライドを指して）ある意味においてはベタベタなコーディングに見えますが、簡単にシンプルに書くとこうなります。

moldを速くするポイント

ここがポイントですが、可能な限りすべての内部パスを並列化しています。これは非常に重要で、lldでもできるだけやろうと思ったものの並列化されていない部分がたくさんあって、並列化されていないパスがボトルネックになるんです。

例えば1つのプログラムで半分のパスの並列化が可能だとすると、無限にコアがあったとしても結局残り半分が時間を使うので、50パーセントしか時間を削れません。でも9割の並列化が可能であれば10パーセントまで切る可能性があります。これを「アムダールの法則」といいますが、マルチコアのマシンで性能を稼ごうと思った時、シングルスレッドで走っている場所はボトルネックになりがちなので、なるべくパラでいくのが基本的な方針です。

（スライドを指して）これがビジュアル的に一番わかりやすい説明だと思います。htopというトップの表示ですが、コアごとに示しています。基本的にlldでは1つのCPUばかり使っていて、パッパッとなっているところが並列化されているパスなんです。その部分は一瞬で終わりますが、結局別のところでボトルネックになる。右がmoldですが、moldを実行すると最初からフルパワーで走ってそのままで終わるという感じです。つまり、ほとんどが並列化されているのがわかると思います。全体が終了するのも速いです。

データ並列と並列コンテナ

扱うデータのスケールは、けっこう大きいです。Chromeをデバッグ情報付きでビルドして、リンカでどれくらいの入力を受け取るかというと、例えばどこの部分をどこのアドレスで修正しないといけないかというリロケーションは3,500万個くらいあります。シンボルは変数の名前ですが、2,000万個とすごく多いです。入力ファイルだけでも数万個あって、数万回繰り返すくらいなら普通のシングルスレッドのループで問題ありませんが、数千万回になるとけっこう時間を使うので並列化をやりたくなってきます。

moldでは小賢しい並列化はやっていません。データ並列というテクニックを使っています。どういうものかというと、同じタイプのデータがたくさんあって、それを一つひとつ処理しています。例えば画像処理だと典型的ですが、画像処理で例えばアルファ合成するようなものだと独立して1ピクセルごとに計算できます。それと似たような感じで、シンボル名がたくさんあるので別々にやっています。実際にはIntel TBBというライブラリを使っています。並列forループのようなものがあるので、それを使って複数のイテレーションを、同時に走るかもしれないforループみたいなもので並列しています。複雑な同期メカニズムやメッセージングメカニズムを使ってマルチスレッドプログラミングをすると面倒くさいのですが、並列forループだと、単に複数のイテレーションが同時に走るかもしれないforループなので非常にわかりやすいです。

それ以外に、性能を稼ぐためにmoldで使っているのは、並列コンテナです。concurrent_hash_mapを使っています。普通のハッシュマップは複数のスレッドから同時に要素を挿入すると壊れたりするのでロックを取らないといけません。しかし、ロックを取ると当然ながらシリアライズされて性能が出ません。コンカレントなハッシュテーブルは中が巧妙な作りになっていて、複数のスレッドから挿入しても壊れないうえに、2スレッドから同時に挿入してもほぼ2倍の性能が出ています。実際にリニアには性能は伸びませんが、わりといい感じで出ているコンテナもあるので、moldではIntel TBBのconcurrent_hash_mapを使っています。

これを使うと何がうれしいのか。一例はmoldにおけるシンボル解決です。シンボル解決は結局名前の突き合わせなので、こっちのファイルはprintfが必要としている、こっちのファイルではprintfを定義している、みたいなことを突き合わせるということなので、その名前を全部ハッシュテーブルに入れて、それに対応するシンボルオブジェクトを見つけます。並列forループで、オブジェクトファイルごとに、一気に全部のシンボルをconcurrent_hash_mapに挿入しています。そうするとシンボル解決が並行でできるようになっています。

その他のパターン

それ以外のパターンは、メジャーなものですが、Map-reduceパターンのようなものを使っています。例えば、リンカに-build-idというオプションを渡すと出力されたハッシュ値を計算してファイルに埋め込んでくれるんですが、2GBの出力ファイルだとボトルネックになってきます。なぜかというと、2GBのファイルのハッシュ値を計算するにはどんなに速くてもそれなりに時間がかかるからです。しかし、これを10MBの単位に仮想的に分割して、10MBのチャンクごとにSHAを計算して、SHAのハッシュ値のハッシュ値取ると並行で計算できるようになります。これを暗号では「マークルツリー」とい言いますが、高さが2のマークルツリーを計算することで性能を稼ぐことができます。

（スライドを指して）今はmoldでは使っていませんが、トリッキーなケースとして並列化できなそうでできるパターンもあります。リンカではよくある操作ですが、大量の文字列をシリアライズしてファイルに出力します。ここはFoo、Bar、Quux、Bazという文字列があって右側のように出力したいのですが、最初の文字列はオフセット0だとして、その長さが4なので次の文字列のオフセットは4、次の文字列のオフセットは8になります。それぞれ前から順番に見ていかないとオフセットが決められなさそうです。つまり並列には同時にコピーできなそうですが、実はできます。一見複雑そうですがわりと簡単で、矢印の方向に足し算をしていくと正しい結果が出てきます。

（スライドを指して）例えば3つ目を見ると15ですが、5＋4＋6を足すと15なので、足し算した結果になるんです。中間結果をまとめて計算しておいて、中間結果と中間結果を足すと自分の結果になる足し算です。最初の文字列長の計算が同時にできるし、2段目も2つをまとめているだけなので同時にできます。全体の計算量は若干増えますが、速くなります。これをparallel scanパターンと言いますが、このようなトリッキーなものもあるので、並行プログラミングはけっこうおもしろいです。

その他の高速化テクニック

ほかにも細かい高速化のテクニックをいくつか使っています。例えばデフォルトのmallocはスレッド数が多くなってくるとスケールしないので、今はマイクロソフトのmimallocを使っています。jemallocやtbbmallocなど、いろいろなマルチスレッドでパフォーマンスが出るものがありますが、mimallocが一番よかったのでこれを使っています。

また、これは若干コントラバーシャルですが、既存のファイルに書き込んだほうが速いんです。新しいファイルを作って書き込むよりも、すでにバッファキャッシュに載っているファイルを上書きしたほうが速いので、すでに出力ファイルが存在している場合はそれを上書きしています。それにより数百ミリ秒くらい速くなります。

それから、たくさんのファイルをmmapしたりメモリをたくさん使っているプロセスは、exitが遅くて、exitだけで何百ミリ秒かかったりするので、プロセスを2つに分割しています。親は単に子を作り、その子が出力ファイルを出力したらそれを親に通知し、それで親が即座にexitするようになっています。そうすれば、子はexitに時間がかかってもユーザーには見えないのでよし！というテクニックを使っています。

速いプログラムを書くためのポイント

（スライドを指して）こちらが最後のスライドで、速いプログラムを書くコツです。まず「こうすると速くなるんじゃないか」というアイデアはたくさんあると思いますが、推測せずに計測するのが基本です。それから凝ったコードを書くのではなく自然と速くなるようなデータ構造を考えて作る。コードでプログラムを速くすることはできません。データを工夫するほうが速くなるのでデータ構造を考えましょう。また、基本的には、手が速いほうが速いプログラムが書けます。つまり、たくさん実装して一番速いものを選ぶ。結局作ってみないとわからないので、作って計測して一番速いものを選ぶ必要があります。

身も蓋もない話ですが、プログラムを書き直さないとうまくできないこともよくあります。何回も同じものを書くと1回目で学んだことは2回目に使えるので、速いプログラムや良いプログラムを書くことができます。完全に二度手間というわけではなく、明らかに上達しているのでちょいちょいと書けます。例えば、moldもChromeにリンクができるところまで2ヶ月くらいでした。最初は1年以上かかったと思いますが、実際に書き直すのはそれほど手間ではありません。発表は以上です。

質疑応答

司会者：「header-onlyライブラリばかり使っていると共有ライブラリの仕組みに乗っかれないから苦しそう」というコメントがあって、おもしろいと思いました。

植山：テンプレートのコンパイルはすごく遅くなるので良し悪しです。ただ、仮に何もライブラリを使っていなくても普通はlibc++を使っているので、完全にブートローダーから起動するプログラムを作っているのでなければ何かしらリンクされているんです。デフォルトのライブラリがリンクされているのでリンカは動いています。

司会者：「昔あった差分リンクは筋としてどうなんだろう」というコメントが来ています。

植山：なかなか良いポイントです。差分リンクはREADMEに細かく書きましたが、僕はあまり良いアイデアだとは思っていません。そもそも差分リンクはgoldも実装していますが遅くて、差分リンクでChromeをビルド、GNU goldでリンクすると何も並行していなくても30秒くらいかかるんです。なので差分リンク自体もうまく実装しないと遅い。普通にリンクしたほうが速いこともある。

あるいはウィークシンボルなど少しトリッキーな機能を使っていると、1つの関数を置き換えるだけではなくカスケーディングな影響がたくさんあるので、ローカルな変更を書くとしても、その変更がバイナリレベルでローカルに収まるという保証はまったくありません。

トリッキーで難しいので、僕の基本的なスタンスとしては差分リンク機能をすごくがんばって作るよりは、普通のリンクをメチャクチャ速くすればモチベーション自体がなくなるので、あまり難しく考えずに、素直なケースを速くしましょうというのが僕の基本的な考え方です。

司会者：もう1つ「moldではリンク時最適化を実装する予定はありますか？」という質問が来ています。「普通のリンカはそういうことをやっていますか」というコメントもあります。

植山：やります。lldやGNU ldでもリンク時最適化があります。LLVMのlldではすごく簡単にリンク時最適化に使うことができて、clangのオプションとlldのオプションに-fltoを付けるとリンク時最適化が行われることになっています。LLVMのビットコードをオブジェクトファイルに出力するようになるんです。そうすると、基本的には中間言語なので中間言語をまとめてリンカを受け取ることになって、リンカがまとめてコンパイルします。

そうすると一つひとつのプログラムの断片からはわかりえないこと、例えばこちらの関数とこちらの関数はインライン化したほうがよさそうだということがモジュールを超えてできるので、プログラム全体の最適化ができるようになります。

しかし、これはナチュラルに遅い。それはなぜか。プログラム全体を本当に受け取ってコンパイルしないといけないからです。moldでもできますがナチュラルに遅くなるので、他のリンカとの差別化要因にはなりえない。もともとリンク時最適化では何十分もかかったりするので、何十分40秒が何十分20秒になるくらいの差しか出ないと思います。最終的には実装するかもしれませんが、今すぐやるつもりはありません。

司会者：他との差別化の意識がおもしろいですね。最後に1つ「moldはx86用ですか？　CPUアーキに依存した実装ですか？」という質問があります。

植山：moldは今のところx86-64専用で書いています。Linuxの実行ファイルを出力したい時は、たぶんLinuxでしかビルドはできないと思います。もしかしたら他のOSでもできるかもしれませんが、特に今のところは考えていません。

別の実装に移植もできると思いますが、最初から移植性を考えてプログラムを書くと難しくなるので、とりあえずLinux前提でベタベタで書いて、移植する価値のあるプログラムになったら改めて考えればよかろうというスタンスです。ただ、移植はできます。ちょっと考えてはいますが、とりあえずx86-64のLinuxにフォーカスして開発しています。

司会者：ありがとうございます。質問は以上です。