Ninja 是设计目标为速度快而生的构建系统，通过官方的博客，本文来深入了解下 Ninja 为何而快。

内容来源： https://aosabook.org/en/posa/ninja.html
原文标题：Ninja
作者：Evan Martin
译者：流左沙
注：翻译较原文会有一定的精简、重排和添删，主要是为了提取重要内容以达到更好的理解，请以原文为准。

As input you describe the commands necessary to process source files into target files. Ninja uses these commands to bring targets up to date. Unlike many other build systems, Ninja’s main design goal was speed.

输入是描述从源文件到目标文件的所需要的参数，Ninja 用这些命令更新目标文件。与其他构建系统不同的是，Ninja 的主要目标是速度快。

Ninja’s other main design goal followed: Ninja needed to be easily embedded within a larger build system.

另一个目标就是：Ninja 需要很方便地就可以嵌入到大型的构建系统。

Design

At a high level any build system performs three main tasks. It will (1) load and analyze build goals, (2) figure out which steps need to run in order to achieve those goals, and (3) execute those steps.

构建系统主要有三个任务：加载和分析编译目标、理解哪些步骤需要被执行、运行这些步骤。

Ninja’s build file language is therefore simple to the point of being inconvenient for humans to write. There are no conditionals or rules based on file extensions. Instead, the format is just a list of which exact paths produce which exact outputs. These files can be loaded quickly, requiring almost no interpretation.

Ninja 的构建文件所用的语言是如此的简陋，对于人而言是很难编写的。它没有对于文件扩展的状态或者规则。它只有一系列指定的输入和输出。这些文件可以被加载得很快，不需要任何的理解时间。

This minimalist design counterintuitively leads to greater flexibility. Because Ninja lacks higher-level knowledge of common build concepts like an output directory or current configuration, Ninja is simple to plug into larger systems (e.g., CMake, as we later found) that have different opinions about how builds should be organized. For example, Ninja is agnostic as to whether build outputs (e.g., object files) are placed alongside the source files (considered poor hygiene by some) or in a separate build output directory (considered hard to understand by others). Long after releasing Ninja I finally thought of the right metaphor: whereas other build systems are compilers, Ninja is an assembler.

最少量的设计反而带来了更好的灵活性。因为 Ninja 对于基本的编译概念缺乏高层级的知识，所以它很容易就能嵌入到不同操作的大型系统中。例如，Ninja 对于编译输出是否放在源文件那或者单独的一个目录是无感知的。总的来说，其他构建系统是编译器，而 Ninja 是集成者。

Philosophical

Where other build systems are high-level languages, Ninja aims to be an assembler.

其他的构建系统都是高级语言，而 Ninja 目标是当一个集成器。

Build systems get slow when they need to make decisions. When you are in a edit-compile cycle you want it to be as fast as possible — you want the build system to do the minimum work necessary to figure out what needs to be built immediately.

构建系统由于需要去做判断所以会变得慢。如果想加快，那么就要构建系统只做最小的必要的工作来完成构建。

Ninja contains the barest functionality necessary to describe arbitrary dependency graphs. Its lack of syntax makes it impossible to express complex decisions.

Ninja 包含了描述任意依赖关系图的所必需的最基本的功能。它缺乏语法去表达复杂的决策。

Instead, Ninja is intended to be used with a separate program generating its input files. The generator program (like the ./configure found in autotools projects) can analyze system dependencies and make as many decisions as possible up front so that incremental builds stay fast. Going beyond autotools, even build-time decisions like "which compiler flags should I use?" or "should I build a debug or release-mode binary?" belong in the .ninja file generator.

Ninja 用来和一个单独的进程来生成其输入文件。生成器进程可以分析系统依赖关系，提前做好尽可能多的决策来加快增量构建。除了 autotools 之外，应该用什么编译参数、应该用 debug 模式还是 release 模式，都在 .ninja 文件生成器中。

Work

A human needs to debug the files when the build rules are wrong, so .ninja build files are plain text, similar to Makefiles, and they support a few abstractions to make them more readable.

当出错时我们需要调试文件，所以 .ninja 文件是纯文本，和 Makefiles 类似，它还支持一些抽象的概念来提供可读性。

The first abstraction is the “rule”, which represents a single tool’s command-line invocation. A rule is then shared between different build steps. Here is an example of the Ninja syntax for declaring a rule named “compile” that runs the gcc compiler along with two build statements that make use of it for specific files.

第一个抽象概念是规则，代表的是一个工具的参数调用。一个规则在不同的编译步骤中可以共享。如下案例：

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

