Rust中的泛型和编译时

在本系列中，我们将探讨Rust在TiKV上下文中的编译时间，TiKV是TiDB数据库背后的键值存储。

在本系列的上一篇文章中，我们介绍了Rust的早期开发历史，以及它如何导致了一系列决策，这些决策导致了一种编译速度很慢的高性能语言。在接下来的几个月里，我们将更详细地描述Rust中一些使编译时间变慢的设计。

在这一系列的前一集之后，人们在HackerNews，Reddit和Lobste.rs上发表了很多很棒的评论。

通常重要的是部分重建，因为这是开发人员在构建-测试周期中体验最多的。

WalterBright指出数据流分析(DFA)是昂贵的(二次)。铁锈依赖于数据流分析。我不知道铁锈是如何编译时间的，但了解它是件好事。

Kibwen提醒我们，更快的链接器对构建时间有影响，LLD最终可能比系统链接器更快。

在没有进一步澄清的情况下泛泛地谈论“编译时”是很诱人的，但“编译时”有很多种类型，有些对不同的人或多或少都很重要。Rust中的四个主要编译时场景是：

“开发配置文件”需要针对快速编译时间、缓慢运行时间和最大可调试性而设计的编译器设置。“版本配置文件”需要针对快速运行时间、缓慢编译时间以及通常最低可调试性而设计的编译器设置。在Rust中，它们分别与Cargo Build和Cargo Build--Release一起调用，并且表示编译时/运行时的权衡。

完全重新生成是从头开始生成整个项目，部分重新生成发生在修改以前生成的项目中的代码之后。部分重建可以明显受益于增量编译。

它们大多分别类似于开发模式和发布模式，尽管在Cargo中开发/测试和发布/工作台之间的交互可能是微妙和令人惊讶的。可能还有其他配置文件(TiKV有更多)，但这些都是铁锈的显而易见的配置文件，因为它们内置在货物中。除此之外，还有其他场景，比如仅检查类型(货物检查)、只构建单个项目(货物构建-p)、单核与多核、本地与分布式、本地与CI。

编译时间也会受到人类感知的影响--编译时间可能会在它实际上很不错的时候感觉不好，而在它实际上不是很好的时候感觉很好。这是RUST语言服务器(RLS)和RUST分析器背后的前提之一--如果开发人员在他们的IDE中得到持续的、实时的反馈，那么完全编译需要多长时间都无关紧要。

因此，在本系列中务必记住，从“快速编译/慢速运行”到“快速运行/慢速编译”，有一系列可调的可能性，不同的场景以不同的方式影响编译时间，其中编译时间以不同的方式影响感知。

碰巧的是，对于TiKV，我们已经发现，我们最关心的编译时间场景是“发布配置文件/部分重建”(Release Profile/Partial Rebuild)。在未来的分期付款中会有更多关于这方面的信息。

这篇文章的其余部分详细介绍了Rust中导致编译时间缓慢的一些主要设计。我将它们描述为“权衡”，因为有很好的理由Rust是这样的，而语言设计充满了尴尬的权衡。

Rust处理泛型的方法是编译时间不佳最明显的语言特性，理解Rust如何将泛型函数转换为机器码对于理解Rust编译时/运行时的权衡非常重要。

泛型通常是一个复杂的主题，而锈型泛型有多种形式。Ruust具有泛型函数和泛型类型，它们可以用多种方式表示。在这里，我将主要讨论Rust如何调用泛型函数，但是对于泛型类型转换，还有更多的编译时注意事项。我忽略其他形式的泛型(比如Iml Character)，因为它们要么有类似的编译时影响，要么我就是对它们了解不够。

作为本节的一个简单示例，请考虑以下ToString特征和泛型函数print：

Print会将任何可以转换为字符串类型的内容打印到控制台。我们说“print是类型T的泛型，其中T实现了Stringify”。因此，我可以使用不同的类型调用print：

编译器将这些打印调用转换为机器码的方式对语言的编译时和运行时特征都有很大影响。

当使用一组特定的类型参数调用泛型函数时，称为使用这些类型实例化。

翻译每组实例化类型参数的泛型函数，直接调用每个特征方法，但复制泛型函数的大部分机器指令，或者。

只转换泛型函数一次，通过函数指针(通过“vtable”)调用每个特征方法。

第一个结果是静态方法分派，第二个结果是动态(或“虚拟”)方法分派。第一种有时称为“单形化”，特别是在C++和Rust的上下文中，这是一个表示简单概念的令人困惑的复杂单词。

前面的示例使用Rust'；的类型参数(<；T：ToString>；)来定义静态分派的打印函数。在本节中，我们将提供另外两个Rust示例，第一个使用静态分派，使用对impl traitinstance的引用，第二个使用动态分派，使用对dyn traitinstance的引用。

请注意，这两种情况之间唯一的区别是，第一个print'；的参数是&；impl ToString类型，第二个参数是&；dyn ToString类型。第一种是使用静态调度，第二种是动态调度。

在Rust&；Iml ToString中，ToString实质上是只使用一次的类型参数参数的简写，如前面的示例FN print<；T：ToString>；(v：t)。

请注意，在这些示例中，我们必须使用内联(从不)来击败优化器。如果没有这一点，它将把这些简单的示例变成完全相同的机器代码。我将在本系列的下一集进一步探讨这一现象。

