使用 clang-cl 和 lld 提高 Windows 上的链接时间

将 clang 和 lld 带到 Windows 上的目标之一始终是改善开发人员体验，而开发人员最想要什么？更快的构建时间！最近，我们的重点是改善链接时间，因为它是最难并行化的步骤，因此我们无法依靠将更多核心投入其中的悠久传统。

在链接涉及的各种步骤中，生成调试信息（在 Windows 上是 PDB 文件）是迄今为止最慢的步骤，因为它涉及合并 O（链接器输入数量）个类型记录序列，其中大部分是重复的。例如，如果两个 cpp 文件都包含 <string>，则这两个目标文件将包含数百个需要在链接步骤中去重的重复类型记录。这意味着您必须计算 O(M x N) 个哈希值，即使只有其中一小部分最终会贡献到最终的 PDB。

多年来，已经发明了几种策略来处理这个问题并尝试使链接更快。很多年前，微软引入了类型服务器的概念（通过在 MSVC 中使用/Zi编译器选项启用），它将部分工作转移到编译器中（以利用并行性）。最近，我们得到了/DEBUG:FASTLINK链接器选项，它试图通过在链接器中完全不合并类型来解决这个问题。但是，每种策略都有其自身的缺点，并且对于所有用例来说，都不能算作完美。

在这篇博文中，我们将首先介绍一些关于 CodeView 的技术背景，以便我们可以理解这个问题，然后总结现有的加速类型合并的尝试。然后，我们将描述对 PE/COFF 文件格式的一种新扩展，它通过将部分去重类型所需的工作卸载到编译器并将使用一种新的算法来加速链接，该算法即使在输入文件之间也能唯一识别类型记录，并讨论各种权衡取舍。最后，我们将展示一些基准测试，并讨论您今天如何在 clang-cl 和 lld 中试用它。

背景

考虑一个简单的 C++ 结构，在头文件中定义如下

struct Node {

Node *Next = nullptr;

Node *Prev = nullptr;

int Value = 0;

};

由于每次编译都独立于其他每次编译，因此编译器无法假设任何其他翻译单元将来会发出描述此类型的记录。因此，为了保证该类型进入最终的 PDB，每个编译器实例都必须为该类型发出类型信息。因此，该记录将被编译器序列化为一系列看起来大致如下的记录

0x1004 | LF_STRUCTURE [size = 40] `Node`

唯一名称：`.?AUNode@@`

vtable：<none>

基类列表：<none>

字段列表：<none>

选项：前向引用 | 具有唯一名称

0x1005 | LF_POINTER [size = 12]

referent = 0x1004

模式 = 指针

opts = 无

种类 = ptr32

0x1006 | LF_FIELDLIST [size = 52]

- LF_MEMBER

名称 = `Next`

类型 = 0x1005

偏移量 = 0

属性 = 公共

- LF_MEMBER

名称 = `Prev`

类型 = 0x1005

偏移量 = 4

属性 = 公共

- LF_MEMBER

名称 = `Value`

类型 = 0x0074 (int)

偏移量 = 8

属性 = 公共

0x1007 | LF_STRUCTURE [size = 40] `Node`

唯一名称：`.?AUNode@@`

vtable：<none>

基类列表：<none>

字段列表：0x1006

选项：具有唯一名称

左边的值对应于类型序列中的索引，并且取决于已经遇到的类型，而其他类型可以参考它们（例如，referent = 0x1004）意味着该记录是指向索引为 0x1004 的类型的指针。

因此，包含相同头文件的另一个编译单元将需要发出完全相同的类型，唯一的区别是索引（因为另一个编译单元可能在该类型之前遇到其他类型，导致排序不同）。

简而言之，类型索引仅在单个类型序列（即编译单元）的上下文中才有意义，但由于链接器需要查看所有目标文件，因此它必须有一种方法来识别目标文件 A 中的类型是否与目标文件 B 中的不同类型同构，即使其类型索引在数值上可能与以前见过的任何类型不同。

