Ninja(2020)の成功と失敗

 (neugierig.org)
2 ポイント 投稿者 GN⁺ 2024-11-30 | 1件のコメント | WhatsAppで共有
  • 2011年に公開された Ninja は、Makeに似たビルドシステムとして始まり、Chrome、Androidの一部、Meson、CMakeベースのプロジェクトにまで広がった代表的なオープンソース成功例となった
  • 成否を分けた軸はコードそのものよりも アーキテクチャ、さらに言えば保守やユーザーの期待といった 社会的な問題 だった
  • Ninjaは ninja.build に書かれたコマンド・入力・出力を読み、ファイルの更新時刻を確認したうえで必要な作業を並列実行し、大規模プロジェクトの インクリメンタルビルド を高速にすることに集中している
  • 最大の設計上の選択は、高水準のビルド機能を自前で抱え込まず アクショングラフ(action graph) の実行器にとどまった点であり、複雑な判断はジェネレーター(generator)に任せるよう分離したことだった
  • CMake統合、Windows対応、並列実行のデフォルト設定は普及を後押しした一方で、設計目標と衝突する要求や貢献はオープンソース保守の大きな負担として残った

Ninjaが広く使われるようになった文脈

  • Ninjaは約9年前に公開されたMakeに似たビルドシステムで、当初は気恥ずかしさを感じながら共有したサイドプロジェクトだったが、その後広く使われるようになった
  • 主な利用例は次のとおり
    • Chromeは最終的に Ninja以外のビルド をすべて削除した
    • Androidはシステムの大きな構成要素の一部でNinjaを使用している
    • Meson プロジェクトはNinjaを使用しており、フリーソフトウェアの世界でますます多く使われるビルドシステムに見える
    • CMakeと一緒にNinjaを使うプロジェクトも多く、Swiftのビルド案内でもNinjaのインストールが求められる
  • Ninjaは2011年にリリースされ、2014年にプロジェクトの所有権が移り、その後さらに3人目のメンテナーへと引き継がれた
  • この回顧で明らかになる中心的な経験は、コードより アーキテクチャ、アーキテクチャより 社会的な問題 のほうが大きな影響を持つという点である

高速ビルドのための基本動作

  • Ninjaのやることは比較的単純である
    • ユーザーは ninja.build ファイルに実行するコマンド、各コマンドが消費するファイル、生成するファイルを書く
    • Ninjaはこのファイルを読み、複数のファイルの 更新時刻 を確認する
    • 最新状態を作るために必要なコマンドを並列実行する
  • Makeと比べると入力用ビルド言語の機能は少なく、その少ない機能を非常に高速に実行する構造に集中している
  • 実行の流れは3段階に分かれる
    • ビルドファイルのパースと解釈
    • 入力ファイルの更新時刻の確認
    • 必要なコマンドの実行
  • 目標は、10万個を超える入力ファイルがある大規模プロジェクトでも、できるだけ早く3段階目に到達することである
  • 最適化の例として、Ninjaは入力ファイルのパスをできるだけ早い段階で一意なメモリオブジェクトにマッピングし、その後のパス同一性比較にはポインタ比較を使う
  • より低レベルな性能の詳細は The Performance of Open Source SoftwareのNinja章 で扱われている
  • 長年にわたりNinjaの再実装も登場した
    • llbuild と Shake はNinjaファイルの入力をサポートしている
    • samurai はほぼファイル単位で再実装したプロジェクトで、コードは少ないが機能も少なく、テストもない
  • 面白い20%の実装は簡単でも、残りの80%には細部が多く、より高速な実装は知られていない

