开源软件的性能
Ninja

Ninja 是一个类似于 Make 的构建系统。作为输入，您描述将源文件处理成目标文件所需的命令。Ninja 使用这些命令来更新目标。与许多其他构建系统不同，Ninja 的主要设计目标是速度。

我在为 Google Chrome 工作时编写了 Ninja。我最初将 Ninja 作为一项实验，以了解是否可以加快 Chrome 的构建速度。为了成功构建 Chrome，Ninja 的另一个主要设计目标随之而来：Ninja 需要能够轻松地嵌入到更大的构建系统中。

Ninja 一直默默地取得成功，逐渐取代了 Chrome 使用的其他构建系统。在 Ninja 公开之后，其他人也贡献了代码来使流行的 CMake 构建系统生成 Ninja 文件——现在 Ninja 也被用于开发基于 CMake 的项目，如 LLVM 和 ReactOS。其他项目，例如 TextMate，直接从其自定义构建中面向 Ninja。

我从 2007 年到 2012 年一直在 Chrome 工作，并在 2010 年开始开发 Ninja。有许多因素会影响像 Chrome 这样大型项目的构建性能（今天大约有 40,000 个 C++ 代码文件生成一个大约 90 MB 大小的输出二进制文件）。在我工作期间，我接触了其中许多因素，从跨多个机器分配编译到链接中的技巧。Ninja 主要只针对构建的前端。这是指从启动构建到第一个编译开始运行之间的时间。要理解为什么这很重要，需要了解我们如何看待 Chrome 本身的性能。

Chrome 的简史

这里不讨论 Chrome 的所有目标，但该项目的一个定义目标是速度。性能是一个涵盖所有计算机科学的广泛目标，Chrome 使用了几乎所有可用的技巧，从缓存到并行化再到即时编译。然后是启动速度——程序在点击图标后显示在屏幕上的时间——与之相比似乎有点微不足道。

为什么要关心启动速度？对于浏览器来说，快速启动会带来一种轻盈的感觉，让人感觉在网上做一些事情就像打开一个文本文件一样简单。此外，延迟对您幸福感和失去思路的影响在人机交互中得到了充分的研究。延迟尤其受到 Google 或 Amazon 等网络公司的关注，它们处于一个能够衡量和实验延迟影响的有利位置——并且他们已经进行了实验表明，即使是毫秒级的延迟也会对人们使用网站或进行购买的频率产生可衡量的影响。这是一种潜意识中积累的小挫折。

Chrome 采用了一种巧妙的技巧来快速启动，这是 Chrome 首批工程师之一想出来的。一旦他们将骨架应用程序发展到可以在屏幕上显示窗口的程度，他们就创建了一个衡量该速度的基准，并使用一个持续的构建来跟踪它。然后，用 Brett Wilson 的话说，“一个非常简单的规则：这个测试永远不能变得更慢。”¹ 当代码被添加到 Chrome 中时，维护这个基准需要额外的工程努力²——在某些情况下，工作被推迟到真正需要的时候，或者在启动期间使用的数据被预先计算——但主要的“技巧”是性能，也是给我印象最深的一个，就是少做工作。

我加入 Chrome 团队时并没有打算从事构建工具的工作。我的背景和首选平台是 Linux，我想成为 Linux 大神。为了限制项目范围，最初只针对 Windows 平台；我认为我的任务是帮助完成 Windows 实现，以便我之后可以使其在 Linux 上运行。

在开始其他平台上的工作时，第一个障碍是理清构建系统。到那时，Chrome 已经很大了（事实上已经完成了——Windows 版 Chrome 在任何移植开始之前就于 2008 年发布了），因此，即使将基于 Visual Studio 的 Windows 构建整体切换到另一个构建系统，也与正在进行的开发相冲突。感觉就像在建筑物正在使用时更换它的地基。

Chrome 团队的成员提出了一个称为GYP³ 的增量解决方案，该解决方案可以一次使用一个子组件，生成 Chrome 已经使用的 Visual Studio 构建文件以及将在其他平台上使用的构建文件。

对 GYP 的输入很简单：所需的输出名称以及源文件的纯文本列表，偶尔的自定义规则，例如“处理每个 IDL 文件以生成一个额外的源文件”，以及一些条件行为（例如，只在某些平台上使用某些文件）。GYP 然后使用这种高级描述生成平台本地的构建文件。⁴