下面是这两个示例的程序集的一个极其简化和净化的版本。如果您想看真实的东西，上面的游戏链接可以通过单击标记为.->；ASM的按钮来生成它们。

打印：：hffa7359fe88f0de2：.。callq*：：core：：fmt：：write：：h01edf6dd68a42c9c(%rip).打印：：ha0649f845bb59b0c：.。callq*：：core：：fmt：：write：：h01edf6dd68a42c9c(%rip).main：：h6b41e7a408fe6876：.。呼叫打印：：hffa7359fe88f0de2.。呼叫打印：：ha0649f845bb59b0c。

这里需要注意的重要一点是功能的重复或缺失，这取决于策略。在静态情况下，有两个打印函数，通过其名称中的散列值来区分，并且main调用这两个函数。在动态情况下，只有一个主要调用两次的打印函数。这两种策略实际上是如何在机器层面处理它们的论点的细节太复杂了，在这里不再赘述。

这两种策略代表了出了名的困难权衡：第一种策略创建了大量的机器指令复制，迫使编译器花费时间生成这些指令，并给指令缓存带来压力，但最重要的是，静态地而不是通过函数指针来分派所有的特征方法调用。第二种方法节省了大量机器指令，编译器转换为机器代码所需的工作较少，但是每个特征方法调用都是通过函数指针进行的间接调用，这通常比较慢，因为CPU在加载指针之前无法知道它将跳转到什么指令。

人们通常认为静态分派策略会导致机器代码更快，尽管我还没有看到任何关于这一问题的研究(我们将在本系列的未来版本中对此主题进行实验)。直观地说，这是有意义的-如果CPU知道它正在调用的所有函数的地址，它应该能够更快地调用它们，而不是必须先加载函数的地址，然后将指令代码加载到指令高速缓存中。然而，有一些因素让人怀疑这一直觉：

首先，现代CPU在分支预测上投入了大量的硅片，因此如果最近调用了函数指针，那么它很可能在下一次被正确预测并被快速调用；

其次，单词化导致了大量的机器指令，这一现象通常被称为“代码膨胀”，这可能会给CPU的指令高速缓存带来很大的压力；

第三，LLVM优化器出人意料地智能，并且在代码中具有足够的可见性，有时可以将虚拟调用转换为静态调用。

C++和Rust都强烈鼓励单形化，都会生成任何编程语言中速度最快的机器代码，而且都有代码膨胀的问题。这似乎证明了单一化策略确实是两种策略中速度较快的一种。但是有一个奇怪的反例：C.C完全没有泛型，而且C程序通常是他们类中最薄、最快的。用C语言重现单态化策略需要使用丑陋的C宏预处理器技术，而现代的C语言面向对象模式通常是基于vtable的。

摘要：编译器工程师普遍认为，单形化会导致泛型代码稍微快一些，而编译时间却会稍微长一些。

请注意，单形化编译时问题在Rust中是复合的，因为Rust在每个实例化泛型函数的机箱(通常称为“编译单元”)中转换泛型函数。这意味着，在我们的打印示例中，如果crate a调用print("；hello，world&34；)，而crate b也调用print("；hello，world，或其他"；)，那么crate a和b都将包含单元化的print_str函数-编译器将两次执行所有的类型检查和转换工作。如今，共享泛型在较低的优化级别部分缓解了这一问题，尽管在兄弟依赖关系和较高的优化级别中仍然存在重复的泛型。

所有这些只涉及到单形化所涉及的权衡的表面。我通过了尼克的这个草稿，他是“铁锈”背后的主要类型理论家，他对此有几句话要说：

妮可：到目前为止，一切看起来都相当准确，除了我认为单词化区域省略了很多复杂性。这绝对不只是关于虚拟函数调用。

妮可：也是像foo.bar这样的东西，bar的偏移量取决于foo的类型。

Niko：很多语言通过在任何地方都使用指针来避开这个问题(如果你不使用宏，包括泛型C语言)。

Niko：更不用说像迭代器这样的复杂类型的构造，它们基本上是完全实例化的小程序，然后是可定制的-尽管这可以由足够智能的编译器重现。

妮可：(特别是，虚拟调用也可以内联，尽管优化程度较低；我记得在当时的…中曾讨论过这一点。虚拟呼叫内联在管道中发生的时间相对较晚)。

Niko：我记得，在转向单形化之前，我们必须有两条路径来处理所有事情：一条是简单的静态路径，其中所有类型都是LLVM已知的；另一条是可怕的动态路径，在这条路径中，我们必须生成代码来动态计算字段和事物的偏移量。

妮可：我认为今天可以更好地处理很多问题-例如，我们有相当可靠的代码来计算布局，我们有MIR，这是一个简单得多的目标-所以我不会那么害怕不得不拥有这两条路径。

Niko：还有一些东西，比如需要动态合成类型描述符(尽管也许我们总是可以通过堆栈分配来满足这一要求)。

Niko：这里，您有一个动态提供给您的T的类型描述符，但是您必须构建VEC的类型描述符

妮可：因为我们必须能搞清楚VEC<；T&>；：DEBUG，而我们只知道T：DEBUG。

妮可：我们也许可以通过向我们的呼叫者…打开VEC来处理这个问题。

在本系列的下一集中，我们将讨论编译单元-编译器一次处理的代码束-以及选择编译单元如何影响编译时间。

很多人为这个博客系列提供了帮助。特别感谢Niko Matsakis的反馈，以及Calvin Weng的校对和编辑。