設計で重要だった選択

  • グラフ表現

    • Makeは1つのビルドルールが複数のファイルを生成する場合をうまく扱えない
    • Ninjaはファイル間グラフではなく ファイルとコマンドの二部グラフ を使う
    • ファイルノードはコマンドノードへ入る辺となり、コマンドノードは再び出力ファイルへ向かう辺を持つ
    • この構造はビルドの実際の形をよりよく捉える
    • 入力の1つが変わるとコマンドは古い状態になり、コマンドが実行されるとすべての出力が更新される
    • 特定のファイルは最大1本の入力辺しか持てない
    • コマンドライン自体もコマンドノードの入力と見なせるため、コマンドラインフラグが変わればコマンドと出力は古い状態になる

  • deps logとCヘッダー依存関係

    • Cヘッダー依存関係を正確に処理するには、Cコンパイラが生成した追加の依存関係データを消費する必要がある
    • データベース導入の是非と単純さのあいだで悩んだ末に、deps log表現形式 を作った
    • この形式はかなりコンパクトだが、重要な点でいまだに間違っている部分がある

  • end-to-end / crash-only設計

    • Ninjaは常駐するデーモンプロセスではなく、実行のたびに最初から処理する
    • この選択は end-to-end principle と crash-only software の影響を受けた構造である
    • 最初から実行する経路を高速にすれば、別の「オンライン」コード経路を作る必要がない
    • メモリ常駐できるプロジェクトは、結局起動性能が放置される傾向がある

  • ファイル状態の確認

    • ビルドツールがメモリ常駐すべきだと期待される理由の1つは、ディスク上のファイル状態をキャッシュするためである
    • 実際にはカーネルがすでにこの情報をメモリにキャッシュしており、ユーザー空間で再度キャッシュしても節約は大きくない
    • Linuxでファイル状態を取得する処理は非常に高速で、Ninjaはこれを単一スレッドで処理する
    • 10年前基準の「高速な」マシンでも、3万個のファイルに対する stat を数十ミリ秒で実行できる

  • 規模と仕様のトレードオフ

    • 経験則として、2倍規模への拡張は最適化で可能だが、10倍規模への拡張には再アーキテクチャが必要になる
    • Ninjaは当時およそ3万個のビルドステップがあったChromeのビルドを中心に設計された
    • 今ではより小さな環境でも使われているが、その場合は速度上の利点が必要でないこともある
    • Androidビルドのようなさらに大きい環境ではスケール限界に突き当たっており、別のアプローチが必要になる可能性がある
    • Ninjaは並列実行のためにユーザーが十分な情報を与えることを必要とするが、ビルド全体を完全に把握していなければならないとは強制しない
    • 正確さ、利便性、性能のあいだにはトレードオフがあり、より正確でも不便なツールより、利便性のために正確さを一部犠牲にしたツールのほうが、エコシステム全体ではより正しい結果をもたらすこともある

「アセンブラ」という比喩が生んだ分離

  • ビルドシステムは多様な高水準機能を提供し、ツールごとに自らを説明する方法も互いに比較しにくいほど幅広い
  • Ninjaの中核的な洞察は、どのような高水準機能を提供しようとも、ビルドシステムは最終的にファイルを最新状態に保つための アクショングラフ を構成しなければならないという点だった
  • Ninjaはこのアクショングラフだけを実行し、その上にどのようなジェネレーターを置くかはユーザーに任せる
  • この2つのプログラムの分離は、もともとChromeプロジェクトにうまく合うよう作られた構造だったが、その後Ninjaの最も重要な貢献となった
  • 利点は2つある
    • Ninja自体を単純かつ高速に保てる
    • *.c をglobするような高コストな処理をジェネレーター側へ押し出せる
  • 他のビルドシステムが一度にすべてを処理するのと違い、Ninjaの構造は計算済みのアクショングラフをディスク上にスナップショットとして保存することになる
  • 結果として、ビルド間でアクショングラフをキャッシュする形になる
  • ジェネレーターは望むだけ高水準になれる
    • たとえばソースツリー全体をglobして、名前に test を含むファイルをテストとして見つけることも可能である
  • 開発者は何にコストを払うかを自分で決めなければならない
    • ジェネレーターがディスク全体をglobすることも可能だが、そのビルドがなぜ遅いのかもより明確になる
  • ジェネレーターとアクショングラフの分離は実際には単純ではなく、Ninjaにもどの層が何を担当するかをめぐる細かな論点が多い
  • XcodeやVisual Studioのビルドシステムも理論上は同じように事前計算して結果をスナップショットできるはずだが、層を混ぜたくなる誘惑のためうまくいっていないと見ている
  • Makeはglobbing、変数展開、substring、関数といったプログラマー向け機能をすべて含めようとし、必要な機能を完全に表現するには弱いが、遅いMakefileを書くには十分強い言語になった
  • Ninjaはこうした方向を避けようとした

デフォルト値が体感性能を支配する

  • Ninjaはデフォルトで望ましいコマンドを 並列実行 する
  • Makeも -j フラグで並列実行できるが、デフォルトは直列実行である
  • Makefileは依存関係を十分に明示していないため、並列実行が安全でない状態で書かれやすい
  • Ninjaは単一コアのシステムでも常に並列実行するため、この種の誤りをより早く露呈させる
  • Ninjaにうまく合うプログラムは通常、並列ビルドでも安全になる
  • Ninjaが誤った依存関係を検出する高度な仕組みを持つわけではなく、誤ったビルドがより頻繁に起きることで問題が表面化する構造である
  • Makeの並列実行フラグを忘れたり知らなかったりするユーザーが多いため、たった1つのデフォルト設定だけでも、実際の利用ではNinjaがMakeより「2倍以上速い」と感じられることがある
  • ユーザーが実際に体験できない最適化には大きな意味がない