在 Mac 上，“本地构建文件”意味着 Xcode 项目文件。然而，在 Linux 上，没有明显的单一选择。最初的尝试使用了 Scons 构建系统，但令我沮丧地发现，GYP 生成的 Scons 构建可能需要 30 秒才能启动，而 Scons 正在计算哪些文件发生了更改。我认为 Chrome 的规模与 Linux 内核大致相当，因此那里采用的方法应该可以奏效。我撸起袖子，编写了代码让 GYP 使用内核 Makefile 中的技巧生成普通的 Makefile。

因此，我无意中开始了我的构建系统疯狂之旅。许多因素会导致软件构建耗费时间，从缓慢的链接器到糟糕的并行化，我深入研究了所有这些因素。Makefile 方法最初非常快，但是当我们将更多 Chrome 代码移植到 Linux 时，构建中使用的文件数量越来越多，它变得越来越慢。⁵

在移植过程中，我发现构建过程中的一个部分特别令人沮丧：我会对单个文件进行更改，运行 make，意识到我漏掉了分号，再次运行 make，每次等待的时间都足够长，以至于我会忘记自己在做什么。我回想起我们如何为最终用户竭尽全力对抗延迟。“为什么这会花费这么长时间，”我想，“不可能有那么多工作要做。”我将 Ninja 作为一项实验，看看我可以让它变得多么简单。

Ninja 的设计

从高级角度来看，任何构建系统都执行三个主要任务。它会（1）加载并分析构建目标，（2）找出为了实现这些目标需要运行哪些步骤，以及（3）执行这些步骤。

为了使步骤（1）中的启动速度更快，Ninja 在加载构建文件时需要做最少的工作。构建系统通常由人类使用，这意味着它们提供了方便的、高级的语法来表达构建目标。这也意味着当真正构建项目时，构建系统必须进一步处理指令：例如，在某个时刻，Visual Studio 必须根据构建配置具体确定输出文件的位置，或者哪些文件必须使用 C++ 或 C 编译器编译。

因此，GYP 在生成 Visual Studio 文件方面的工作实际上仅限于将源文件列表转换为 Visual Studio 语法，并将大部分工作留给 Visual Studio 来完成。通过 Ninja，我看到了在 GYP 中完成尽可能多工作的机会。从某种意义上说，当 GYP 生成 Ninja 构建文件时，它会执行所有上述计算一次。然后，GYP 将该中间状态的快照保存为一种格式，Ninja 可以快速加载该格式以进行每次后续构建。

因此，Ninja 的构建文件语言简单到对人类来说编写起来很不方便。没有基于文件扩展名的条件语句或规则。相反，该格式只是一个列表，其中列出了哪些确切的路径生成哪些确切的输出。这些文件可以快速加载，几乎不需要解释。

这种极简主义的设计反直觉地带来了更大的灵活性。由于 Ninja 缺乏对输出目录或当前配置等常见构建概念的高级了解，因此 Ninja 很容易插入到具有不同构建组织方式的更大的系统（例如，CMake，正如我们后来发现的）中。例如，Ninja 对构建输出（例如，目标文件）是放置在源文件旁边（被某些人认为是不卫生的）还是在单独的构建输出目录中（被另一些人认为难以理解）是无知的。在发布 Ninja 很久之后，我终于想到了一个合适的比喻：其他构建系统是编译器，而 Ninja 是汇编器。

Ninja 做了什么

如果 Ninja 将大部分工作推给了构建文件生成器，那么还有什么工作要做呢？以上理念在原则上很好，但现实世界中的需求总是更复杂。Ninja 在开发过程中不断发展（和丢失）功能。在每一步中，最重要的问题始终是“我们能做更少吗？”以下是对其工作原理的简要概述。

当构建规则错误时，人类需要调试文件，因此 .ninja 构建文件是纯文本，类似于 Makefile，并且它们支持一些抽象，使其更易于阅读。

第一个抽象是“规则”，它表示单个工具的命令行调用。然后，一个规则在不同的构建步骤之间共享。以下是一个使用名为“compile”的规则声明 Ninja 语法的示例，该规则运行 gcc 编译器以及两个使用它的特定文件的 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

第二个抽象是变量。在上面的示例中，这些是美元符号前缀的标识符（$in 和 $out）。变量可以表示命令的输入和输出，也可以用来为长字符串创建简短的名称。以下是一个扩展的编译定义，它使用一个变量来表示编译器标志

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