The second abstraction is the variable. In the example above, these are the dollar-sign-prefixed identifiers ($in and $out). Variables can represent both the inputs and outputs of a command and can be used to make short names for long strings. Here is an extended compile definition that makes use of a variable for compiler flags:

第二个抽象概念是变量。在上面的案例中，是有美元符号 $ 的标识符。变量可以代表着参数中的输入和输出，可以用来简短长串。

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

The build file, once parsed, describes a graph of dependencies: the final output binary depends on linking a number of objects, each of which is the result of compiling sources. Specifically it is a bipartite graph, where “nodes” (input files) point to “edges” (build commands) which point to nodes (output files)6. The build process then traverses this graph.

构建文件一旦被解析，就会有依赖图：最终输出的二进制是由一堆目标文件链接而成的，每一个都是编译源文件的结果。这是二向图，输入文件通过编译参数(边)指向了输出文件。编译过程就是遍历这个图。

Given a target output to build, Ninja first walks up the graph to identify the state of each edge’s input files: that is, whether or not the input files exist and what their modification times are. Ninja then computes a plan. The plan is the set of edges that need to be executed in order to bring the final target up to date, according to the modification times of the intermediate files. Finally, the plan is executed, walking down the graph and checking off edges as they are executed and successfully completed.

给定一个编译目标，Ninja 首先会遍历图的每条边以确认每个输入文件的状态：输入文件是否存在，以及它们的修改时间是什么时候。Ninja 会计算一个计划列表，这个计划列表是一系列需要被执行的边(用以更新输出目标)，根据中间文件的修改时间来进行判断。最终，计划列表里的边会被执行，遍历这个图然后检查这些边是否被执行成功。

Optimizing

The initial implementation of Ninja was careful to arrange the data structures in order to allow a fast build, but wasn’t particularly clever in terms of optimizations. Once the program worked, I reasoned, a profiler could reveal which pieces mattered.

Ninja 的初始版本是小心地安排数据结构以达到快速编译，但并非对于优化足够清晰。一旦程序跑起来，profiler 可以知道哪些部分是重要的。

Over the years, profiling pointed at different pieces of the program. Sometimes the worst offender was a single hot function that could be micro-optimized. At other times, it suggested something more broad like being careful not to allocate or copy memory except when necessary. There were also cases where a better representation or data structure had the most impact. What follows is a walk through the Ninja implementation and some of the more interesting stories about its performance.

profile 文件指向程序的不同地方。有时更糟糕的是一个热函数会被小量的优化。其他时候，它会建议只在必要时才分配或复制内存。对于更好的代码结构和数据结构影响更大。之后就是编译 Ninja 的实现，优化它的性能。

Parser

Initially Ninja used a hand-written lexer and a recursive descent parser. The syntax was simple enough, I thought. It turns out that for a large enough project like Chrome8, simply parsing the build files (named with the extension .ninja) can take a surprising amount of time.

早期时 Ninja 使用手写的 lexer 和递归下降的解析器。这个语法是十分地简单，导致大型工程的构建文件 (.ninja) 会占用大量的时间。

A simple fix–at the time saving 200 ms–was to replace the function with a 256-entry lookup table that could be indexed by the input character.

使用表结构来处理输入参数可以加快这个时间。

Canonicalization

Ninja avoids using strings to identify paths. Instead, Ninja maps each path it encounters to a unique Node object and the Node object is used in the rest of the code. Reusing this object ensures that a given path is only ever checked on disk once, and the result of that check (i.e., the modification time) can be reused in other code.

Ninja 不用字符串表示路径。相反，它把每个路径映射成一个节点来使用。重用这个节点可以让它只在磁盘检查一次路径，而且检查结果也能够复用。

To always use the same Node for a single file, Ninja must reliably map every possible name for a file into the same Node object. This requires a canonicalization pass on all paths mentioned in input files, which transforms a path like foo/../bar.h into just bar.h. Initially Ninja simply required all paths to be provided in canonical form but that ends up not working for a few reasons. One is that user-specified paths (e.g., the command-line ninja ./bar.h) are reasonably expected to work correctly. Another is that variables may combine to make non-canonical paths. Finally, the dependency information emitted by gcc may be non-canonical.

为了使同一个节点代表的是同一个文件，Ninja 需要非常可靠地把路径名映射到节点。这需要一个规范化的 pass 去处理输入文件的所有路径。开始时，Ninja 会需要所有的路径都以规范化的格式组织起来，但最终没有用处，一个是用户指定的路径，另一个则是变量可能会被拼接成一个非规范化的路径。最后，gcc 生成的依赖信息就不是规范化的。

