Ninja

Ninja は Make に似たビルドシステムである。ユーザーは入力として、ソース (例えば C++ のソースコード) をターゲット (例えばライブラリファイルや実行可能ファイル) に変換するためのコマンドを記述する。Ninja は記述されたコマンドを使って、ターゲットを最新の状態に更新する。他の多くのビルドシステムと異なり、Ninja はパフォーマンスを主要な設計目標としている。

私は Google Chrome に取り組んでいるときに Ninja を開発した。Ninja は Chrome のビルドを高速化できないかを探るための実験として始まったのである。実際に Chrome のビルドで使えなければならないので、Ninja にはスピードの他にもう一つ主要な設計目標があった: Ninja は他の大規模なビルドシステムに簡単に組み込めなければならない。

Ninja は大きな成功を収めており、Chrome で利用される他のビルドシステムを少しずつ置き換えている。Ninja がパブリックに公開されてからは、人々がコントリビュートしたコードによって、有名なビルドシステム CMake が Ninja 用の構成ファイルを生成できるようになった ── 現在では LLVM や ReactOS といった CMake を利用するプロジェクトの開発でも Ninja は利用されている。TextMate のように、独自のビルドプロセスで Ninja を直接利用するプロジェクトもある。

私は 2007 年から 2012 年にかけて Chrome に取り組み、Ninja の開発は 2010 年に始まった。Chrome ほどに巨大な (執筆時点において 40,000 個の C++ ソースファイルが約 90 MB のバイナリを生成する) プロジェクトのビルドパフォーマンスには様々な要因が影響する。複数マシンを利用した分散ビルドからリンク時のトリックまで、様々なビルド高速化手法を私はこれまで扱ってきた。Ninja が高速化の対象とするのはビルドプロセスの一要素 ── ビルドのフロント ── だけである。ここで「フロント」はビルドを開始してから最初のコンパイルが実行されるまでの待機時間を指す。この時間を短くするのがなぜ重要かを理解するには、Chrome 自体のパフォーマンスに関して開発チームが考えていることを最初に理解する必要がある。

Chrome の簡単な歴史

Chrome の目標を一つ残らず議論したいわけではない。Chrome の決定的な目標の一つにパフォーマンスがある。「パフォーマンス」はコンピューターサイエンスの全ての分野が関わる広範な目標であり、Chrome はキャッシュ化から並列化、just-in-time コンパイルまで利用可能なトリックをほぼ全て使っている。そして、パフォーマンスの一要素としてスタートアップ時間 ── アイコンをクリックしてから Chrome のウィンドウが現れるまでの時間 ── がある。これは他の要素に比べると取るに足らないものに思えるかもしれない。

どうしてスタートアップ時間など気にかけるのだろうか？ ブラウザのスタートアップ時間が短ければ、ウェブブラウザを開くことがテキストファイルを開くのと同じくらいに「軽い」という印象をユーザーに与えることができる。さらに、プログラムのレイテンシが長いとユーザーの幸福感が下がり、思考の流れが断ち切られてしまうことは HCI (human-computer interaction) の分野で詳しく研究されている。レイテンシは Google や Amazon といったウェブ企業によって特に重要視される。ウェブ企業はレイテンシの影響を計測・実験するのに適した場所であり、実地での実験からはミリ秒単位の遅延でさえサイトの利用率や商品購入率に影響することが判明している。レイテンシは無意識に積み重なるストレスと言える。

スタートアップ時間を短縮するために、Chrome は開発の最初期にエンジニアたちが実装した賢いトリックを使っている。開発が進んでスケルトンアプリケーションのウィンドウを画面に表示できるようになった時点で、開発チームはスタートアップ時間を計測するベンチマークを作成し、継続的ビルドでその結果を追跡した。そして、Brett Wilson の言葉を借りるなら「このテストは絶対に遅くなってはいけない¹」という「非常に簡単なルール」が定められた。Chrome にコードが追加されるにつれて、このベンチマークのメンテナンスに多くのエンジニアリングコストがかかるようになっていった² ── 機能の追加が本当に必要となるまで先送りになったり、スタートアップで利用されるデータが事前計算されたりするケースもあった。ただ、パフォーマンス改善の第一歩として使われる重要な (そして私が最も感銘を受けた) トリックは「する仕事を減らす」だった。