在规则中使用的变量值可以通过缩进其新定义来在单个 build 块的范围内进行覆盖。继续上面的示例，cflags 的值可以针对单个文件进行调整

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

规则的行为几乎就像函数，变量的行为就像参数。这两个简单的功能非常接近编程语言——与“不做工作”的目标背道而驰。但它们具有重要的优势，可以减少重复的字符串，这不仅对人类有用，而且对计算机也有用，减少了要解析的文本数量。

构建文件解析后，描述了一个依赖关系图：最终的输出二进制文件依赖于链接多个对象，每个对象都是编译源的结果。具体来说，它是一个二部图，其中“节点”（输入文件）指向“边”（构建命令），而“边”又指向节点（输出文件）⁶。构建过程然后遍历此图。

给定一个要构建的目标输出，Ninja 首先会遍历图以确定每个边输入文件的状态：即输入文件是否存在以及它们各自的修改时间。然后 Ninja 会计算一个计划。这个计划是需要执行的边集，以便根据中间文件的修改时间，将最终目标更新到最新状态。最后，执行计划，遍历图并检查已执行并成功完成的边。

一旦这些部分到位，我就可以为 Chrome 建立一个基准测试：在成功完成构建后再次运行 Ninja 的时间。这是加载构建文件、检查构建状态并确定没有工作要做的所需时间。这个基准测试运行所需的时间不到一秒。这是我的新的启动基准测试指标。然而，随着 Chrome 的发展，Ninja 必须不断加快速度，以防止该指标出现倒退。

优化 Ninja

Ninja 的初始实现非常谨慎地安排数据结构，以便允许快速构建，但在优化方面并不是特别聪明。我推断，一旦程序正常运行，分析器就可以揭示哪些部分很重要。⁷

多年来，分析器指向程序的不同部分。有时最糟糕的罪魁祸首是一个可以进行微优化，而且很重要的单个热函数。在其他时候，它会建议更广泛的事情，例如小心不要在必要时分配或复制内存。还有一些情况是，更好的表示或数据结构对性能影响最大。下面我们将介绍 Ninja 实现以及它的一些关于性能的更有趣的故事。

解析

最初，Ninja 使用手写的词法分析器和递归下降解析器。我认为语法足够简单。事实证明，对于像 Chrome⁸ 这样的大型项目，仅仅解析构建文件（以 .ninja 为扩展名命名）就可能花费令人惊讶的时间。

分析单个字符的原始函数很快出现在分析器中。

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

一个简单的解决办法（当时节省了 200 毫秒）是用一个 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 在相当长一段时间内保持快速运行。最终我们转向更原则性的东西：re2c，这是 PHP 使用的词法分析器生成器。它可以生成更复杂的查找表和难以理解的代码树。例如

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

是否将输入本身视为文本仍然是一个悬而未决的问题。也许最终我们将要求 Ninja 的输入以某种机器友好的格式生成，这将使我们能够在很大程度上避免解析。

规范化

Ninja 避免使用字符串来标识路径。相反，Ninja 将它遇到的每条路径映射到一个唯一的 Node 对象，然后在代码的其余部分中使用 Node 对象。重复使用此对象确保给定路径仅在磁盘上检查一次，并且该检查的结果（即修改时间）可以在其他代码中重复使用。

指向 Node 对象的指针充当该路径的唯一标识。要测试两个 Node 是否引用同一路径，只需比较指针，而无需进行更昂贵的字符串比较。例如，当 Ninja 遍历构建输入的图时，它会保留一个依赖 Node 栈来检查依赖循环：如果 A 依赖于 B，B 依赖于 C，C 依赖于 A，则构建无法继续。这个表示文件的栈可以用一个简单的指针数组实现，并且可以使用指针相等来检查重复项。

要始终对单个文件使用相同的 Node，Ninja 必须可靠地将文件的所有可能名称映射到相同的 Node 对象。这要求对输入文件中提到的所有路径进行规范化处理，将类似于 foo/../bar.h 的路径转换为 bar.h。最初，Ninja 只要求所有路径都以规范形式提供，但这最终不起作用，原因有几个。一个原因是，合理地期望用户指定的路径（例如，命令行 ninja ./bar.h）能够正常工作。另一个原因是变量可能会组合成非规范路径。最后，gcc 发出的依赖信息可能是非规范的。

因此，Ninja 大部分工作最终变成了路径处理，所以规范化路径是分析器中另一个重要的点。原始实现是为了清晰，而不是为了性能，因此标准优化技术（如消除双重循环或避免内存分配）起到了相当大的帮助作用。

