CTTI是指数级的，RTTI是线性的

# 编译时类型信息呈指数级增长，运行时类型信息呈线性增长 来源: https://www.gingerbill.org/article/2026/09/02/ctti-is-exponential-rtti-is-linear/ 2026\-09\-02 ## 摘要 运行时类型信息（RTTI）存在成本，但与被标榜为“零成本”实则并非如此的编译时类型信息（CTTI）相比，其成本是*可控*的。 - RTTI的表格规模相对于类型数量（N个类型 -> N个条目）呈***线性***成本，是单一成本。 - RTTI的使用成本是***固定常量***成本，即遍历一个表格的单个过程，无论存在多少类型。 - 在语义检查阶段，RTTI实际上***零***额外成本，因为无需特化处理。 - CTTI不一定需要额外的表格，但在某些情况下通常会生成它们。 - 在最坏情况下，CTTI在各方面（语义检查、代码生成以及二进制大小）都是***指数级***成本。在一般情况下，实例化会呈乘法增长。 人们在权衡线性内存成本（可测量）与指数级编译时间成本（无法测量）之间的取舍时，往往倾向于后者，并将其宣传为“零成本”。 --- ## 引言 我常收到的一个问题是，为何Odin使用运行时类型信息（RTTI）而非编译时类型信息（CTTI）来处理格式化打印之类的事情。这难道不是额外的运行时成本吗？而CTTI相关的一切不都是“零成本”的吗？难道不应该把所有计算都在编译时完成，以便编译器能针对这些类型集合进行优化吗？ “在编译时已知”和“在编译时可免费枚举”之间存在细微差别，混淆二者是一种范畴错误。这种理解上的缺失源于只对单个事物（一个实例）进行局部推理，而从未考虑整体或此类系统的涌现属性。 在本文中，我将尝试解释两者的真实成本，因为似乎很少有人能将其清晰勾勒出来。 ## RTTI 的成本 RTTI通常存储在表格中，Odin也不例外。程序中的每种类型（注意这里的“每种类型”仅指那些信息被保留并用于RTTI目的的类型，而非语言中所有可表达的类型，甚至不是程序中所有已表达的类型）都将存储在该表中。RTTI表格存储关于这些类型的一些信息，例如其大小、对齐方式、种类、字段，以及语言/语言设计者认为值得保留的任何信息。集合是有限且已知的，因为归根结底，类型只是*数据*。 RTTI的代价分散在几个方面：处理RTTI的过程、表格以及语义检查。 当你使用 `fmt.println` 打印一个值，或对任何东西进行（反）序列化时，你实际上在调用*一个*（或一组）过程，该过程遍历类型表中引用的类型。该过程的代码量不会因为你程序中有更多类型而增长，链接器也不需要为每种类型复制它，也不会为传入它的每种新类型组合产生更多*代码*。它始终是相同的代码在读取类型表中的类型信息。 处理这些运行时类型信息的*代码*其大小和形态将保持不变，因为唯一增长的是它所读取的类型表本身（如前所述，它是线性增长的）。 类型表的复杂度是线性的：`N` 种类型对应 `N` 个条目。通常（并且希望如此），此类型表驻留在只读数据段中（例如 Odin 中的 `@(rodata)`），因此该表的代价在编译时一次支付，体现在二进制文件和执行程序的内存中。你可以直接查看二进制文件，看到该表在二进制文件中占用了多少字节。所有这些都是可以轻松测量的，这正是为什么许多声称不喜欢RTTI的人可以给你一个具体数字，因为其成本足够简单明了，可以被量化（对于CTTI则不能轻易做到，我稍后会谈到）。 当你拥有RTTI时，语义上没有额外需要“检查”的东西。检查器只检查一个过程，该过程的参数类型为 `any`（或你的语言中实际使用的擦除句柄类型），然后它会*一次性*进行类型检查，并声明其已被使用。它不需要对每种类型重新检查，因为这种情况下没有每种类型的特定代码。 ### RTTI 的扩展复杂度 RTTI在表格大小上是线性的，在生成/编写的代码量上是常量的，在语义检查情况下是“零”的。 $$ \mathcal{O}(\text{表} \cdot \text{代码} + \text{检查}) = \mathcal{O}(N \cdot 1 + 0) = \mathcal{O}(N) $$ 因此，即使在最坏情况下，RTTI也是线性扩展的，其成本（显然）纯粹是运行时成本，体现在表间接寻址、序列化过程的代码大小，以及缺乏对特定类型代码的特定优化。 ## CTTI 的成本 使用CTTI的全部意义在于它允许你在使用它的每处地方特化*代码*。你对每种*不同*类型执行操作（例如打印）都会生成该操作的独立版本。对于一小类类型来说，这完全没问题，甚至很好。这是一小组编译器和优化器可以处理的代码；几乎没有间接寻址，也没有需要遍历的表格（CTTI*不一定*需要额外的表格，但在实践中出于实际原因它通常还是会生成一些）。 如果你确实只有一小类类型，CTTI可以是一个很好的工具。然而，即使在严重依赖类型安全格式化打印的小型程序中，这种“小类”的情况在实践中也永远不会成立，它会很快变得庞大。因此，如今任何对CTTI的使用都伴随着你在每处支付的成本，而且它呈指数级增长。 当你在关键工作负载中使用CTTI时，它从来不只是一个小类型集合，它总是一个类型的*组合*，而这些组合学确实会爆炸式增长。让我们以`N`种类型的基础打印器，或将`N`种类型序列化为`K`种格式的序列化器，或者一个由`K`个不同类型参数参数化多态的容器类型为例。一旦这些示例在类型参数上是任何形式的多元（多值/类型参数，多个返回值，多个字段），语言中就会充满这种组合爆炸发生的地方。 这意味着实例化的数量不仅仅是`N`，而是变成了`N×K`，或`N^k`。你没有编写`Nk`个过程，但编译器为你单态化了它们，哎呀。并且因为每个实例化都是一个*独立*的东西，它必须每次单独进行语义检查（假设是C++/Odin风格的参数化多态），然后代码也必须每次单独生成。这两者在编译阶段都是昂贵的方面，而这两者都变成了指数级增长。你可能省掉了一个“表”（包括存储和访问），但你在编译器内部和最终二进制文件中为此支付了`Nk`倍的代价。 不幸的是，这些正是许多程序员最习惯/被训练去忽略的成本，因为他们被告知，如果编译器能做某事，那就让它去做，而不是质疑它是否应该做。当有一天构建需要6分钟（而不是600毫秒），而二进制文件现在有400MiB大时，没有人能指出导致这种疯狂膨胀的具体代码行。它不可能是某一行特定代码造成的，因为它是代码本身组合学的结果。 ### CTTI 的扩展复杂度 计算CTTI的扩展复杂度稍微复杂一些，但仍然可以做到。 $$ N = \text{类型的数量} $$ $$ K = \text{传递给一个过程的类型组合} $$ 在`K=0`的情况下，该过程的实例数量为`1`。在`K=1`的情况下，该过程的最大实例数量为`N`。在`K=2`的情况下，该过程的最大实例数量为`N^2`。以此类推，这可以推广到`N`种类型的任意组合量： $$ \sum_{i=0}^{K} N^i = \frac{N^{K+1} - 1}{N-1} \implies \mathcal{O}(N^K) $$ 因此，即使在最常见的打印过程情况下，这也随着实例化呈指数级扩展。一些语言只是采用这种朴素的打印方法，并认为它不会成为问题。他们甚至说“嗯，每个输入只有一个实例化”，但随后忘记了内部结构现在变成了组合学。因此，在最佳情况下，这种方法是`N×K`，但在最坏情况下是`Nk`（根据你的理解方式，这要么是幂律（`K`为常量）要么是指数（`N`为常量），但实际上因为`N`并非真正“固定”，我认为它是指数级的。无论如何，它比线性差得多。）。一些确实使用CTTI进行打印的语言（例如 Rust）试图通过编译器中一个显式的边缘情况来缓解这种灾难，该情况试图最小化编译器复杂性中的这种爆炸，但它不一定能解决中大型项目中的二进制文件问题。 一些语言也尝试通过显式标记来缓解组合爆炸，以生成CTTI相关的代码，强制产生乘法复杂度。例如，Rust中的 `serde` (https://serde.rs/) 可用于CLI参数、GUI表单、漂亮打印等。所有这些我都在Odin中使用RTTI和结构体字段标签（https://odin-lang.org/docs/overview/#struct-field-tags）来实现，我觉得这更容易处理。 ## 不对称的方法 - RTTI的最坏情况是**线性的，在一个地方**，而且它是你可以实际测量的地方（内存）。 - CTTI的最坏情况是**指数级的，在三个地方同时发生**（语义检查、代码生成和二进制大小）。 在我看来，就成本而言，这根本不是一个接近的选择；当我在2016年开始创建Odin时，我毫不犹豫地直接选择了RTTI。人们似乎用一个他们可以看到的线性内存成本（如果它成为问题，他们可以解决）来交换一个他们看不到的指数级编译时间成本。而所有这一切只是因为他们看不到第二个成本，他们说服自己称之为“零成本抽象”。我真的非常不喜欢“零成本”这个短语，因为它几乎总是隐藏了巨大的代价。 ## 再论个体元素思维 我曾写过关于*个体元素思维*（https://www.gingerbill.org/article/2026/01/02/was-it-really-a-billion-dollar-mistake/）的文章：习惯于孤立地思考一个事物，而从不考虑群体。语言设计中条件反射式地使用CTTI，正是戴着类型理论帽子（https://en.wikipedia.org/wiki/Mr_Benn）的这种思维。 我在Odin中选择RTTI，因为它是一种数据驱动的方法（一个过程处理一个表格）。CTTI方法则是一种非常代码驱动的方法，它可能为每个过程实例化产生更好的*代码*，但代价是假装你不想让数据存在。 ## 一致性优于巧妙性 除了成本论点之外，还有一个架构设计论点，这也是我在Odin中选择RTTI的一个重要原因。 在Odin中，`fmt.println` 通过RTTI处理所有内容。任何形式的（反）序列化/（编）解组都使用RTTI。 Odin中RTTI的一个美妙之处在于`typeid`是确定性的——无论程序如何，每种类型都将具有相同的typeid（假设类型相同）。当一个typeid跨越LIB/DLL边界时（无需重新实例化任何东西），它“可以”跨边界工作，因为它只是*数据*，具有稳定的规范布局；没有Nk个生成的程序需要双方同意以完全相同的方式生成，单态化代码不会自动跨越动态库边界。使用CTTI时，双方必须产生相同的实例化，或者*你*重新生成它们。数据在这样的边界上移动绝对没问题。 这个设计论点实际上是关于一致性与[每种类型的]巧妙性。它是一个可以被统一应用的单一理念，每个人都可以理解并在此基础上构建。而不是N个不同的生成物让编译器在检查所有这些时苦苦挣扎。 而CTTI给了你什么回报呢？ - 随时间推移会变得*转移性*（https://en.wikipedia.org/wiki/Metastasis）的参数化多态/模板 - 错误信息长达数KB，且需要埃及学学位才能解读 - 指数级扩展的构建时间，让你有时间烤一份完整的周日烤肉 - 二进制文件充斥着近乎相同的过程，链接器现在必须去重（但实际上做不到） 让我发笑的是，依赖链接器去重这一点恰恰承认了问题所在。你他妈已经生成了所有这些，检查了所有这些，然后才要求另一个工具花时间扔掉大部分……我创建Odin的一个重要原因就是要远离那种做“无用功”的疯狂。 ## 权衡取舍是存在的 需要明确的是，有些情况下CTTI是更好的权衡。Odino确实通过其 `base:intrinsics` 具有一种形式的CTTI，尽管使用起来有些笨拙（这部分是为了有意引导人们最小化其使用，但也因为它没有相同的数据驱动设计，纯粹是通过编译时求值过程/内置函数派生的）。 - 当你有一个热路径，无法负担间接寻址或遍历类型表的成本时。 - 当你希望优化器实际上针对特定类型优化代码本身，而不是使用通用代码时。 - 当你确实有一个小型的已知类型集合，且组合学从未导致任何问题爆发时。 在上述情况下，CTTI提供的特化是极好的，但我认为这些情况比你想象的要少。 当然，RTTI本身也有其成本： - 表格在二进制文件和执行内存中占用空间。 - 表格查找是运行时成本，即使它是“常量”的。 - 所有信息都必须保留，否则整个系统无法工作。 - 你可能需要出于隐私/安全考虑对某些类型信息进行混淆。 - 如果你处于一个无法节省字节或间接寻址的环境（这是一个真实的约束），那么就用RTTI。 我在这里的重点不是“CTTI不好，RTTI好”，而是我认为很多人没有意识到，在考虑检查、代码生成和二进制大小时，CTTI的成本在最坏情况下是指数级的，在一般情况下是乘法的。CTTI的好处几乎总是*局部的*，但却有*全局*影响。而在设计语言时，我认为应该默认使用RTTI，只在绝对需要时才使用CTTI。 ## 结论 RTTI在类型数量上具有***线性***成本，然后在运行时（表格查找/间接寻址）、二进制大小和内存使用中支付。CTTI在最坏情况下在类型数量上具有***指数级***成本，在一般情况下是乘法的，然后在编译时（检查和代码生成）和二进制大小中支付。