该算法，以下简称类型合并，是链接期间 CPU 周期的主要消耗者（在 LLD 中测量，并在 MSVC 链接器中通过比较 /DEBUG:FULL 和 /DEBUG:FASTLINK 时间估计），因此它是本博文提出了一种新解决方案的链接过程的部分。

现有解决方案

值得讨论一些减少与类型合并相关的成本的现有尝试，以便我们可以比较和对比它们各自的优缺点。

类型服务器 (/Zi)

/Zi 编译器选项是解决类型合并速度问题的首次尝试之一，它可以追溯到很多年前。类型服务器背后的理念是从链接阶段将去重的任务卸载到编译阶段。大多数构建系统已经支持并行编译，即使它们没有，cl.exe也通过 /MP 编译器开关原生支持它，因此对于任何人来说，利用并行编译都没有障碍。

为了实现类型服务器，每个编译进程都通过 IPC 与单个进程（mspdbsrv.exe）通信，该进程的工作是实时去重类型记录，当记录与现有记录同构时，类型服务器会将以前保存的索引传回，当它是新的时，它会传回一个新的索引。这允许类型去重大部分并行发生，但增加了每个编译的一些开销（因为存在对全局锁的争用），以换取显着减少的链接时间，因为类型将已经合并。

但是，类型服务器也带来了一些缺点，因此我们将在此列出它们。

类型服务器向编译阶段添加了大量的上下文切换和全局锁争用，降低了并行性并降低了构建过程中的整体系统性能。虽然从链接器中恢复了一些性能，但由于使用了全局系统锁，因此也牺牲了一些性能。它仍然是一个净收益，但它不是免费的，因此它留下了我们可以使用其他方法实现更好的并行性的可能性。
类型服务器进程本身（mspdbsrv.exe）引入了单点故障。当它崩溃时（例如，我们在 Chrome 上每天看到几次 C1033，这似乎表明 mspdbsrv.exe 崩溃），如果类型服务器 PDB 文件处于损坏状态，它可能会触发完全重建。
mspdbsrv与分布式构建不兼容，这对在普通工作站上需要几个小时才能构建的大型应用程序来说是一个障碍。类型服务器仅通过本地 IPC 运行。虽然多处理对于小型应用程序来说效果很好，但许多大型产品都有构建场，它们在数十或数百台物理机器之间分配编译任务。类型服务器与这种情况不兼容。

快速链接 PDB

快速链接 PDB 是一个相对较新的引入，该解决方案使用的方法是完全消除类型合并。为了支持这一点，PDB 文件中设置了特殊的元数据来指示工具这是一个快速链接 PDB，当工具（例如调试器）遇到此元数据时，它将从原始目标文件而不是从 PDB 中获取所有类型信息。同样，这种方法也有一些缺点，列举如下

对于性能原因，pdbcopy 实用程序在使用快速链接 PDB 时几乎不可用。
由于没有发生类型合并，因此类型信息的索引也不会发生（因为构建索引的昂贵部分——哈希——在您对记录进行哈希时就免费获得了）。这会导致调试器用户体验下降，因为以前只发生在构建时的等待现在发生在调试时。
快速链接 PDB 不可移植。 PDB 通过路径引用目标文件，因此如果您将 PDB 和目标文件复制到不同的机器（甚至在同一机器上的不同路径）以供归档，它们就无法再进行调试。对于在生产构建中使用它来说，这是一个障碍。
无法在快速链接 PDB 中枚举符号。如果你尝试在快速链接 PDB 上使用 DIA SDK，这一点最为明显，它只会拒绝执行任何操作。这意味着对于用户来说，唯一外部支持的查询调试信息的途径是不可能针对快速链接 PDB 完成的。此外，这也意味着即使微软自己的需要枚举符号的工具也不能使用任何标准 API 来执行此操作。例如，WinDbg 不完全支持快速链接 PDB，即使使用支持的微软工具，许多工作流程也会因使用它们而中断。
它有几个严重的稳定性问题，使其在大型项目上不可用 [参考]。这可能与上面的第 4 点有关，即每个想要能够处理快速链接 PDB 的工具都需要使用与经过测试和经过多年开发的 SDK 不同的代码。
当使用 clang-cl 编译并使用 /debug:fastlink 链接时，必须指示编译器发出额外的调试信息，使 .obj 文件大小增加约 29%。