Thus most of what Ninja ends up doing is path processing, so canonicalizing paths is another hot point in profiles. The original implementation was written for clarity, not performance, so standard optimization techniques–like removing a double loop or avoiding memory allocation–helped considerably.

因此大多数时候 Ninja 是在解析路径，所以规范化的路径是 profile 文件上的热点。原始的实现是为了写得清晰，但没有好的性能，所以标准优化技术像去除双重循环和避免内存分配都很有作用。

Build Log

One part of the Linux kernel build system tracks the commands used to generate outputs. Consider a motivating example: you compile an input foo.c into an output foo.o, and then change the build file such that it should be rebuilt with different compilation flags. For the build system to know that it needs to rebuild the output, it must either note that foo.o depends on the build files themselves (which, depending on the organization of the project, might mean that a change to the build files would cause the entire project to rebuild), or record the commands used to generate each output and compare them for each build.

一部分的构建系统是根据参数来生成输出文件的。比如我们修改了参数就得重编。构建系统想知道是否需要重编输出文件，它就需要标记输出文件依赖于哪些构建文件(.ninja)，否则需要记录用来生成输出文件的参数并进行对比。

While building, Ninja writes out a build log that records the full commands used to generate each output.9 Then for each subsequent build, Ninja loads the previous build log and compares the new build’s commands to the build log’s commands to detect changes. This, like loading build files or path canonicalization, was another hot point in profiles.

编译时，Ninja 生成一个 build log 来记录输出文件的全部参数。然后在之后每次编译时，它会加载之前的 build log 然后对比参数来判断是否改变了。像加载构建文件(.ninja)或者规范化，都是 profile 里的热点。

After making a few smaller optimizations Nico Weber, a prolific contributor to Ninja, implemented a new format for the build log. Rather than recording commands, which are frequently very long and take a lot of time to parse, Ninja instead records a hash of the command. In subsequent builds, Ninja compares the hash of the command that is about to be run to the logged hash. If the two hashes differ, the output is out of date. This approach was very successful. Using hashes reduced the size of the build log dramatically–from 200 MB to less than 2 MB on Mac OS X–and made it over 20 times faster to load.

在进行过一些少量优化之后，实现了一个 build log 的新格式。为了避免记录所有的参数(耗时巨大)，Ninja 采用记录参数的哈希值。在之后的编译，直接比较哈希值就可以了。这个优化减少了 build log 的大小和优化了将近 20 倍的速度。

Dependency Files

Some build systems use a “header scanner” to extract these dependencies at build time, but this approach can be slow and is difficult to make exactly correct in the presence of #ifdef directives. Another alternative is to require the build files to correctly report all dependencies, including headers, but this is cumbersome for developers: every time you add or remove an #include statement you need to modify or regenerate the build.

一些构建系统采用头文件扫描的方式在编译时提取依赖信息，但这个方式会很慢，而且很难去正确地提取，尤其是在宏判断之下。另一个选择是需要构建文件(.ninja)去正确地反映这些依赖，包括头文件，但这对于开发者而言很繁琐：需要跟着宏的修改同步操作。

A better approach relies on the fact that at compile time gcc (and Microsoft’s Visual Studio) can output which headers were used to build the output. This information, much like the command used to generate an output, can be recorded and reloaded by the build system so that the dependencies can be tracked exactly. For a first-time build, before there is any output, all files will be compiled so no header dependency is necessary. After the first compilation, modifications to any files used by an output (including modifications that add or remove additional dependencies) will cause a rebuild, keeping the dependency information up-to-date.

一个更好的方式是依赖 gcc 在编译时可以得到输出文件用到哪些头文件。这些信息有点像哪些参数用来生成输出文件，可以被构建系统记录或重复加载，所以依赖信息可以被追踪。在第一次编译时，在存在任何输出之前，所有文件都会被编译，所以没有用到头文件依赖信息的必要。在之后的编译，修改任何输出文件用到的文件都会引起重编，保证依赖信息是最新的。

When compiling, gcc writes header dependencies in the format of a Makefile. Ninja then includes a parser for the (simplified subset) Makefile syntax and loads all of this dependency information at the next build. Loading this data is a major bottleneck. On a recent Chrome build, the dependency information produced by gcc sums to 90 MB of Makefiles, all of which reference paths which must be canonicalized before use.

当编译时，gcc 以 Makefile 的格式写出头文件的依赖信息。Ninja 会包含一个 Makefile 的语法解析器，然后会在下次编译时加载所有的依赖信息。加载这些数据是主要的瓶颈。Makefile 的大小和引用的路径需要被规范化都占用大量的时间。