私はビルドツールを作るつもりで Chrome 開発チームに参加したわけでは決してない。私は Linux の専門知識を持っていて、好きなプラットフォームも Linux だったので、チームでは「Linux の人」になりたいと思っていた。しかし初期の Chrome は作業を減らすために Windows だけに集中していた。そこで私は、Linux への移植を始めるために Windows 実装を手伝って早く完了させることが自分の仕事だと考えるようにした。

今までとは違うプラットフォームで開発を始めるとき、最初のハードルはビルドシステムの整備である。当時の Chrome は既に巨大だった (完全ではあった: Windows 用 Chrome のリリースは 2008 年であり、このとき移植は始まっていない)。そのため、Windows で使われる Visual Studio ベースのビルドシステムを別のシステムに切り替えることさえ、継続して行われる開発との衝突は避けられなかった。中に人が残っている状態で建物の基礎を取り換えるようなものだった。

Chrome チームは段階的な解決法として、GYP (Generate Your Projects) と呼ばれるプログラムを作成した。GYP を実行すると、サブコンポーネントごとに、当時 Chrome が利用していた Visual Studio 用ビルドファイルに加えて他のプラットフォームで使用できるビルドファイルが生成される。

GYP への入力は単純である: 期待される出力の名前と、プレーンテキストで並んだソースファイルのリスト、「各 IDL ファイルから追加のソースファイルを生成する」といったカスタムルール、そして条件付き振る舞い (「特定のプラットフォームでは特定のファイルを使う」など) からなる。この高レベルな記述を受け取った GYP はプラットフォーム固有のビルドファイルを生成する³。

Mac において「プラットフォーム固有のビルドファイル」と言えば Xcode のプロジェクトファイルを指す。しかし Linux では、「プラットフォーム固有のビルドファイル」が一つに定まらない。Scons というビルドシステムが最初に試されたものの、GYP が生成する Scons ビルドファイルを Scons に読み込ませると、処理が必要なファイルの計算に 30 秒もかかることが判明したので選択肢からは外れた。その後、私は Chrome が Linux カーネルとほぼ同規模なことに気が付き、Linux カーネルで使われているアプローチなら上手く動作するのではないかと考えた。私は袖をまくり、Linux カーネルと同じ手法で GYP からプレーンの Makefile ビルドファイルを生成するコードを書いた。

こうして私はビルドシステムの迷宮に意図せず迷い込んだ。ソフトウェアのビルドに時間がかかる原因には「リンクが遅い」から「並列化できていない」までいくつも考えられるので、私はそれらを一つずつ調べていった。Makefile を使うアプローチは始めのころは高速だったものの、Chrome の Linux 移植が進んでビルドされるファイルが増えるにつれて遅くなっていった⁴。

Linux 移植を進める中で、私はビルドプロセスの一要素に特に不快感を覚えるようになった: 一つのファイルを編集して、make を実行する。するとセミコロンが足りなくてエラーになる。そこでセミコロンを一つ付け足して make を再度実行する。このシナリオで、make の実行時間が何をしていたかを忘れてしまうほどに長いのである。私は Chrome 開発チームがエンドユーザーの体感するレイテンシを削減するために大変な努力をしていることを思い出し、「なぜ Makefile はこんなに遅いのだろうか。たいした仕事があるわけでもないのに」と考えた。Makefile の処理をどれだけ単純に行えるかを調べるための実験として、Ninja の開発が始まった。

Ninja の設計

高いレベルで言うと、ビルドシステムの仕事は三つステップからなる:

