正则表达式分支性能异常：双分支为何比三分支更慢？

测试场景与结果 #

实际使用的正则表达式更为复杂，但添加第二个分支后性能开销飙升，以下是测试代码：

import timeit
SETUP = "import re; STRING = ' ' * 100000"

print(min(timeit.Timer("re.findall(r'(foo)'        , STRING)", SETUP).repeat(10, 1000)))
print(min(timeit.Timer("re.findall(r'(foo|bar)'    , STRING)", SETUP).repeat(10, 1000)))
print(min(timeit.Timer("re.findall(r'(foo|bar|qux)', STRING)", SETUP).repeat(10, 1000)))

Python 3.10.2 测试结果 #

0.012617316999239847
0.18311264598742127
0.146542029993725

双分支正则速度比单分支慢15倍，且三分支比双分支更快。

Python 3.11.8 测试结果 #

0.022139030000005278
0.8239181079999867
0.6327433810000116

性能差异更显著，双分支比单分支慢近37倍。

PyPI regex库测试结果 #

0.022885548998601735
0.25088962000154424
0.2537434719997691

整体速度更慢，但单分支与双分支的性能差依然明显，三分支和双分支性能接近。

原因分析 #

• NFA引擎的回溯机制：Python标准库re使用NFA（非确定有限自动机）引擎，双分支场景下，引擎在匹配失败后会频繁切换分支尝试回溯。测试用的全空格字符串属于完全不匹配的极端场景，每个位置都要遍历双分支的所有可能路径，回溯成本极高。
• 分支数量触发的优化差异：当分支增加到三个时，引擎会自动启用分支预测或状态合并优化，减少不必要的回溯操作，反而降低了整体开销；而双分支时引擎未触发这类优化，导致性能暴跌。
• PyPI regex库的特性：该库虽优化更全面，但同样基于NFA，单分支到双分支的状态跃迁成本依然存在，只是多分支后的优化幅度不如标准库明显，因此双分支与三分支性能接近。

性能优化方法 #

• 使用原子组禁止回溯：将(foo|bar)改为(?>foo|bar)，原子组会禁止引擎在分支间回溯，匹配失败后直接移动到下一个位置，大幅减少无意义的遍历。修改后的测试代码示例：

  print(min(timeit.Timer("re.findall(r'(?>foo|bar)'    , STRING)", SETUP).repeat(10, 1000)))
  

• 前置快速检查：如果业务中经常出现完全不匹配的长字符串，可先做简单检查（比如判断字符串是否包含目标分支的首字符'f'/'b'），再执行正则匹配，避免无意义的遍历。
• 合并共同前缀：若分支有共同前缀，合并前缀可减少分支数量。例如(foo|foobar)可改为foo(bar)?，降低引擎的分支切换成本。

内容的提问来源于stack exchange，提问作者Peter Lang