Once Ninja has started executing build commands, all of the performance-critical work has been completed and Ninja is mostly idle as it waits for the commands it executes to complete. In this new approach for header dependencies, Ninja uses this time to process the Makefiles emitted by gcc as they are written, canonicalizing paths and processing the dependencies into a quickly deserializable binary format. On the next build Ninja only needs to load this file. The impact is dramatic, particularly on Windows. (This is discussed further later in this chapter.)

一旦 Ninja 开始处理编译参数，所有的性能监控都会被完成，Ninja 是几乎空闲的，因为它在等在参数被执行完成。在最新的头文件依赖的记录方法中，Ninja 使用这部分时间来处理 gcc 写出的 Makefile 文件，规范化路径，以及把依赖转成可快速反序列化的二进制格式。在下一次编译时，Ninja 只需要加载这个文件。

The “dependency log” needs to store thousands of paths and dependencies between those paths. Loading this log and adding to it needs to be fast. Appending to this log should be safe, even in the event of an interruption such as a cancelled build.

这个依赖日志需要存储上千的路径和路径间的依赖关系。加载这个日志或者写入这个日志都需要快。日志增加需要是安全的，即使在编译被中断时。

After considering many database-like approaches I finally came up with a trivial implementation: the file is a sequence of records and each record is either a path or a list of dependencies. Each path written to the file is assigned a sequential integer identifier. Dependencies are then lists of integers. To add dependencies to the file, Ninja first writes new records for each path that doesn’t yet have an identifier and then writes the dependency record using those identifiers. When loading the file on a subsequent run Ninja can then use a simple array to map identifiers to their Node pointers.

最终的实现方式是：这个文件是一系列的记录，每个记录要么是路径，要么是一系列的依赖。每个写入这个文件的路径都被赋值一个唯一的整型标识符。依赖就是一系列的整数。为了给这个文件添加依赖，Ninja 首先写入每个路径的新的记录(还没有标识符的)，然后使用它们的标识符来写入依赖。当加载这个文件时，Ninja 可以使用简单的数组来映射每个标识符到它的节点。

Executing a Build

Ninja runs build commands in parallel by default, based on the number of available CPUs on the system. Since commands running simultaneously could have their outputs interleave, Ninja buffers all output from a command until that command completes before printing its output. The resulting output appears as if the commands were run serially.11

Ninja 默认会并行编译，基于系统的可用 CPU 的数量。由于同时运行编译会存在输出文件有交集的情况，Ninja 将一个命令的所有输出文件都缓存起来，直到这个命令被执行完成。

This control over command output allows Ninja to carefully control its total output. During the build Ninja displays a single line of status while running; if the build completes successfully the total printed output of Ninja is a single line.12 This doesn’t make Ninja run any quicker but it makes Ninja feel fast, which is almost as important to the original goal as real speed is.

在编译时，Ninja 会用一行文字来显示运行状态，成功后也只会显示一行文字。这会让 Ninja 感觉很快。

Comparison to Make

Ninja is closest in spirit and functionality to Make, relying on simple dependencies between file timestamps.

Ninja 本质上和功能上与 Make 相近，依赖于文件时间戳之间的简单依赖关系。

But fundamentally, make has a lot of features: suffix rules, functions, built-in rules that e.g. search for RCS files when building source. Make’s language was designed to be written by humans. Many projects find make alone adequate for their build problems.

但基本上，Make 还有大量的特性。Make 语言设计成人类可写的形式，许多项目只用 make 就能解决构建的问题。

In contrast, Ninja has almost no features; just those necessary to get builds correct while punting most complexity to generation of the ninja input files. Ninja by itself is unlikely to be useful for most projects.

相反的，Ninja 几乎没有任何特性。只是那些必要的能力：在生成 ninja 输入文件的复杂流程中，保证构建的正确性。

Conclusions

Simplicity is a virtue in software; the question is always how far it can go. Ninja managed to cut much of the complexity from a build system by delegating certain expensive tasks to other tools (GYP or CMake), and because of this it is useful in projects other than the one it was made for. Ninja’s simple code hopefully encouraged contributions– the majority of work for supporting OS X, Windows, CMake, and other features was done by contributors. Ninja’s simple semantics have led to experiments by others to reimplement it in other languages (Scheme and Go, to my knowledge).

Ninja 通过把复杂的操作转交给其他工具，成功降低了构建系统的复杂性。Ninja 简单的代码逻辑吸引了很多开发者的贡献，主要是支持了 OS X、Windows、Cmake 等。同时它简单的语法也催生出很多其他编程语言的版本。

reference

https://aosabook.org/en/posa/ninja.html

https://ninja-build.org/manual.