1. ビルドファイルを読み込み、解析する。
2. ターゲットを生成するために実行すべきコマンドを計算する。
3. そのコマンドを実行する。

ステップ 1 を高速化するには、ビルドファイルを読み込むときに行う仕事を最小限にする必要がある。一方でビルドシステムは人間によって使われることが多いので、ビルドシステムはビルドターゲットを表現する高レベルで使いやすい構文を提供しなければならない。また、一部の処理はプロジェクトを実際にビルドするときに実行される: 例えば、ある時点で Visual Studio はビルド構成から出力ファイルの配置場所を具体的に計算し、C コンパイラと C++ コンパイラのどちらを使うかをファイルごとに決定しなければならない。

このため、GYP が Visual Studio 用ビルドファイルの生成で行うのはソースファイルのリストを Visual Studio の構文に変換する処理だけであり、それ以降の様々な処理は Visual Studio に任せられる。Ninja を開発するとき、私は可能な限り多くの処理を GYP に押し付けるようにした。ある意味で、GYP は Ninja ビルドファイルを生成するときに上述した実行すべきコマンドの計算を一度だけ行い、そのスナップショットの中間表現を Ninja が素早く読み込めるフォーマットで保存していると言える。

そのため Ninja のビルドファイル用の言語は単純であり、人間には書きにくいと言っても過言ではない。例えば、ファイル拡張子に応じた条件や規則を書くことはできない。具体的に言えば、Ninja のビルドファイルは完全なパスで書かれた特定の出力を得るための完全なコマンドが並んだリストである。このフォーマットで書かれたファイルは高速に読み込むことができ、解釈がほとんど必要とならない。

このミニマリストな設計によって、意外にも Ninja の柔軟性は増す。Ninja は「出力ディレクトリ」や「現在の構成」といったビルドプロセスの高レベルな概念に関する知識を持たないので、Ninja はビルドの整頓方法に関して異なる意見を持つ様々な大規模ビルドシステム (例えば CMake と GYP) のそれぞれに簡単に組み入れることができる。例えば、Ninja はビルド結果 (例えばオブジェクトファイル) がソースファイルと同じディレクトリに配置される (これを「汚い」と考える人がいる) か、それとも個別のディレクトリに配置される (これを「分かりにくい」と考える人がいる) かを区別しない。Ninja をリリースして長い時間が経った後、私はピッタリな比喩を思い付いた: 他のビルドシステムがコンパイラだとすれば、Ninja はアセンブラである。

Ninja は何をするか

Ninja がビルドファイルを生成するプログラムに多くの仕事を押し付けているのだとすれば、Ninja の仕事としては何が残るだろうか？ 上述したアイデアは理論上は素晴らしいものの、現実の世界は必ず理論より複雑である。Ninja の開発が進む中で、いくつかの機能が追加 (そして削除) されてきた。そのたびに問われてきた重要な質問は「もっと仕事を減らせないか？」だった。これから Ninja の持つ機能を概観する。

ビルド規則が間違っていた場合は人間がファイルを読んでデバッグする必要がある。そのため Ninja のビルドファイルは Makefile と同じようにプレーンテキストで書かれ、可読性を上げるためにいくつかの抽象化をサポートする必要がある。

最初の抽象化としてルール (rule) がある。ルールはコマンドラインから特定のツールを起動する方法を示した記述であり、異なるビルドステップで共有される。例えば、次の例では GCC コンパイラを起動する「compile」という名前のルールが定義され、そのルールを使って C ソースコードをコンパイルする build 文が二つ示されている:

rule compile
  command = gcc -Wall -c $in -o $out
build out/foo.o: compile src/foo.c
build out/bar.o: compile src/bar.c

二つ目の抽象化として変数 (variable) がある。上の例でドル記号が前に付いた識別子 $in, $out が変数の例である。変数はコマンドの入力と出力を取得したり、長い文字列に短い名前を付けたりするために利用できる。コンパイラに渡すフラグを変数 cflags に格納して compile ルールを定義する例を次に示す:

cflags = -Wall
rule compile
  command = gcc $cflags -c $in -o $out

ルール内で参照される変数には、build ブロック内で新しい定義を与えることができる。build ブロックは build 文の次の行をインデントすることで作成できる。上の例で使った cflags を特定のファイルに対して調整する例を次に示す:

build out/file_with_extra_flags.o: compile src/baz.c
  cflags = -Wall -Wextra

ルールは関数とほぼ同じであり、変数は引数と同じように振る舞う。この二つの単純な機能は危険なほどプログラミング言語に似ている ── 「する仕事を減らす」の目標に逆行している。しかしルールと変数があれば文字列の反復が減ってパースすべき文字列が短くなるので、人間だけではなくコンピューターにとっても利点がある。

ビルドファイルのパースが完了すると、依存関係を表すグラフが手に入る: 最終的に出力されるバイナリファイルはいくつかのオブジェクトファイルに依存し、それぞれのオブジェクトファイルはソースコードに依存する。細かく言うと、このグラフはファイルを頂点、ビルドコマンドを辺とした二部グラフである⁵。ビルドプロセスではこのグラフが走査される。

ビルドすべきターゲットの出力ファイルが与えられると、Ninja はビルドファイルを読み込んで構築したグラフを走査し、出力ファイルに接続する辺の反対側にある入力ファイルの状態を (必要なら再帰的に) 確認する: つまり、入力ファイルの有無と、もし存在するならその最終更新時刻を確認する。その後 Ninja はプラン (plan) を計算する。プランは最終的なターゲットを更新するために実行が必要な辺の集合であり、中間ファイルの最終更新時刻から計算される。最後にプランは実行され、Ninja はグラフをターゲットに向かって登りながら各コマンドが正しく実行を完了することを確認していく。

この部分の処理を実装し終わったとき、私は Chrome を使って今後の基準となるベンチマークを作成した: ビルドが成功した直後に Ninja を再度実行したときの実行時間である。これはビルドファイルを読み込み、ビルド結果とソースツリーの状態を確認し、行うべき仕事が無いことを確認するまでの時間に対応する。このベンチマークの実行結果は 1 秒以下であり、この値がスタートアップベンチマークの新しい指標となった。Chrome の規模は増加を続けたので、この指標がリグレッションを起こすのを避けるには Ninja を高速化し続ける必要があった。

Ninja の最適化

Ninja の最初の実装では高速なビルドが行えるように注意深く工夫されたデータ構造が使われたのに対して、コードの最適化に関しては特に賢いことをしていなかった。一度プログラムが正しく動くようになれば、プロファイラが遅い部分を明らかにしてくれるだろうと私は考えていた⁶。

長年にわたる開発の中で、プロファイル結果はプログラムの様々な部分を指摘してきた。パフォーマンスに対する影響が大きい単一の関数が明らかな場合もあれば、「不必要なメモリのアロケートとコピーを避けた方がいい」のようなぼんやりとしたことしか分からない場合もある。また、データの表現あるいはデータ構造の改善が最も大きな影響を持つ場合もある。ここからは Ninja の実装を概観しつつ、パフォーマンスに関連する興味深いストーリーを紹介する。

パース

最初 Ninja は手書きの字句解析器と再帰下降パーサーを使っていた。構文は十分に単純だから問題ないだろう、と私は考えた。しかし Chrome⁷ のような十分に巨大なプロジェクトでは、ビルドファイル (拡張子 .ninja を持つファイル) のパースだけでも驚くほど長い時間がかかることが後に判明した。

ビルドの規模が大きくなると、単一の文字を解析する次の関数がプロファイラの示すホットスポットの上位に現れるようになった:

static bool IsIdentifierCharacter(char c) {
  return
    ('a' <= c && c <= 'z') ||
    ('A' <= c && c <= 'Z') ||
    // ....
}

