每周性能技巧 #21：提升正则表达式的效率

本文翻译自 Abseil 官网的 Performance Tip of the Week #21: Improving the efficiency of your regular expressions。

原文发布于 2020 年 1 月 16 日，作者 Paul Wankadia 和 Darryl Gove，更新于 2025 年 9 月 3 日。

正则表达式几乎无处不在，也经常被误用和滥用。Google 也不例外，而且在我们的规模下，一个简单改动就可能节省数百甚至数千个核心。本篇介绍如何更高效地使用 RE2。

注意：本文专门讨论 RE2 和 C++。下面很多想法普遍适用，但其他库和其他语言不在讨论范围内。

正则表达式使用示例

先看一个正则常见用法。下面代码在 zone_name 字符串末尾查找 zone ID，并把值提取到整数 zone_id：

1
2

int zone_id;
if (RE2::FullMatch(zone_name, R"(.*\.zone(\d+))", &zone_id)) {

下面介绍几类提升效率的方法：改进使用正则的代码，以及改进正则表达式本身。

编写更高效的代码

关于 RE2 对象

初始示例把模式字符串传给 RE2::FullMatch()。传入模式字符串而不是 RE2 对象，会隐式构造临时 RE2 对象。构造期间，RE2 会把模式字符串解析成语法树，并把语法树编译成自动机。

根据正则复杂度，构造可能消耗大量 CPU，并构建内存占用很大的自动机。

对字面字符串使用 Abseil 函数

很多情况下，简单字符串操作已经足够，正则表达式是不必要的。精确匹配可使用 absl::string_view 的 operator==()；子串、前缀和后缀匹配分别可用 absl::StrContains()、absl::StartsWith() 和 absl::EndsWith()。它们比正则更快，也更易读。

1
2
3

const RE2 re(absl::StrCat(row_key, ":.*"));
for (const auto& row : rows) {
  if (RE2::FullMatch(row, re)) {

可以改写为：

1
2
3

const std::string prefix = absl::StrCat(row_key, ":");
for (const auto& row : rows) {
  if (absl::StartsWith(row, prefix)) {

减少 RE2 对象 churn

构造 RE2 对象可能很昂贵，因此经验法则是让它们长寿命。建议尽可能预编译或缓存。

对静态或全局正则使用 LazyRE2

RE2 类不适合直接用于静态或全局正则。应使用 LazyRE2，因为它会惰性构造底层 RE2 对象，并且永不析构。

初始示例可以改写为：

1
2
3

static constexpr LazyRE2 kZoneRe = {R"(.*\.zone(\d+))"};
int zone_id;
if (RE2::FullMatch(zone_name, *kZoneRe, &zone_id)) {

编写更高效的正则表达式

使用 RE2::PartialMatch() 避免前导或尾随 .*

带前导或尾随 .* 使用 RE2::FullMatch() 是反模式。应改用 RE2::PartialMatch() 并移除 .*。RE2::PartialMatch() 执行未锚定搜索，因此仍需要用 ^ 或 $ 指明必须在字符串开头或结尾匹配。

替换前导 .*

前导 .* 应被移除，并把表达式用 $ 锚定到末尾。例如，.*-(?:bar|qux)-foo 应变成 -(?:bar|qux)-foo$。

前导 .* 会阻止 RE2 在从输入字符串末尾反向执行时，在匹配到最后一个相关字节后终止。当剩余输入较大时，RE2 会做大量无收益工作。

初始示例可以继续改写为：

1
2
3

static constexpr LazyRE2 kZoneRe = {R"(\.zone(\d+)$)"};
int zone_id;
if (RE2::PartialMatch(zone_name, *kZoneRe, &zone_id)) {

替换尾随 .*

尾随 .* 应被移除，并用 ^ 锚定到开头。例如，foo-(?:bar|qux)-.* 应变成 ^foo-(?:bar|qux)-。RE2 会分离 ^foo- 前缀，并用 memcmp(3) 匹配它。

尾随 .* 会阻止 RE2 在匹配到最后一个相关字节后终止。当剩余输入较大时，RE2 会做大量无收益工作。

同时替换前导和尾随 .*

如果同时有前导和尾随 .*，二者都应移除。例如，.*-(?:bar|qux)-.* 应变成 -(?:bar|qux)-。前导 .* 会阻止 RE2 使用 memchr(3) 查找第一个相关字节。

.* 真正意味着什么

问题在于，.* 默认并不表示“匹配任何内容”。实际上，. 默认等价于 [^\n]，也就是匹配非换行字符。RE2 默认使用 UTF-8 编码，因此会构建能处理多字节字符的自动机。因此，默认 .* 表示“匹配零个或多个非换行的多字节字符”。

自动机会逐字节遍历输入字符串，所以执行 .* 比使用通常由 SIMD 实现的 memchr(3) 慢得多，也远慢于在正则已经匹配后立即终止执行。

减少捕获组和子匹配

如果括号只是用于分组，除非要提取子匹配，否则应使用非捕获组 (?:...)。并且，应提取尽可能少的子匹配，因为执行引擎选择部分取决于调用方想要多少子匹配。

为无用子匹配传入 nullptr 是反模式。应把捕获组改成非捕获组。

对子匹配使用 absl::string_view

提取子匹配时使用 absl::string_view。提取到 std::string 必然涉及字符串复制。

即使对子匹配做数值转换，也同样适用。提取到数值类型也涉及字符串复制，因为 strtol(3) 等函数需要 NUL 结尾字符串。提取到 absl::string_view 后调用 absl::SimpleAtoi() 等函数，可以避免复制。

初始示例还可以继续改写为：

1
2
3
4
5

static constexpr LazyRE2 kZoneRe = {R"(\.zone(\d+)$)"};
absl::string_view zone_id_str;
int zone_id;
if (RE2::PartialMatch(zone_name, *kZoneRe, &zone_id_str) &&
    absl::SimpleAtoi(zone_id_str, &zone_id)) {

减少歧义

执行正则的成本很大程度取决于歧义。规则可以概括为：

• 必须能立即明确 alternation 的哪个分支应该被选择。
• 必须能立即明确 repetition 什么时候结束。

例如，(.+)/ 和 (.+?)/ 有歧义，因为 . 和 / 不互斥，一个 / 字节可能被任何一边消费。相反，([^/]+)/ 没有歧义，因为 [^/] 和 / 互斥。并非总能消除歧义，但通常可以减少。

例外：alternation 的公共前缀

RE2 会提取 alternation 的公共前缀。例如，abacus|abalone 会解析为 aba(?:cus|lone)。这个优化允许正则以更易读的方式书写。它适用于连续片段，因此建议按字典序排列子表达式。

避免计数重复

x{n}、x{n,} 或 x{n,m} 形式会让 x 在自动机中至少复制 n 或 m 次。对于锚定匹配这已经不理想，尤其使用 Unicode 字符类时；对于未锚定匹配则更危险，因为 DFA 状态数量和大小容易爆炸。每个 RE2 对象有内存预算，默认 8 MiB，主要用于缓存 DFA 状态；耗尽预算会带来可观性能损失。

例如，构造完整 DFA 时，锚定的 ^[a-q][^u-z]{13}x 需要 22 KiB，而未锚定的 [a-q][^u-z]{13}x 需要 6 MiB。前者因锚定而不适合搜索，后者则因未锚定导致 DFA 状态指数增长而效率低。也许可以改用 [a-q][^u-z]+x，再后续检查匹配长度，但这不一定可接受。

附加：匹配多个正则表达式

最后简单谈谈 RE2::Set 和 FilteredRE2。它们是匹配多个正则的两种不同方法，适用于多次扫描输入字符串成本过高的情况，例如关键词匹配和日志处理。

RE2::Set 把多个正则组合成一个“多匹配”自动机。它的优缺点类似普通 DFA 执行，适合较短、较不复杂的正则。

FilteredRE2 识别正则中的字面字符串 atom；给定输入中出现了哪些 atom，它判断哪些正则可能匹配。它需要先用类似 Aho-Corasick 或 RE2::Set 的东西扫描一遍输入，适合更长、更复杂的正则。