内联启发式综述

# 内联启发式方法概述 来源：https://bernsteinbear.com/blog/inlining-heuristics/ 编译器，尤其是方法即时（JIT）编译器，每次只处理一个函数。这是自然的代码单元大小，特别是对于动态语言的 JIT：在某个时间点，你能收集到关于一个运行中、不断变化的系统的其他部分的什么信息？我没有数据支持这一点——也许我应该去收集一些——但平均而言，方法很小。尤其是在像 Ruby 这样几乎所有操作都使用方法派发的语言中，即使是实例变量（属性、字段等）查找也是如此——它们非常小。而且无处不在。这让编译器很沮丧。如果我们继续把它们拟人化，编译器喜欢拥有更多上下文以便更好地优化。考虑下面这个看起来有点愚蠢但实际上代表了大量真实世界代码的例子： ```ruby class Point attr_reader :x, :y def initialize(x, y) @x = x @y = y end def distance(other) Math.sqrt((@x - other.x)**2 + (@y - other.y)**2) end end def distance_from_origin(x, y) Point.new(x, y).distance(Point.new(0, 0)) end ``` 目前，在 `distance_from_origin` 方法中，我数出了 8 个不同的方法调用： - `Point.new` - `Point#initialize` - `Point.new` - `Point#initialize` - `Point#distance` - `Float#**` - `Float#**` - `Math.sqrt` （实际上更多，但实例变量查找（包括 `attr_reader`！）、加法和减法通常会被特化处理，即使在解释器中也不会压栈。） 此外，至少有两个堆分配：每个 `Point` 实例一个。最后，还有大量进出 `Point` 实例的内存流量。这真是令人沮丧！本来应该是一个简单的数学运算，现在却被一堆其他东西淹没了。`Point` 肯定不是零成本抽象。即使我们有一堆其他优化，比如加载-存储消除或逃逸分析，它们也无法做太多事情：几乎所有的东西都逃逸了并且有副作用。也就是说，除非我们**内联**。内联是撬动其他优化链的杠杆。 ## 内联：“简单”的部分 几年前，我写过关于 Cinder 内联器的设计与实现（FB 链接（https://engineering.fb.com/2022/05/02/open-source/cinder-jits-instagram/），个人博客链接（https://bernsteinbear.com/blog/cinder-jit-inliner/））。我写的是可以说最简单的部分，即将被调用者的主体复制到调用者中。我花了至少一周才让它工作。如果算上 JIT 其余部分的管道工作，可能接近几个月。 今年二月的一次小型黑客马拉松中，我看着我的同事 k0kubun（https://github.com/k0kubun）在 ZJIT 中大约 30 分钟就原型化了内联的那一部分。当虚拟机的几乎每个部分都从宿主语言中可观察时，还有更多工作要做：Python 和 Ruby 都允许从用户代码检查局部变量的状态、调用栈等。采样分析器也期望一些面包屑来检查栈。所以还需要一些额外的机制来假装被调用函数没有被内联。我在 Cinder 的博文中稍微提到过这一点。即便如此，所有这些可能都可以在几个月内设计和连接起来。然后你会发现自己接下来 10 年都在调优内联器。这要难得多。 ## 何时：更难的部分 内联困难的地方，尤其是在方法 JIT 中，在于你试图让整个（动态！）系统变得更快，但你只能通过显微镜观察，并且只能进行局部推理¹（https://bernsteinbear.com/blog/inlining-heuristics/#fn:aot-split）。而其他优化，比如强度削弱、内联缓存和值编号，对生成的代码只有纯好处，内联却可能产生**负面影响**。它也可能是人们添加的第一个具有非局部影响的优化。如果你内联错了，代码大小可能会暴涨。这可能会使 CPU 的缓存抖动。很糟糕，但谁都会遇到。但此外，如果你内联错了，你可能会妨碍其他有用的优化：如果内联方法 A 后达到了某个大小限制，你可能永远无法内联 B，而 B 正是解锁你要优化的方法性能的关键。最后，内联可能会损害编译时间。在延迟至关重要的场景（比如交互式客户端 JavaScript）中，将大量额外代码加入混战可能会导致明显的卡顿，即使长期吞吐量有所提升。一如既往，带内编译是一种权衡，因为你花在编译上的任何时间，都无法执行代码。 你必须让你的编译器推理所有这些事情。所以你需要启发式方法。例如，这是 Michael Pollan 的内联启发式： > *内联方法。大多数情况下小的。不要太多。* 我调查了一大堆编译器，主要是 JIT 编译器，看看它们的内联启发式方法是什么样的。我还阅读（略读）了一些论文，看看那些作者怎么说。我想知道他们是否同意。 这篇文章酝酿已久。大约五年前我开始写，但后来当我从 Facebook 离职时，我不小心丢掉了为 Cinder 内联器做的所有研究。所以之后我有一段时间漫无目的地思考，直到今年重新开始。无论如何，这就是“奇迹墙”。 ## 启发式方法 剧透警告：总的来说，人们通常会考虑以下几点： - 调用目标的性能分析数据 - 累计调用者大小（随着被调用者被内联而增加） - 被调用者大小 - 内联深度 - 特定深度内联调用的数量 - 是否存在递归 - 被调用者/调用者调用次数比率（如果被调用者仅被调用次数少于调用者调用次数的 K%，则不内联被调用者） - 被调用者的栈使用情况 - 被调用者的多态性 - 编译器所处的模式（基线 vs 更激进） - 被调用者是否看起来总是抛出异常 并且还有不同的有趣方式来引入性能分析信息。最后，一些较新的论文做了一些疯狂的事情： - 训练神经网络来做内联决策 - 让内联驱动整个优化管道，将其视为对调用图的 BFS 遍历的搜索启发式 - 使用 AOT 收集的信息来辅助 JIT 启发式 另一个在内联中需要考虑的是如何收集和解释性能分析数据。 ## 调用上下文和性能分析：另一个更难的部分 当你编译一个函数时，你倾向于基于它历史上接收的输入来特化它。对于单态输入，你可能检查类型是否仍然相同，否则跳转到解释器。对于多态输入，你可能检查最常见的 K（~4）种情况，否则跳转到解释器。没问题。但有时你可能正在编译一个多态方法 `bar`，它在调用者 `foo` 中实际上是单态的。也就是说，`foo` 可能只向 `bar` 传递一种输入，但其他调用者传递各种东西。这里有一个有点傻的例子来说明我的意思： ```ruby class HashWithIndifferentAccess def initialize @hash = {} end # 允许使用 String 或 Symbol 读取 Hash def [](key) = @hash[key.to_sym] # ... end # 一些方法... some_hash = HashWithIndifferentAccess.new # ... some_hash["abc"] # 另一个方法... another_hash = HashWithIndifferentAccess.new # ... another_hash[:xyz] ``` 开个玩笑，其实并不傻。这在 Rails 中是一个非常常见的模式（https://github.com/rails/rails/blob/6c75e6d5663afa4278ee593c2d6c20c1ee396e32/activesupport/lib/active_support/hash_with_indifferent_access.rb#L55）。它使得 `key` 在 `HashWithIndifferentAccess#[]` 中变成多态的，即使对于它的许多调用者来说，它可能是单态的（甚至是常量）。为了将这些信息传递到编译器中，你必须弄清楚这种调用上下文关系。有几种常见的方法。 ### 分裂 例如，YJIT 虽然不进行内联，但会根据传入参数的类型来分裂方法。这意味着它会克隆编译后的代码，为每个上下文生成一个新版本。这并不提供**调用**上下文（“A 调用 B”），但提供类型上下文（“B 用整数调用，B' 用字符串调用”）。编译器可以在解释器或基线层级进行基于类型的分裂。 ### 性能分析分裂 如果你不喜欢复制代码，你可以改为复制性能分析数据。你可以使用类型上下文（如上所述）或调用上下文来做。例如，SpiderMonkey 进行“试用内联”，允许调用者向下传递一点内存，让可能的内联候选被调用者记录它们的内联缓存。每个函数不持有自己的 ICScript，而是调用者为该可能内联的调用点分配一个唯一的 ICScript。这为每个被调用函数提供了（至少？）一层的调用上下文。稍后，当将被调用者内联到调用者时，我们就不会让其他调用者的类型信息污染 IR 构建器（或读取性能分析数据的工具）。 ### 字节码内联 JavaScriptCore 通过将字节码内联到其他字节码中来处理这个问题。这是一个棘手的转换，但即使解释器也能访问调用上下文（！）。在升级到编译器时，所有内联决策已经做出了。 ### 带计数器的早期层级 HotSpot 通过多个层级处理这个问题。解释器升级到客户端编译器 C1。C1 在编译代码中对分支和调用目标进行性能分析。C1 可能根据这些新信息重新编译。C1 可能最终升级到 C2，C2 复制 C1 的内联决策。这样，我们通过内联在性能分析中获得了调用上下文。 ### 内联、分析并希望 最后一种你可以做的事情是信任优化器中的类型推断和分支折叠。你可以在构建 IR 时内联并在被调用者中进行多态特化，然后希望你的分支修剪将内联的被调用者单态化。这有点浪费，因为多态代码是“白建的”，但也许也能工作？ 好的，接下来是收集的笔记和半成品的评论。以下是对一大群 JIT 编译器的调查，以及它们如何推理内联启发式。 ### 致谢 但在那之前，感谢 Iain Ireland、CF Bolz-Tereick 和 Ian Rogers 对本博文的反馈！ ## 调查：零碎知识点 以下大致是 Phil Zucker（https://www.philipzucker.com/）风格的“零碎知识点”部分。我们从 Cinder（https://github.com/facebookincubator/cinderx）开始，因为当我写 Cinder 的内联器时，我只添加了最简单的启发式方法，主要是“不要内联”的信号。随着时间的推移，我离开后，人们对其进行了更多调优。 ### Cinder 内联器（https://github.com/facebookincubator/cinderx/blob/88189ebf4bfd196ac7578c5076efa39bfa11f211/cinderx/Jit/hir/inliner.cpp#L341）从调用者的 CFG 开始，遍历它找到合适的内联候选。内联候选项仅限于已知的调用目标——在 Cinder 的情况下，仅限单态调用目标——并通过一些检查。被调用者只能通过其函数对象得知，其中包括其字节码。在我们决定内联之前，没有可用的被调用者 IR。大多数“无法处理”的检查与参数处理有关。Python 有相当复杂的调用约定，因此如果调用者/被调用者没有就参数如何传递达成一致，内联器不关心尝试自己解决。那是编译器其他部分（https://github.com/facebookincubator/cinderx/blob/88189ebf4bfd196ac7578c5076efa39bfa11f211/cinderx/Jit/hir/simplify.cpp#L1765）的责任。这个 `canInline` 函数中的内容可以被认为是“TODO”。 ```cpp bool canInline(Function& caller, AbstractCall* call_instr) { // ... BorrowedRef<PyFunctionObject> func = call_instr->func; auto fail = [&](InlineFailureType failure_type) { dlogAndCollectFailureStats(caller, call_instr, failure_type); return false; }; if (func->func_kwdefaults != nullptr) { return fail(InlineFailureType::kHasKwdefaults); } BorrowedRef<PyCodeObject> code{func->func_code}; JIT_CHECK(PyCode_Check(code), "Expected PyCodeObject"); if (code->co_kwonlyargcount > 0) { return fail(InlineFailureType::kHasKwOnlyArgs); } // ... } ``` 失败会被记录以便分析。如果 Cinder 团队确定有一些非常频繁的情况需要处理，他们会在日志中找出。内联器在一遍 CFG 遍历中收集所有候选调用指令。它从选项结构体加载可配置的“成本限制”。然后它一遍遍历内联候选向量，内联直到（可能）达到成本限制。 ```cpp // ... size_t cost_limit = getConfig().inliner_cost_limit; size_t cost = codeCost(irfunc.code); // Inline as many calls as possible, starting from the top of the function and // working down. for (auto& call : to_inline) { BorrowedRef<PyCodeObject> call_code{call.func->func_code}; size_t new_cost = cost + codeCost(call_code); if (new_cost > cost_limit) { LOG_INLINER( "Inliner reached cost limit of {} when trying to inline {} into {}, " "inlining stopping early", new_cost, funcFullname(call.func), irfunc.fullname); break; } cost = new_cost; inlineFunctionCall(irfunc, &call); // We need to reflow types after every inline to propagate new type // information from the callee. reflowTypes(irfunc); } // ... ``` 它在内联这些调用后进行一些图维护工作，但仅此而已。这种方法虽然简单，却获得了惊人的实用性：它内联常量（不少方法看起来像是 `def foo(): return 5`）、小方法，并且（至少据我所知）缩小了编译后的代码大小。而编译时间开销非常小。 还有一个“独立的” Python JIT，PyPy。所以我们也应该看看它。 ### PyPy PyPy 中有两个内联器。一个在 RPython 到 C 的翻译管道中，它更像是一个提前编译器²（https://bernsteinbear.com/blog/inlining-heuristics/#fn:rpython-inliner）。另一个是追踪 JIT 部分，它有自己的优化器和启发式方法。我们将看后者。 我和 CF Bolz-Tereick（https://cfbolz.de/）聊过内联器，他们的评论是 PyPy 的内联启发式是“是”。有一些例外，比如不内联递归函数或带循环的函数。但追踪的基本思想包括追踪调用指令，这自然意味着你在“内联”。 PyPy 还做了一件巧妙的事情，它们将帧推入视为普通分配。帧推入、帧读取和帧写入像普通对象内存流量一样写入追踪，并且可以像其他字段读写一样被优化掉。这意味着它们可以“只用”死代码消除来消除帧推入和弹出，而 Cinder 有一些复杂的机制来做这件事（那是我的错）。 TODO 在此获取更多细节 ### V8 V8 是一个 JS 引擎，多年来它有许多执行方法。我们将看其中三个，因为它们都在历史中占有一席之地： - Hydrogen 是第一个真正的 SSA IR，对我而言看起来非常熟悉，因为我曾工作于 Cinder 和现在的 ZJIT。它现在已经废弃了。 - Turbofan 是替代者，完全采用 Sea of Nodes。总体而言它是一个相当快的编译器，但它并不回避进行一些昂贵的重写。最近它从 Sea of Nodes 重写为传统的 CFG 模式，并昵称为 Turboshaft。 - Maglev 旨在与 Turbofan 共存，更倾向于更急切地进行推测，并减少增量重写的次数以换取编译时间。³（https://bernsteinbear.com/blog/inlining-heuristics/#fn:turbolev） 它们各自在管道的不同时间点进行内联，这使得理解不同代码变得有趣。