当時 200 ms が節約された単純な解決法は、関数を 256 要素のルックアップテーブル (入力文字が添え字となる) で置き換えることだった。このルックアップテーブルは次のような Python コードで簡単に生成できる:

cs = set()
for c in string.ascii_letters + string.digits + r'+,-./\_$':
    cs.add(ord(c))
for i in range(256):
    print '%d,' % (i in cs),

このトリックによって、かなり長い間 Ninja は高速に保たれた。その後、もっときちんとしたものが使われるようになった: PHP が利用している字句解析器生成器 re2c である。re2c は複雑なルックアップテーブルや人間には理解不能なコードを生成できる。例えば、次のようなコードが生成される:

if (yych <= 'b') {
    if (yych == '`') goto yy24;
    if (yych <= 'a') goto yy21;
    // ....
}

「そもそも入力がテキストなのは良いアイデアなのか？」という疑問に対する答えを私は持ち合わせていない。パースがほとんど必要とならない、機械が理解しやすいフォーマットで Ninja に対する入力を生成することを他のツールに要求するときはいずれ来ると思われる。

正規化

Ninja はパスの特定に文字列を使うことを避ける。そうする代わりに、Ninja は自身がビルドファイルから読み込んだパスを Node オブジェクトにマップし、ビルドファイルの読み込み以外のコードでは Node オブジェクトを利用する。このオブジェクトを使い回すことで、特定のファイルの情報をディスクまで確認に行く処理が確実に一度だけ行われることが保証され、その確認で得られた情報 (例えば最新更新時刻) を他のコードから再利用できるようになる。

Node オブジェクトを指すポインタは、その Node オブジェクトが表すパスの一意識別子として機能する。つまり、二つの Node オブジェクトが同じパスを表しているかどうかはポインタの比較だけで判定できる (コストの高い文字列比較は必要とならない)。例えば Ninja がビルドに依存するファイルを表すグラフを走査するとき、依存関係ループを検出するために依存ファイルに対応する Node がスタックに保存される: もし A が B に依存し、B が C に依存し、C が A に依存するなら、ビルドは実行できない。ファイルのリストを表すこのスタックは単なるポインタの配列として実装でき、重複要素はポインタの比較を使って検出できる。

同じファイルに対する Node を必ず一つとするために、Ninja は同じファイルを表す異なる文字列を全て単一の Node オブジェクトに対応付ける。この処理のために、正規化 (canonicalization) がビルドファイルに含まれる全てのパスに必要となる。正規化は例えば foo/../bar.h を bar.h に変換する。最初 Ninja は全てのパスが正規化された状態で提供されることを要求したものの、この要件はいくつかの理由で撤廃された。まず、ユーザーが手書きしたパス (コマンドラインから ninja ./bar.h と起動したときの ./bar.h など) は正しく認識できることが期待される。次に、変数を組み合わせた結果として正規でないパスが生成される場合がある。最後に、GCC が出力する依存ファイルの情報に正規でないパスが含まれる場合がある。

このため、現在の Ninja が行う処理の多くはパスに関する処理であり、プロファイラが示すホットスポットにはパスの正規化処理が現れる。最初の実装はパフォーマンスではなく明快さを優先させていたので、標準的な最適化手法 ── 二重ループやメモリアロケートの回避 ── によってパフォーマンスが大きく改善された。

ビルドログ

上述したような細部の最適化は、アルゴリズムやアプローチを変更する構造的な最適化と比べると影響が小さい傾向にある。Ninja のビルドログに関する処理では構造的な最適化が大きな成果を上げた。

Linux カーネルのビルドシステムには、出力を生成するコマンドを記録する機能がある。例えば、入力 foo.c をコンパイルすると出力 foo.o が生成される状況で、ビルドファイルが変更されて foo.c をコンパイルするコマンドが変わったとする。このときビルドシステムは foo.o を再生成しなければならないことを察知し、新しいコマンドで foo.c コンパイルを行う必要がある。以上の処理を行う方法には少なくとも二つの選択肢が考えられる:

1. foo.o および全ての出力は無条件にビルドファイルに依存すると定める (このとき、プロジェクトの構成によってはビルドファイルを変更するたびにプロジェクト全体の再ビルドが起こる)。
2. 出力を生成するコマンドを出力ごとに記録し、ビルドのたびに変化したかどうかを確認する。

Linux カーネル (そして後の Chrome で使われる Makefile や Ninja) は後者のアプローチを採用する。Ninja は出力を生成するのに使われた完全なコマンドを出力ごとに記録したビルドログをビルドのたびに保存する⁸。以降のビルドで Ninja は前回のビルドログを読み込み、そこにあるビルドコマンドを新しいビルドコマンドと比較して変更を検出する。このため、ビルドファイルの読み込みやパスの正規化と同じように、ビルドログに関連する処理もプロファイルが示すホットスポットの一つとなる。

小規模な最適化がいくつか行われた後、多産な Ninja コントリビューター Nico Weber がビルドログ用の新しいフォーマットを実装した。コマンドは非常に長いことが多く、その場合パースに時間がかかるので、新しいフォーマットではコマンドではなくコマンドのハッシュがビルドログに記録されるようになった。ビルドログが保存されているとき、Ninja は今から実行しようとしているコマンドのハッシュとビルドログに保存されたコマンドのハッシュを比較する。もし二つのハッシュが同じならコマンドの実行は必要なく、異なるなら (ファイルが変化していなくても) コマンドを実行しなければならない。このアプローチは素晴らしい成功を収めた。ハッシュの利用によってビルドログのサイズが大きく削減された ── Mac OS X では 200 MB から 2 MB 以下になった ── ことで、ビルドログの読み込みは 20 倍以上高速化した。

依存ファイル

ビルドに何らかのメタデータの記録・利用が必要な場合がある。例えば C/C++ コードベースを正しくビルドするには、ビルドシステムがヘッダーファイル間の依存関係を理解しなければならない: foo.c に #include "bar.h" という行が含まれ、bar.h に #include "baz.h" という行が含まれるとき、三つのファイル (foo.c, bar.h, baz.h) 全てがコンパイルに関係する。そのため baz.h が変更されたときは foo.o の再ビルドが必要になる。

ビルド時に入力ファイルから依存関係を抽出する「ヘッダースキャナー」を持つビルドシステムもある。しかし、このアプローチは低速であり、#ifdef ディレクティブが存在するために正しく動作させるのが難しい。もう一つの選択肢として「ビルドファイルにヘッダーを含む全ての依存ファイルを正確に記述することを要求する」があるものの、このアプローチだと開発者の負担が大きい: #include ディレクティブを追加/削除するたびにビルドファイルの改変または再生成が必要になる。

これらより優れたアプローチは、GCC (そして Microsoft の Visual Studio) がビルドで利用したヘッダーファイルを出力できる事実を利用する。この情報は出力を生成するコマンドと同様に記録され、ビルドシステムによる依存関係の正確な追跡が可能となる。初回のビルドでは全てのファイルがコンパイルされるので、ヘッダーの依存関係に関する情報は必要とならない。二回目以降のビルドでは、初回のビルドで抽出された情報があるおかげで任意のファイルに対する変更が正しいファイルの再ビルドを起動するようになる。再ビルド時には依存ヘッダーの追加/削除も検出され、依存関係も更新される。

コンパイルを行うとき、GCC はヘッダーの依存関係を Makefile が読めるフォーマットでファイルに書き出す。Ninja には Makefile の構文 (の単純化された部分集合) を読めるパーサーが備わっており、GCC の出力から依存関係の情報を完全に読み込むことができる。しかし、この読み込み処理は Ninja の主要なボトルネックの一つである。最近の Chrome ビルドでは、GCC が出力する Makefile フォーマットの出力は合計で 90 MB に達する。この出力には、使う前に正規化が必要なパスも多く含まれる。