速度において重要だった指標

  • ビルドシステムの性能には複数の意味がある
    • 最初からのフルビルドにどれだけ時間がかかるか
    • すでにビルドした後で1つのファイルを修正し、再ビルドするのにどれだけ時間がかかるか
  • Ninjaは大規模コードベースの インクリメンタルビルド における編集-コンパイルループの高速化に集中していた
  • 最初にNinjaを作ったときは、blaze、つまり bazel が非常に速いという記憶から、その速度に追いつこうとしていた
  • 後から見れば、関心のあった指標ではblazeは特別速いわけではなく、Javaプログラムなのでヘルプ表示ですら遅かった
  • インクリメンタルビルドに執着したのは、反復時間がプログラマーの満足度に大きく影響すると考えたからである
  • Ninjaは編集-コンパイルループで使われ、1秒と4秒の差が重要になる
  • 「速い」という意味はユーザーに伝えにくく、Ninjaマニュアルは小規模プロジェクトでは速度効果をほとんど感じられない可能性があると警告している
  • それでも「速い」は売りやすい表現なので、機能不足に不満を抱く小規模アプリのユーザーもNinjaを使いたがる
  • Ninjaはインクリメンタルな再ビルドに集中していたが、一部のユーザーはフルビルド性能も改善したと報告している
    • Ninja自身がほとんど何もせず、ビルド中のCPU使用が少なく、実際のビルド作業からCPUを奪いにくいためである
  • 出力も非常に簡潔である
    • 成功したビルドではたいてい1行しか出力しない
    • 他のビルドシステムは多くの段階やタイミング情報を大量に出力し、重く感じられることがある
  • あまり語らない構造が、Ninjaをより「存在しないかのように」感じさせる

普及を後押ししたCMake統合とWindows対応

  • CMake

    • NinjaはもともとChromeの特殊なビルドシステムと一緒に使うために作られた
    • Peter Collingbourneが、より広く使われているCMakeビルドシステムへNinjaを接続する作業を行った
    • この統合はLLVMの作業のために始まり、CMakeだけでなくNinja側にも新しいセマンティクスを追加する必要があった
    • 現実世界でNinjaが成功するうえで最も大きく貢献した人物としてPeterが挙げられている
    • その後CMakeの作者たちが統合を引き継いだが、要求や懸念に十分対応できなかった
    • 開発者自身は現在までCMakeを直接使ったことがない

  • Windows

    • ChromeがWindowsも対象としていたため、NinjaもWindowsで動作するようになった
    • Windows対応のかなりの部分は 貢献者 が書いた
    • 技術的にはWindows対応は大きな手間である
    • プロセス実行と出力キャプチャは、プラットフォームごとにAPIを新たに学ぶ必要がある種類の違いである
    • Ninjaの設計は、カーネルがキャッシュしたファイルの最終更新時刻を高速に取得できるという性質に依存しているが、Windowsではこれが成り立たない
    • それでもWindowsは開発者規模の大きいプラットフォームである
    • Linux向けの優れたツールは共有したいという衝動が強い一方、Windows向けツールは販売したいという衝動が強く、自由に提供されるツールは相対的に少ない
    • 初期のNinjaユーザーにWindows利用者が多かったのは当時驚きだったが、Windows開発者の母数が多いため、一部が関心を持つだけでもユーザーとして現れる

関連する取り組みを理解すること

  • Ninjaは当初、週末のデモ的ハックのように始まったため、作る前に関連する取り組みを十分調べられなかったことを残念に思っている
  • 何かを作るときには、設計空間を本当に理解することが重要である
  • 「action graph」という用語は、Ninjaを作ったときに使った表現ではなく、Googleのビルドシステムblaze/bazelから取り入れたものだ
  • bazelは、「library」「binary」のような高水準ターゲットのグラフが コマンドのグラフであるaction graph を生成すると説明している
  • コマンドラインテキストをファイルと同じ入力として見る発想は インクリメンタル計算 の一例である
  • インクリメンタル計算はビルドシステムだけでなく、UIのインクリメンタル性にもつながる
  • Jane Streetのブログには Incrementalの紹介記事 があり、ReactのようなUI構成方式ともつながっている
  • "Build Systems à la Carte" はビルドシステム文脈でインクリメンタル計算を論じた論文で、Ninja執筆前に存在していてほしかった資料として挙げられている