Clang 的解决方案 - COFF .debug$H 节

这种新方法试图将类型服务器和 fastlink PDB 背后的理念结合起来。与类型服务器一样，它试图将重复数据删除的工作卸载到编译阶段，以便可以并行完成。但是，它使用一种算法来完成此操作，该算法的特性是生成的哈希值可以用于识别类型记录，即使它们来自不同的类型流。具体来说，**如果两个记录具有相同的哈希值，即使它们来自不同的目标文件，它们也是相同的记录。**如果你可以相信这种算法的存在（我们将在以后称之为 _全局哈希_），那么链接器需要执行的工作量将大大减少。它需要执行的仍然可以更快地完成。也许最重要的是，_它会生成与未使用该选项时完全相同的字节 PDB_，这意味着与 Fastlink PDB 和兼容性相关的所有问题都消失了。

以前，链接器会执行类似于以下内容的操作

HashTable<Type> HashedTypes;

vector<Type> MergedTypes;

for (ObjectFile &Obj : Objects) {

for (Type &T : Obj.types()) {

remapAllTypeIndices(MergedTypes, T);

if (!HashedTypes.try_insert(T))

continue;

MergedTypes.push_back(T);

}

这里重要的观察结果是

remapAllTypeIndices 对每个目标文件中的每个类型都被无条件地调用。
对每个类型的类型都无条件地计算哈希值
至少一次对每个类型进行完整的记录比较。实际上，它会更多，因为哈希桶是按表大小取模计算的，因此实际上每个探测都会进行 1 次完整的记录比较。

给定上述全局哈希函数，该算法可以像这样重写：

HashMap<SHA1, int> HashToIndex;

vector<Type> OrderedTypes;

for (ObjectFile &Obj : Objects) {

auto Hashes = Obj.DebugHSectionHashes;

for (int I=0; I < Obj.NumTypes; ++I) {

int NextIndex = OrderedTypes.size();

if (!HashToIndex.try_emplace(Hashes[I], NextIndex))

continue;

remapAllTypeIndices(T);

OrderedTypes.push_back(T);

}

虽然这看起来非常相似，但它的性能特征却截然不同。

remapAllTypeIndices 仅在记录实际上是新的时才调用。正如我们之前讨论的那样，在许多链接器输入中，这只是一小部分时间。
链接器从不计算类型的哈希值。它只是存在于目标文件中（这方面的例外是混合链接器输入，如前所述，但它们只是输入文件的一小部分）。
从不进行完整的记录比较。由于我们使用的是具有极低虚假碰撞概率的强哈希函数，并且由于记录的哈希值在流之间提供相等语义，因此哈希值与记录本身一样好。

将所有这些点结合起来，我们得到了一种极其缓存友好的算法。在所有输入文件上进行摊销，类型合并期间大多数记录都是缓存命中（即重复记录）。使用此算法，当我们获得缓存命中时，仅访问的两个数据结构是

一个连续哈希值数组。
一个连续哈希桶数组。

由于我们从不进行完整的相等性比较（由于类型记录的平均大小大于缓存行，这会导致 L1 甚至有时会导致 L2 缓存爆炸），因此这里的算法非常快。

我们一直推迟讨论如何创建这样的哈希值，但实际上它相当简单。我们使用的是一种称为“树哈希”或“Merkle 树”的方法。这个想法是将类型记录中的字节直接传递给哈希函数，直到我们到达类型索引。然后，我们不是将类型索引的数值传递给哈希函数，而是传递被引用的记录的先前计算的哈希值。

这种哈希值在编译器中计算起来非常快，因为编译器必须无论如何都对类型进行哈希处理，因此将此信息输出到 .debug$H 部分的增量成本可以忽略不计。例如，当在翻译单元中遇到类型时，在你将该类型添加到目标文件的 .debug$T 部分之前，必须首先验证该类型尚未添加。并且由于这是按遇到类型顺序自然发生的，因此只需要将这些哈希值保存在按类型索引索引的数组中，后续的哈希操作将能够以 O(1) 的访问速度访问计算此 Merkle 哈希所需的所有信息。

混合输入文件和编译器/链接器兼容性

链接器必须准备好处理一组混合的输入文件。例如，虽然特定编译器可能选择始终发出 .debug$H 部分，但链接器必须准备好链接由于任何原因没有此部分的目标文件。为了处理这种情况，链接器可以预先检查所有输入，并手动为缺少 .debug$H 部分的输入计算哈希值。实际上，这被证明只是一小部分，并且串行执行此操作的惩罚可以忽略不计，尽管应该注意，理论上，如果某些用例表明这具有不可忽略的成本，也可以将其作为并行预处理步骤执行。

类似地，在目标文件中发出此部分不会影响未学习使用它的链接器。由于它是对目标文件的纯添加（和可选）包含，因此任何不理解它的链接器将继续像今天一样工作。

磁盘上的格式

Clang 使用以下磁盘上的格式来表示 .debug$H 部分。

0x0 : <Section Magic> (4 bytes)

0x4 : <Version> (2 bytes)

0x6 : <Hash Algorithm> (2 bytes)

0x8 : <Hash Value> (N bytes)

0x8 + N : <Hash Value> (N bytes)

…

这里，“Section Magic”是一个任意选择的 4 字节数字，其目的是提供一定程度的确定性，以确保我们看到的是一个真正的 .debug$H 部分，而不是有人创建的、碰巧具有该名称的某个部分。我们当前的实现使用值为 0x133C9C5，它表示初始原型实现的日期。但是，这可以是任何合理的值，只要它永远不会改变。

“Version”保留供将来使用，以便该部分的格式可以理论上发生变化。

“Hash Algorithm”是一个值，指示用于生成后续哈希值的算法。因此，上述 N 的值也是哈希算法使用情况的函数。目前，唯一建议的“Hash Algorithm”值是 SHA1 = 0，这意味着当“Hash Algorithm” = 0 时，N = 20。如果事实证明使用截断的 8 字节 SHA1 哈希值很有用，我们可以定义 SHA1_8 = 1，例如。

限制和陷阱

这种格式的最大限制是它会增加目标文件大小。在相当大的项目上进行的本地实验表明，与 /DEBUG:FULL 相比，目标文件的平均聚合大小增加了约 15%（对于 clang-cl，实际上会使 .debug$H 目标文件 _小于_ 支持 /DEBUG:FASTLINK 所需的目标文件）。

还存在另一个不太明显的潜在陷阱。最糟糕的情况是当没有输入文件包含 .debug$H 部分时，但即使只有一部分文件包含 .debug$H 部分，这种限制在原则上也是一样的。由于链接器必须对所有目标文件达成一个哈希函数，因此当并非所有目标文件都同意哈希函数时，或者当并非所有目标文件都包含 .debug$H 部分时，该如何处理是一个问题。如果代码没有仔细编写，你可能会遇到一种情况，例如，没有输入文件包含 .debug$H 部分，因此链接器决定为每个输入文件动态合成一个。由于 SHA1（例如）非常慢，这会导致巨大的性能损失。

但是，可以通过一些小心处理来解决此限制。例如，可以预先并行计算树哈希作为预处理步骤。或者，可以选择哈希函数，该函数基于对可能导致最快链接的启发式估计（例如，基于包含 .debug$H 部分的输入百分比）。还存在其他可能性。重要的是要意识到这种潜在的陷阱，如果你的链接变得非常慢，你就会知道首先要检查的是“我的所有目标文件是否都有 .debug$H 部分？”

最后，由于哈希值被认为与原始记录相同，我们必须考虑碰撞的可能性。也就是说，在实践中这似乎不是一个严重的问题。由于类型索引为 4 字节，因此单个 PDB 理论上最多可以包含 2³² 个类型记录。下表显示了作为哈希值大小函数，发生碰撞所需的预期类型记录数量。

哈希值大小（字节）	发生碰撞所需的平均记录数
4	82,137
6	21,027,121
8	5,382,943,231
12	3.53 x 10¹⁴
16	2.31 x 10¹⁹
20	1.52 x 10²⁴

鉴于这严格用于调试信息而不是生成的代码，值得考虑碰撞的_严重程度_。我们认为，对于实际使用，8 字节哈希值可能可以接受。

基准测试

本文将对一些大型真实应用（特别是 Chrome 和 clang）进行链接时间性能比较。展示的时间 **仅** 指链接器所花费的时间。每个 chromium 构建的 gn 参数将在最后列出。

工具链	模式	目标
工具链	模式	blink_core.dll	content.dll	chrome.dll	clang.exe
MSVC	/DEBUG:FULL	553.11 秒	205.45 秒	507.17 秒	62.45 秒
MSVC	/DEBUG:FASTLINK	116.77 秒	56.05 秒	67.80 秒	29.37 秒
lld-link	/DEBUG:FULL	121.17 秒	42.10 秒	42.31 秒	24.14 秒
lld-link	/DEBUG:GHASH	88.71 秒	33.30 秒	34.76 秒	17.99 秒

这些数字表明在 lld 中启用 /DEBUG:GHASH 可以将链接时间缩短高达 30%。

值得一提的是，lld 尚未支持增量链接，因此我们无法比较使用 /DEBUG:GHASH 的增量链接与 MSVC 的成本。我们预计在最佳条件下（例如，更改头文件中的空格）使用 MSVC 进行增量链接将比 lld 目前所能实现的快得多。

然而，还有几个可能的优化途径，我们将在后面进行讨论。

进一步改进

有几种方法可以进一步缩短时间，但尚未进行探索。

使用更小或更快的哈希算法。我们目前使用的是 20 字节的 SHA1 哈希。这不是缓存行大小的倍数，而且即使在最大的 PDB 中，考虑到 PDB 的理论限制略小于 2^32 个可能的唯一类型（由于类型索引的 4 字节大小），碰撞概率也极低。SHA1 也以其速度著称。尝试例如将 Blake2 设置为输出 8 字节哈希可能会很有趣。这应该可以提供足够低的碰撞概率，同时提高缓存性能。磁盘格式的设计考虑了这种灵活性，因为可以在头文件中指定不同的哈希算法。
对于缺少 .debug$H 部分的编译单元，可以在链接之前并行计算哈希值。目前，当我们遇到没有 .debug$H 部分的对象文件时，我们必须在链接器中合成一个。我们的原型算法对每个输入都串行执行此操作。
来自 .debug$S 部分的符号记录可以并行合并。目前在 lld 中，我们首先将类型记录合并到 TPI 流中，然后我们迭代符号记录并将每个符号记录中的类型重新映射以对应于新的类型索引。如果我们预先合并所有模块中的类型，则符号记录（除了全局符号）可以并行合并，因为它们会被写入到独立的流中。

试一试！

如果您现在已经在 Windows 上使用 clang-cl 和 lld，那么可以尝试一下。需要两个标志来启用此功能，一个用于编译器，一个用于链接器。

要启用编译器生成 .debug$H 部分，您需要将未公开的 -mllvm -emit-codeview-ghash-section 标志传递给 clang-cl（这个标志将在将来消失，一旦它被认为是稳定的并且足够好以至于默认情况下启用）。
要告诉 lld 使用这些信息，您需要将 /DEBUG:GHASH 传递给 lld。

请注意，此功能仍被认为是高度实验性的，因此我们希望收到您的反馈（llvm-dev@ 邮件列表，直接电子邮件也可以）和错误报告（bugs.llvm.org）。