去年排查过一个性能问题. 一个包含很多正则替换的函数, 在处理几十万字符长度的文本时, 跑了 10 秒才完成. 最后定位到问题正则形式如下:
\s*xyz blahblah
几年前排查过 灾难性回溯 问题, 但这个正则的结构其实完全没有相关特征. 如果真的是灾难性回溯, 处理几十万字符的字符串早就卡死了, 而不是只跑 10 秒.
最后解决方案是先用
xyz blahblah
找 match, 再处理 leading spaces. 时延是毫秒内.
首字符优化
正则表达式引擎有一个核心优化技术——初始字符/类/子串区分优化 (Initial character/class/substring discrimination optimization). 下面内容参考 Mastering Regular Expressions.
现代正则表达式引擎在编译正则表达式时, 会进行一系列静态分析. 其中最重要、也是效果最显著的一项分析就是: 确定任何匹配这个正则表达式的字符串, 必须以哪些字符或子串开头.
如果引擎能够确定这一点, 它就不会在字符串的每个位置都尝试完整匹配正则表达式, 而是会采用一个极其高效的两步策略:
- 使用高度优化的原生字符串扫描算法 (通常是 Boyer-Moore 或其变种) 快速定位所有可能的候选起始位置
- 只在这些候选位置上尝试完整匹配正则表达式
对于正则表达式 xyz blahblah, 引擎很容易分析出: 任何匹配都必须以字符 x 开头. 因此, 它会先在整个字符串中快速扫描所有 x 出现的位置. 如果一个几十万字符的字符串中只有 3 个 x, 那么它只需要在这 3 个位置尝试匹配后续的 yz blahblah, 而不是在几十万个位置都尝试一次.
为什么 \s* 会彻底破坏这个优化? 问题就出在 \s* 这个前导空白字符匹配上. 因为 “零个空白字符” 是完全合法的匹配, 每个字符位置都可能是匹配的起点. 当正则表达式以无锚点的 \s*、.*、.*? 这类通用量词开头时, 引擎无法确定任何必须的起始字符. 它只能退回到最原始、最低效的匹配方式: 在字符串的每一个字符位置上, 都从头开始尝试完整匹配整个正则表达式.
正则引擎的其他相关优化
1. 必需字符/子串预检查优化
这是首字符优化的更通用版本. 引擎不仅会分析起始字符, 还会分析整个正则表达式中必须出现的任何字符或子串, 无论它们出现在什么位置.
在实际应用正则表达式之前, 引擎会先快速检查目标字符串中是否包含这些必需字符或子串. 如果不包含, 就可以直接跳过整个正则匹配过程, 节省大量时间.
例如, 对于正则表达式 ^Subject: (.*), 引擎会发现字符串 Subject: 是任何匹配都必须包含的. 它可以使用 Boyer-Moore 算法快速搜索整个字符串, 如果找不到 Subject:, 就直接返回不匹配.
2. 长度认知优化
引擎还会分析正则表达式的最小匹配长度. 如果目标字符串的长度小于这个最小长度, 就可以直接跳过匹配.
例如, ^Subject: (.*) 的最小匹配长度是 9 个字符 (“Subject: “). 因此, 对于任何长度小于 9 的字符串, 引擎都不需要启动完整的匹配过程. 对于那些有很长固定后缀的正则表达式 (如 :\d{79}:), 这个优化的效果会更加明显.
3. 不同引擎的实现差异
需要特别注意的是, 不同的正则表达式引擎在这些优化的实现程度上有非常大的差异:
- 大多数现代引擎都能很好地处理简单的固定前缀优化
- 但对于包含交替 (
|) 的复杂表达式, 很多引擎无法推导出共同的起始字符 - 例如, 对于
this|that|other, 一些引擎只能推导出起始字符是[ot], 而无法推导出更复杂的模式 - 这也是为什么书中建议使用
th(is|at)代替this|that, 这样引擎可以更容易地推导出共同前缀th