オープンソース保守の負担

  • オープンソースメンテナーの経験は特別楽しいものではなかった
  • プロジェクトへの感情は、誰かが良い言葉をかけてくれたときの誇りと、それ以上の大きな失望が入り混じっている
  • 無償で公開した結果、ときどき丁寧に頼む人もいたが、もっと多かったのは怒ったユーザーからの要求で、感謝の言葉はまれだった
  • 要求を受け入れなければフォークすると脅す人も繰り返しいた
  • 設計目標と衝突する合理的な貢献も別の難しさだった
    • 親切で賢い人が出した貢献を断るなら、十分な説明で応えたいと思ったが、その説明自体が消耗する作業だった
  • フリーソフトウェアを通じてプログラミングに入門し、受け取ったものを返したいと思ってコードを書いたが、今のフリーソフトウェアは対等な者同士の共有というより、ユーザーが自分を顧客のように見なし、作者をマネージャーに苦情を言う相手のように扱う流れがある
  • 今の動機は広く成功することより、尊敬する少数のハッカーに印象を残したり、その期待に応えたりすることに近い
  • Ninjaの成功は多くを学ばせてくれたが、もっと小さな成功でも同じような学びは得られただろうと見ている

メンテナーと貢献者

  • Nico Weberは慎重な協力者で、長年Ninjaのメンテナーを務めた
  • Jan Niklas HasseはNicoの後を引き継ぎ、うまくやっているように見える
  • そのほかにも多くの Ninja貢献者 がプロジェクトに参加している

関連記事