构建日志

通常，上述微优化不如结构优化那样有影响力，结构优化会改变算法或方法。这在 Ninja 的构建日志中就是这样。

Linux 内核构建系统的一部分跟踪用于生成输出的命令。考虑一个激励性的例子：你将输入 foo.c 编译成输出 foo.o，然后更改构建文件，使其以不同的编译标志重新构建。为了让构建系统知道它需要重新构建输出，它必须要么注意到 foo.o 依赖于构建文件本身（这取决于项目的组织方式，可能意味着对构建文件的更改会导致整个项目重新构建），要么记录用于生成每个输出的命令，并在每次构建时进行比较。

内核（以及随之而来的 Chrome Makefiles 和 Ninja）采取了后一种方法。在构建过程中，Ninja 会写出一个构建日志，记录用于生成每个输出的完整命令。⁹ 然后，在每次后续构建中，Ninja 会加载上一次构建日志，并将新构建的命令与构建日志的命令进行比较，以检测更改。这就像加载构建文件或路径规范化一样，是分析器中的另一个重要点。

在进行了一些较小的优化之后，Nico Weber（Ninja 的一位多产贡献者）为构建日志实现了一种新的格式。Ninja 不再记录命令（命令通常很长，解析需要很多时间），而是记录命令的哈希值。在后续构建中，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（以及微软的 Visual Studio）可以输出用于构建输出的头文件。这种信息，就像用于生成输出的命令一样，可以由构建系统记录和重新加载，以便可以准确地跟踪依赖关系。对于第一次构建，在没有输出之前，所有文件都将被编译，因此不需要头文件依赖。在第一次编译之后，对用于输出的任何文件的修改（包括添加或删除其他依赖关系的修改）都会导致重新构建，从而保持依赖信息是最新的。

在编译时，gcc 会以 Makefile 格式写入头文件依赖关系。然后，Ninja 包含一个（简化子集）Makefile 语法的解析器，并在下次构建时加载所有这些依赖信息。加载这些数据是一个主要瓶颈。在最近的 Chrome 构建中，gcc 生成的依赖信息总共包含 90 MB 的 Makefile，所有这些 Makefile 都引用必须在使用之前进行规范化的路径。

就像其他解析工作一样，使用 re2c 并尽可能避免复制也有助于提高性能。然而，就像工作转移到 GYP 一样，这种解析工作可以推迟到启动的临界路径之外的时间。我们对 Ninja 最近的工作（截至本文撰写之时，该功能已完成但尚未发布）是让这种处理在构建过程中及时发生。

一旦 Ninja 开始执行构建命令，所有性能关键的工作就都完成了，Ninja 基本上处于闲置状态，等待它执行的命令完成。在这种针对头文件依赖的新方法中，Ninja 使用这段时间来处理 gcc 在写入时发出的 Makefile，规范化路径并将依赖关系处理成一种可以快速反序列化的二进制格式。在下一次构建中，Ninja 只需要加载这个文件。其影响是巨大的，特别是在 Windows 上。（这将在本章后面进一步讨论。）

“依赖日志”需要存储数千条路径以及这些路径之间的依赖关系。加载此日志并向其添加内容必须很快。即使在出现中断（例如取消构建）的情况下，追加到此日志也应该是安全的。

在考虑了许多类似数据库的方法之后，我最终想出一个简单的实现：该文件是一个记录序列，每个记录要么是一个路径，要么是一个依赖列表。写入文件的每个路径都分配了一个连续的整数标识符。然后，依赖关系是整数列表。要向文件添加依赖关系，Ninja 首先为每个还没有标识符的路径写入新的记录，然后使用这些标识符写入依赖关系记录。在随后的运行中加载文件时，Ninja 就可以使用一个简单的数组来将标识符映射到它们的 Node 指针。

执行构建

从性能方面来看，根据上面讨论的依赖关系来执行判断为必要的命令的过程相对来说并不有趣，因为需要完成的大部分工作都在这些命令中完成（即在编译器、链接器等中完成），而不是在 Ninja 本身中完成。¹⁰

默认情况下，Ninja 会根据系统上可用的 CPU 数量并行运行构建命令。由于同时运行的命令可能会使它们的输出交织在一起，因此 Ninja 会将来自一个命令的所有输出缓冲起来，直到该命令完成，然后再打印其输出。最终的输出看起来就像命令是串行运行的一样。¹¹