ビルドファイルのパース時と同様に、可能な限りコピーを避け、さらに re2c を使うことで GCC が書き出す Makefile を読み込む処理のパフォーマンスは改善した。しかし、GYP に可能な限り仕事を押し付けたのと同じように、この処理もスタートアップのクリティカルパスから排除できる。ヘッダーの依存関係をビルド中に読み込むようにする改善が現在 Ninja 開発者によって進められている (この改善は執筆時点で完成しているものの、まだリリースはされていない)。

ビルドコマンドの実行を開始した時点でパフォーマンスクリティカルな仕事は全て完了し、Ninja は実行したコマンドの終了を待つだけとなる。新しいアプローチでは、Ninja はコマンドの終了待ちの間に GCC によって生成される Makefile ファイルを処理する: ファイルを読み込み、パスを正規化し、素早くデシリアライズ可能なバイナリフォーマットに依存関係を変換する。次回のビルドでは、このバイナリファイルを読むだけで済む。このアプローチによってパフォーマンスは劇的に改善される。特に (後述する理由により) Windows で改善は大きい。

バイナリの「依存ログ」には数千個のパスとそれらの間の依存関係を格納する必要がある。また、このログの読み込みと編集は高速に行えなければならず、ビルドのキャンセルなどによって Ninja の実行が中断されたときに壊れてもいけない。

私はデータベース風のアプローチを数多く試した後、最終的にとても簡単な実装にたどり着いた: ログが格納されるファイルはレコードが並んだバイナリファイルであり、各レコードは「パス」または「依存関係のリスト」を表す。パスには識別子として連番の整数が割り振られ、依存関係は整数列として表される。このファイルに新しく依存関係を追加するとき、Ninja は識別子を持たないパスを表すレコードを最初に書き込み、それから依存関係を (新しく割り当てた識別子を使って) 表すレコードを書き込む。以降の実行で Ninja がファイルを読み込むときは、識別子を Node 型の値へのポインタに対応付ける単純な配列を利用できる。

ビルドの実行

パフォーマンスの観点からすると、これまでに解説してきた依存関係の解析から必要と判明した外部コマンドを実行する部分には興味深い部分が比較的少ない。実際の仕事は大部分が Ninja ではない外部コマンド (コンパイラやリンカ) によって行われるためである⁹。

デフォルトで Ninja はシステムで利用可能な CPU コア数に基づいてビルドコマンドを並列に実行する。同時に実行されるコマンドからの出力が干渉する可能性があるので、Ninja はコマンドが終了するまで出力をバッファし、コマンドが終了してから一度に出力する。このため、ユーザーはコマンドを逐次的に実行したかのような出力を目にする¹⁰。

こうして各コマンドの出力を制御することで、Ninja は自身の出力を完全に制御できる。ビルドの実行中 Ninja は進捗を表す一行のステータスバーを表示し、ビルドが成功するとき Ninja の出力は一行だけとなる¹¹。こうしたところで Ninja の実行は速くならないものの、ユーザーが体感する速度は向上する。Ninja にとって体感速度は実際の速度と同程度に重要である。

Windows のサポート

私は Ninja を Linux 用プログラムとして書き、後に Nico (先述) が Mac OSX への移植を行った。Ninja が広く使われるようになると、Windows のサポートを望む声が聞かれるようになった。

表面的に見る限り、Windows のサポートは難しくない。パスの分離文字をバックスラッシュに変えたり、コロンを含むパス (c:\foo.txt) を許したりといった簡単な変更が最初に行われた。この実装が終わると、根深い問題が現れた。Ninja はシステムの Linux 的な振る舞いを仮定して書かれており、Windows は小さいものの重要な部分が異なっていたのである。

例えば、Windows ではコマンドの長さに比較的短い制限が付いているので、プロジェクトに含まれるほとんどのファイルを参照する最後のリンクステップで問題が発生する可能性がある。この問題に対しては Windows が「レスポンスファイル」を使った解決策を用意しており、幸い Ninja だけを変更すれば対応が可能だった (Ninja のビルドファイルを生成する前段のプログラムに変更は必要なかった)。

