跳到主要内容

改善 V8 正则表达式

· 阅读需 8 分钟
Patrick Thier 和 Ana Peško，对正则表达式发表意见的常规专家

在默认配置下，V8 在正则表达式第一次执行时会将其编译为本地代码。作为我们对 无 JIT 的 V8 的工作的一部分，我们引入了一个正则表达式解释器。解释正则表达式的优势在于使用更少的内存，但会带来性能上的损失。本文中我们介绍了如何利用解释正则表达式的优势，同时减轻其缺点。

正则表达式的分层策略​

我们希望为正则表达式使用“鱼与熊掌兼得”的方法。为此，我们首先将所有正则表达式编译为字节码并进行解释。这样，我们节省了大量内存，而且（通过新的、更快的解释器）总体来看性能损失是可以接受的。如果相同模式的正则表达式再次使用，我们认为它是“热点”，因此我们重新编译为本地代码。从这时起，我们尽可能快地继续执行。

在 V8 中根据调用方法、正则表达式是全局还是非全局模式，以及是否走快速路径或慢速路径，正则表达式代码可能存在许多不同的路径。话虽如此，我们希望分层决策尽可能集中化。我们为 V8 的 RegExp 对象添加了一个 ticks 字段，该字段在运行时初始化为某个值。这个值表示在升级到编译器之前将解释正则表达式的次数。每次解释正则表达式，我们都会将 ticks 字段减 1。在用 CodeStubAssembler 写成的内置方法（适用于所有正则表达式）中，我们在每次执行时检查 ticks 标志。一旦 ticks 到达 0，我们就知道需要将正则表达式重新编译为本地代码，并跳到运行时进行调整。

我们曾提到正则表达式可能有不同的执行路径。对于使用函数作为参数的全局替换的情况，原生代码和字节码的实现是不同的。原生代码期望提前存储所有匹配项的数组，而字节码一次匹配一个。基于此，我们决定在此用例中始终主动升级到原生代码。

提升正则表达式解释器的速度​

消除运行时开销​

当正则表达式执行时，会调用一个用 CodeStubAssembler 编写的内置方法。这个内置方法之前会检查 JSRegExp 对象的代码字段中是否包含可以直接执行的 JIT 编译的本地代码，否则会调用一个运行时方法来编译（或在无 JIT 模式下解释）正则表达式。在无 JIT 模式下，正则表达式的每次执行都通过 V8 的运行时，这非常昂贵，因为我们需要在执行栈中在 JavaScript 和 C++ 代码之间进行转换。

从 V8 v7.8 开始，无论何时正则表达式编译器生成字节码来解释正则表达式，现在会在 JSRegExp 对象的代码字段中存储跳转到正则表达式解释器的中继代码以及生成的字节码。这样，解释器现在可以从内置方法直接调用，而无需通过运行时进行绕行。

新的分发方法​

之前，正则表达式解释器使用了一个简单的 switch 分发方法。此方法的主要缺点是 CPU 很难预测下一条要执行的字节码，导致许多分支预测失败，从而减慢执行速度。

我们在 V8 v7.8 中将分发方法更改为线程代码。此方法允许 CPU 的分支预测器根据当前执行的字节码预测下一条字节码，从而减少预测失败的次数。具体来说，我们使用一个分发表，存储每个字节码 ID 与实现该字节码的处理程序地址之间的映射。V8 的解释器 Ignition 也使用了这种方法。然而，Ignition 和正则表达式解释器之间的一个重要区别是 Ignition 的字节码处理程序是用 CodeStubAssembler 编写的，而整个正则表达式解释器是用 C++ 编写的，并使用 计算 gotos（一个 GNU 扩展也被 clang 支持），这些代码比 CSA 更易于阅读和维护。对于不支持计算 gotos 的编译器，我们回退到旧的 switch 分发方法。

字节码窥孔优化​

在讨论字节码窥孔优化之前，让我们先看一个激励性的例子。

const re = /[^_]*/;
const str = 'a0b*c_ef';
re.exec(str);
// → 匹配 'a0b*c'

对于这个简单的模式，正则表达式编译器为每个字符创建了 3 条字节码。这些字节码在高层次上如下：

  1. 加载当前字符。
  2. 检查字符是否等于 '_'。
  3. 如果不是，前移主题字符串中的当前位置并执行 goto 1。

对于我们的主题字符串，我们运行了 17 条字节码直到找到一个不匹配的字符。窥孔优化的思想是用一个新的优化字节码替换字节码序列，以结合多个字节码的功能。在我们的例子中，我们甚至可以在新字节码中显式处理由 goto 创建的隐式循环，因此一个字节码就可以处理所有匹配的字符，节省了 16 次调度。

尽管这个例子是虚构的，但这里描述的字节码序列在真实网站中经常出现。我们分析了真实网站并为我们遇到的最频繁的字节码序列创建了新的优化字节码。

结果​

图 1：不同升级设置下的内存节省情况

图 1 展示了在 Facebook、Reddit、Twitter 和 Tumblr 浏览故事中，不同升级策略对内存的影响。默认值是 JIT 编译代码的大小，然后是我们实际使用的正则表达式代码的大小（如果我们不升级则为字节码大小，如果升级则为本地代码大小），对应的初始化 ticks 值为 1、10 和 100。最后，是我们将所有正则表达式解释执行时的正则表达式代码大小。我们基于这些结果和其他基准测试决定以 ticks 初始化为 1 的策略开启升级，即我们先解释一次正则表达式，然后再升级。

采用这种升级策略后，我们在真实网站上的 V8 堆代码大小减少了 4% 到 7%，V8 的有效大小减少了 1% 到 2%。

图 2：正则表达式性能对比

图 2 展示了用于 RexBench 基准测试套件中，本文描述的所有改进对正则表达式解释器性能的影响1。作为参考，还展示了 JIT 编译正则表达式的性能（本地）。

新的解释器的速度最多是旧解释器的 2 倍，平均快约 1.45 倍。除了 Regex DNA 外，我们在大多数基准测试中甚至接近 JIT 正则表达式的性能。在这个基准测试中，解释执行的正则表达式比 JIT 编译的正则表达式慢得多，其原因在于使用了长的主题字符串（~300,000 个字符）。即使我们将调度开销降至最低，对超过 1,000 个字符的字符串来说，这种开销仍然累积，从而导致较慢的执行。由于解释器在处理长字符串时速度过慢，我们添加了一种启发式方法，对这些字符串提前升级。

结论​

从 V8 v7.9（Chrome 79）开始，我们针对正则表达式采用升级策略，而不是直接编译。因此，之前只在无 JIT 的 V8 中使用的解释器现在被应用到所有地方。这样我们节省了内存。为了使这一点可行，我们加快了解释器的速度。但这并不是最终结果 — 未来还会有更多改进。

我们想借此机会感谢 V8 团队的每一位成员在我们的实习期间给予的支持。这是一次非常棒的经历！

Footnotes​

  1. 此处显示的结果还包括 V8 v7.8 发布公告 中已经描述的正则表达式改进。 ↩