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

Question

我需要接受用户的正则表达式——我知道，这太疯狂了。Google RE2 正则表达式解析器比基于 PCRE 的解析器更安全，因为它不使用回溯，从而防止灾难性回溯、无限循环和一般混乱。据称它通常会更快。在我的测试用例中，它只是解析一个 syslog 行，它慢了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
• 使用 node-re2 包中包含的日期为 2016 年 11 月 30 日的 re2 C++ 代码。
• 我安装了 libre2-dev 软件包版本 20160501+dfsg-1。也许我应该更新 node-re2 下的源代码，或者让它简单地链接到系统库。

Answer 1

RE2 具有线性最坏情况复杂度。Node.js 的 Irregexp 引擎在最坏情况下的复杂性呈指数级增长。

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