这种对命令输出的控制使 Ninja 能够仔细控制其总输出。在构建过程中，Ninja 在运行时显示一行状态；如果构建成功完成，Ninja 的总打印输出将是一行。¹² 这不会让 Ninja 运行得更快，但它会让 Ninja 感觉很快，这与真正的速度一样重要，几乎与最初的目标一样重要。

支持 Windows

我为 Linux 编写了 Ninja。Nico（前面提到过）做了让它在 Mac OS X 上运行的工作。随着 Ninja 的越来越广泛使用，人们开始询问 Windows 支持。

从表面上看，支持 Windows 并不难。有一些简单的更改，比如将路径分隔符更改为反斜杠，或者更改 Ninja 语法以允许路径中包含冒号（例如 c:\foo.txt）。一旦这些更改到位，更大的问题就浮出水面了。Ninja 是根据 Linux 的行为假设设计的；Windows 在一些细微但重要的方面与之不同。

例如，Windows 对命令长度有相对较低的限制，这在构建传递给最终链接步骤的命令时会遇到问题，因为该命令可能包含项目中的大部分文件。Windows 对此的解决方案是“响应”文件，只有 Ninja（而不是 Ninja 前面的生成器程序）能够管理这些文件。

一个更重要的性能问题是，Windows 上的文件操作速度很慢，而 Ninja 处理了大量文件。Visual Studio 的编译器通过在编译时简单地打印它们来发出头文件依赖关系，因此 Windows 上的 Ninja 目前包含一个工具来包装编译器，使其生成 Ninja 所需的 gcc 风格的 Makefile 依赖关系列表。这种大量的文件在 Linux 上已经是瓶颈了，在 Windows 上更糟糕，因为打开文件要昂贵得多。前面提到的在构建时解析依赖关系的新方法非常适合 Windows，使我们能够完全删除中间工具：Ninja 已经缓冲了命令的输出，因此它可以直接从该缓冲区解析依赖关系，从而绕过了与 gcc 一起使用的中间磁盘上的 Makefile。

获取文件的修改时间 - Windows 上的 `GetFileAttributesEx()`¹³ 和非 Windows 平台上的 `stat()` - 在 Windows 上似乎比在 Linux 上慢 100 倍。¹⁴
这可能是由于“不公平”因素造成的，例如防病毒软件，但在实践中，这些因素确实存在于最终用户系统中，因此 Ninja 的性能会下降。Git 版本控制系统也需要获取许多文件的状态，它可以在 Windows 上使用多个线程并行执行文件检查。Ninja 应该采用此功能。

结论和替代设计

邮件列表中偶尔会有人建议 Ninja 应该作为一个内存驻留守护进程或服务器工作，尤其是与文件修改监控器（例如 Linux 上的 `inotify`）结合使用。如果 Ninja 只是在构建之间一直存在，那么所有这些关于加载数据所需时间和写回数据所需时间的担忧都不会成为问题。

事实上，这最初是我的 Ninja 设计方案。只有在我看到第一个构建快速完成时，我才意识到可能可以在不需要服务器组件的情况下让 Ninja 工作。随着 Chrome 的不断发展，这可能仍然是必要的，但我总是更倾向于简单的方法，我们通过减少工作量而不是更复杂的机制来提高速度。我希望其他一些重构（比如我们对使用词法分析器生成器或 Windows 上的新的依赖关系格式所做的更改）就足够了。

简单是软件的优点；问题在于它能走多远。Ninja 通过将某些昂贵的任务委托给其他工具（GYP 或 CMake）来减少构建系统的大部分复杂性，因此它在除创建它的项目之外的其他项目中也很有用。Ninja 的简单代码有望鼓励贡献 - 为支持 OS X、Windows、CMake 和其他功能所做的绝大部分工作都是由贡献者完成的。Ninja 的简单语义导致其他人尝试用其他语言（据我所知，Scheme 和 Go）重新实现它。

毫秒真的重要吗？在软件中更大的关注点中，可能担心毫秒是愚蠢的。但是，在处理过构建速度较慢的项目后，我发现我得到的不仅仅是生产力的提高；快速的周转让项目有一种轻盈感，这让我乐于使用它。而让我写软件的原因，就是因为它代码有趣，可以随意修改。从这个意义上说，速度至关重要。

致谢

要特别感谢 Ninja 的众多贡献者，你可以在 Ninja 的 GitHub 项目页面 上找到其中一些人的名字。