为什么在这个例子中节点的回溯正则表达式比 RE2 更快

Question

我需要接受来自用户的正则表达式——我知道这很疯狂。 Google RE2 正则表达式解析器比基于 PCRE 的正则表达式解析器更安全，因为它不使用回溯，从而防止灾难性回溯、无限循环和一般混乱。 据称它通常更快。 在我的测试用例中，它只是解析系统日志行，它慢了 300% 以上。 知道为什么吗？

我在 Ubuntu 上使用 Node v7.7.3。

有问题的代码：

const SYSLOG_LINE_REGEX = new RegExp([
    /(<[0-9]+>)?/, // 1 - optional priority
    /([a-z]{3})s+/, // 2 - month
    /([0-9]{1,2})s+/, // 3 - date
    /([0-9]{2}):/, // 4 - hours
    /([0-9]{2}):/, // 5 - minutes
    /([0-9]{2})/, // 6 - seconds
    /(s+[w.-]+)?s+/, // 7 - host
    /([w-().0-9/]+)/, // 8 - process
    /(?:[([a-z0-9-.]+)])?:/, // 9 - optional pid
    /(.+)/ // 10  message
].map(regex => regex.source).join(''), 'i');
const parts = SYSLOG_LINE_REGEX.exec(log.trim());

更新：

• 使用节点模块 re2@1.4.1
• 使用 re2 C++ node-re2 包中包含的日期为 2016 年 11 月 30 日的代码。
• 我安装了libre2-dev软件包版本20160501 + dfsg-1。也许我应该更新 node-re2 下的源代码，或者让它简单地链接到系统库。

Answer 1

RE2 具有线性最坏情况的复杂性。Node.js的Irregexp引擎具有指数级的最坏情况复杂性。

但！引擎的最坏情况行为不仅是正则表达式的函数，也是正在测试的输入的函数。正则表达式/(a+)+$/在 Node 中最坏的情况下呈指数级.js但如果您将其与除aaaaaaaaaa...a以外的任何东西匹配，它将运行得很快。正则表达式的平均匹配时间与其最坏情况的复杂性不同。Node.js引擎开发人员可能优化了平均情况的复杂性，而不是最坏情况的复杂性。