これより重要なパフォーマンスの問題として、Windows ではファイル操作が遅く、Ninja は大量のファイルを処理するという問題があった。Linux でさえボトルネックだった大量のファイルに対する処理は、ファイルオープンのコストが非常に高い Windows で大きく悪化する。

Visual Studio のコンパイラ (cl) はヘッダーの依存関係をコンパイル中にそのまま出力するので、現在 Windows の Ninja は cl をラップして出力を読み取り、Ninja が要求する GCC と同じ Makefile スタイルのフォーマットに変換する機能を持つ。先述した「ビルド時に依存関係をパースする」新しいアプローチは Windows で特に効果を発揮し、この中間ツールを削除できる: Ninja はコマンドの出力をバッファしているので、そのバッファから依存関係を直接読み取れる。GCC のようにディスク上に保存される中間ファイルは利用されない。

最終更新時刻を取得する処理 ── Windows では GetFileAttributesEx¹² 関数、Windows 以外では stat 関数 ── の実行時間を比較すると、Windows は Linux の 100 倍近く遅い¹³。これがアンチウイルスソフトといった「不公平な」要因による可能性はあるものの、そういった要因は実際のエンドユーザーのシステムに存在するので、Ninja のパフォーマンスが低下する事実からは逃れられない。Ninja と同様に多くのファイルの状態を取得する必要があるバージョン管理システム Git では、ファイル状態の取得を複数のスレッドを使って並列に行うことができる。この機能は Ninja にも存在するべきである。

他の設計

「Ninja をメモリ上に常駐するデーモン (サーバー) として動作するようにしてはどうか」という提案がメーリングリストに寄せられることがある。そうすれば、ファイルの変更を監視する機能 (Linux では inotify) を活用できる。さらに、ビルドを終えた後も Ninja が起動されたままなので、内部で使われるデータをファイルとして読み書きする時間が節約される。

実は、これは私が最初に考えた Ninja の設計だった。しかし Ninja の最初のバージョンを作ったとき、私はサーバーの機能を持たせずとも Ninja を十分高速にできるのではないかと感じた。Chrome が成長を続ければいずれサーバーの機能が必要になるかもしれないと思いはしたが、少ない仕事をする単純なアプローチは複雑な機構より魅力的に思えた。これまでに行った「字句解析機生成器の利用」や「Windows での新しい依存関係フォーマットの利用」のような構造的な最適化をしていけば今後も十分な高速化ができるだろう、と私は考えている。

結論

ソフトウェアにおいて単純さは善である。問題は常に「どこまで単純にできるか」にある。Ninja は時間のかかる仕事を他のビルドツール (GYP や CMake) に押し付けることで複雑性を排除し、さらにそのおかげで元々の対象プロジェクト (Chrome) 以外でも使えるようになっている。Ninja の単純なコードはコントリビューションを促したはずだと私は思う ── Mac OS X, Windows, CMake のサポートをはじめとした機能は大部分が私ではないコントリビューターによって実装された。他の言語 (私の知る限り Scheme と Go) で Ninja を再実装する実験が行われているのも Ninja の単純な意味論のおかげだと私は考えている。

ミリ秒など本当に重要なのだろうか？ ソフトウェアが持つ他の重大な懸念事項と比べれば、ほんの少しの高速化に頭を悩ませるのは馬鹿げているように思えるかもしれない。しかし、高速化によって生産性以上のものが手に入ることに私は気が付いた: ビルドのターンアラウンドが短いとプロジェクトが「軽く」感じられるようになり、コードをいじるのが楽しくなる。そして楽しくハックできるコードというのは、私がソフトウェアを書くそもそもの理由である。この意味で、ビルドの速度は非常に大きな重要性を持つ。

謝辞

Ninja の多くのコントリビューターに感謝する。その一部は GitHub のプロジェクトページから確認できる。