1件のコメント

 
GN⁺ 2024-11-30
Hacker News の意見

  • 「プログラミングはコードを書くことのように語られるが、実際にはコードよりもアーキテクチャが重要で、アーキテクチャよりも社会的な問題が重要になっていく」という表現が、長い間心の中にあった考えを正確に言い当てている

    • 強く同意する。Peopleware 1987 [1] でも同じことを述べている
      この本の第1章は「私たちの仕事における主要な問題は、技術的というより社会学的な性格が大きい」と主張し、チームの相性と結束、「没入時間」、静かな作業環境、離職コストといった社会的・政治的問題を扱っている
      [1] https://en.wikipedia.org/wiki/Peopleware:_Productive_Project...
    • プログラミングとそのツールはコンピュータのためではなく人間のためのもので、ごく些細なことを除けば、コンピュータ上で動く何かを作るには複数の人が必要になる
      だからソフトウェア工学は、多くの人が認めたり心地よく感じたりする以上に、ずっと社会科学に近いと思う。社会科学は自然科学より流動的で予測しにくいので、社会的な部分を避けるか、非常に原始的な形でしか扱わない傾向があるようだ。技術の原子的な細部には執着するのに、肝心のチームが作った製品はあまりにも頻繁にひどいものになる
    • https://en.wikipedia.org/wiki/Conway's_law
      「システムを設計する組織は、その組織のコミュニケーション構造を複製した設計を作らざるを得ない。」— Melvin E. Conway, How Do Committees Invent?
    • 私の経験では、技術的な問題のおよそ**80%**は、2人または2つのチームがただ向き合って話すことを嫌がるせいで起きる
    • とはいえ二分法ではない。優れたアーキテクチャは、人々がシステムに求めるものを満たしつつ、人間が理解できる状態に保ってくれる

  • 当時も議論されていた:
    The Success and Failure of Ninja - https://news.ycombinator.com/item?id=23157783 - 2020年5月、コメント38件
    1年ほど経てば再投稿も問題なく、過去スレッドへのリンクは、さらに知りたい読者のためのものだ

  • 「Android がシステムの何らかの大きなコンポーネントで Ninja を使っているが、正確には理解したことがない」という部分が面白い
    Ninja は実際に AOSP で大きな比重を占めている。ビルドシステムは最初 Makefile を使っていたが、カスタムの宣言型ビルドシステムである soong と、失敗・中断された Bazel 移行のために急速に複雑化した。Google は Makefile を Ninja ビルドファイルに変換する kati（https://github.com/google/kati）を作り、その成果物は本当に巨大だ:
    λ wc -l out/build-qssi.ninja
    3035442 out/build-qssi.ninja
    Makefile/soong から Ninja へ移る過程は苦痛で、最新のマシンでも数分かかるが、Ninja が受け取った後はものすごく高速に回る

    • Ninja を使ったことがないのだが、Makefile と比べてどんな利点があるのか気になる
      あるツールから別のツールへ変換するために、さらに別のツールを導入する価値があるのかも疑問だ。特に Ninja ファイルがあれほど大きく、人間には読みづらい可能性があるならなおさらだ

  • 「プログラマーはレイテンシを体感し、本人が気づいていなくても気分に影響を受けると信じている。Google が最近この分野の研究をしており、私の信念をある程度裏づけてくれた」という部分について、そのレイテンシ研究が実際に公開されたのか気になる

  • Ninja はゲーム開発者の間でかなり人気がある
    「Windows は今でも開発者の観点では巨大なプラットフォームであり、その開発者たちはツールに飢えている」という文が興味深かった。主に Windows で開発している立場からすると、むしろ優れたデバッガである Visual Studio やプロファイラである Superluminal なしで暮らしている Linux 開発者のほうが、ツールに飢えているように感じる。最近は2つのプラットフォーム間の差がだんだん小さくなっているようで、概してクロスプラットフォームで動作する Rust ユーティリティも気に入っている

    • 誰かが Visual Studio と「良い」を同じ文に入れるたびに、宇宙はシミュレーションで、他の人たちは別の宇宙から来たのではないかという奇妙な感覚になる
      Visual Studio とのやり取りの中で「良い」と呼べるものが思い浮かばない。「かろうじて許容範囲」くらいならいくつか思いつくが、デバッグはそこに入らない。ただし 2022 ではデバッガがもはやバグだらけではないので、たぶんその話なのかもしれない
    • どんな世界で Visual Studio デバッガが良いと見なされているのか分からない。ついに修正されたのならともかく、最後に使ったときは1行ステップ実行するのに何秒もかかるほど耐えがたく遅かった
    • UNIX が開発者ツールのすべてだと考えるコミュニティがあり、そのせいで森を見て木を見落としているように思う
      1993年に Xenix に触れて以来、さまざまな派生版を使ってきたくらい UNIX には詳しいが、WSL は Linux Docker コンテナを動かす用途以外ではほとんど使っていない

  • まだ Ninja を使っていたいくつかのものは samurai に置き換えたし、可能なあらゆる面で改善されていた。
    それでも、この種のビルドシステムは方向性が間違っていると思う。ビルドシステムに望むのは、すべての推移的な入力の内容をハッシュし、その結果がレジストリにあるかどうかを問い合わせることだ。

    • その通り。分散キャッシュをサポートするビルドシステムは、基本的に変更確認にタイムスタンプではなくダイジェストを使う: Bazel、Pants、Buck などがそうだ。
      ただし、どれも非常に複雑だ。ローカルビルドだけで見れば、SCons と Waf も変更検出にハッシュを使っていると理解している。
    • Ninja の作者が作った n2 に興味があるかもしれない。
    • それは NetKernel のアイデアだった気がする。
      似たものとして Deno ライブラリ “TDAR”[1] を作っていて、うまく動くが、変更可能なファイルシステム上で動作することを前提にしたコマンドラインツールを、純粋関数のように呼び出しているふりをするラッパーにするには少し手間がかかる。
      [1] まだ上位プロジェクト[2]から切り出してはいないが、この YouTube 動画で話した: https://youtu.be/sty29o8sUKI
      [2] こういうものに興味があるなら、ソースを公開しろとせっついてくれてもよい。togos zero zero at gee mail dot comb
    • Samurai の何が優れているのか気になる。Ninja の互換サブセットだと思っていた。
      それに「自分が望んでいたものではない」は、すなわち「間違っている」という意味ではない。世の中には好みの違う人もいるからだ。
    • Samurai がまだ生きているのか分からない。シグナル処理を改善するプルリクエストを送ったが、半年以上無視されたままだ。

  • CMake で C++20 モジュールを使うには Ninja が必要なので、Ninja はかなり長く残るだろう。

  • いちばん興味深かったのは、「正確性と利便性または性能の間でしばしば妥協が必要であり、その連続線上のどこを選ぶのかを意識的であるべきだ」という部分だ。
    一部のプログラマーはこの力学をあまりに硬直的に見て、片方の価値が当然優先されると考える。しかし実際には相互作用はかなり微妙だ。たとえば、正確性を一部犠牲にして利便性を取ったツールが、より正確だが利便性の低い代替手段よりも、エコシステム全体ではより正しい結果をもたらすことがある。プログラマーが後者を避けるようになる場合がそうだ。

    • これは本当に金鉱のような洞察だ。だから Python、Go、TypeScript/JavaScript は Haskell/OCaml よりはるかに人気がある。

  • 「恥ずかしい名前は許してほしい」だなんて、名前は素晴らしい。
    追伸: これを実装すれば、もっと高速にできるかもしれない: https://github.com/ninja-build/ninja/issues/2157 ただし記事で説明されているように、このツールは前回実行から得られるごく小さなヒントさえ含め、意図的に状態を持たない。