Go 的最佳正则表达式替代方案

介绍

“不要使用正则表达式，否则你会遇到 2 个问题，而不是 1 个” ——专家是这么说的。对于那些想要有效地搜索大量模板的淘气者来说，还剩下什么呢？

当然，对于这个特定问题，有一些很酷的解决方案，例如Ragel或re2c。然而，对于我的项目来说，暂时掌握这些精细技术似乎不太切实际。

在本文中，我们将研究 Go 中标准正则表达式库的替代方案，并对它们的速度和内存消耗进行基准测试。我们也会从实际的角度考虑它们之间的差异。

正则解决方案

目前，我发现了以下默认正则表达式的工作替代方案，可用于在 Go 中查找模式（基准测试中使用的版本在括号中给出）：

• go-re2 (1.3.0) — 尽可能简单地替换默认的正则表达式。使用C++ re2来提高处理大输入或复杂表达式时的性能；
• regexp2 (1.10.0) — 一个功能丰富的Go正则表达式引擎。它不像内置的regexp包那样有运行时保证，但与Perl5和.NET兼容；
• go-pcre (1.0.0) —使用libpcre或libpcre++提供对Perl兼容正则表达式的支持。JIT 编译可用，使得该分支比其对应版本快得多。缺点是，您需要libpcre3-dev依赖项；
• rure-go (正则表达式 1.9.3) — 使用带有CGo绑定的Rust正则表达式引擎。缺点是需要编译Rust库依赖项；
• gohs (1.2.2 + hs5.4.1) — 专为高性能而设计的正则表达式引擎。它被实现为一个提供简单C-API 的库。它还需要编译和链接第三方依赖项；
• go-yara — 用于识别和分类恶意软件样本的工具。虽然YARA具有模板和正则表达式的功能，但它非常有限，因此我不会在即将进行的测试中包含该库。

现有基准

在我们开始比较上述解决方案之前，有必要先展示一下Go中的标准正则表达式库有多么糟糕。我找到了作者比较各种语言的标准正则表达式引擎性能的项目。该基准测试的重点是对预定义文本重复运行 3 个正则表达式。Go在这个基准测试中排名第三！从最后……

据我所知，对正则表达式引擎进行基准测试并不是最简单的主题，因为您需要了解实现和算法细节才能进行正确的比较

从其他基准来看，我可以强调以下几点：

• 基准测试— 比较每种语言的引擎和优化版本。例如，Go不再处于底部，但它仍然远未达到理想状态……当然，它不使用本机库，而是使用 PCRE 的包装器 — go-pcre。
• 正则表达式引擎的性能比较- 不同正则表达式引擎（PCRE、PCRE-DFA、TRE、Oniguruma、RE2、PCRE-JIT）的比较。
• 正则表达式引擎的比较- 在这里，作者尝试比较使用不同正则表达式的引擎，这可能会使事情变得复杂，具体取决于引擎的实现。在这个基准测试中，作者排名前三的引擎是：Hyperscan、PCRE（带有 JIT 编译）和 Rust regex（rure使用它）

基准#1

现在让我们尝试将类似物与其他语言的默认正则表达式引擎库进行比较。还可以看看它们与默认的Go 正则表达式相比快了多少。为此，我通过添加新的库代码更新了上述项目。这是我在我的机器上运行后得到的结果：

尽管如此，您仍然可以看到某些库的正则表达式可以快得多！我们甚至通过使用 Rust 库的 Go 库超越了 Rust 🥴🙆🏼‍♂️。也许这就是该解决方案的作者试图在他的存储库中向我们解释的内容。

因此，几乎所有替代解决方案都能使我们的速度提高8-130倍！除Regexp2之外，它比标准库慢。

基准#2

1. 问题

在研究现有基准测试和Benchmark#1的结果时，我缺乏以下问题的答案：

• 上述库处理大文件的速度有多快？
• 对正则表达式进行分组时，处理速度有多快？
• 处理文本中没有匹配项的正则表达式的速度有多快？
• 不同的库使用多少内存？
• 使用分组我可以编译多少个正则表达式？

2. 基准差异

为了回答这些问题，我编写了一个小型基准测试程序，可用于比较不同的正则表达式引擎的速度和内存使用情况。如果您想自己测试或评估所使用方法的正确性，这里是代码。

该基准测试的以下特点值得一提：

在下面的测试中，我使用了5 种不同的正则表达式：

allRegexps["email"] = `(?P<name>[-\w\d\.]+?)(?:\s+at\s+|\s*@\s*|\s*(?:[\[\]@]){3}\s*)(?P<host>[-\w\d\.]*?)\s*(?:dot|\.|(?:[\[\]dot\.]){3,5})\s*(?P<domain>\w+)`
allRegexps["bitcoin"] = `\b([13][a-km-zA-HJ-NP-Z1-9]{25,34}|bc1[ac-hj-np-zAC-HJ-NP-Z02-9]{11,71})`
allRegexps["ssn"] = `\d{3}-\d{2}-\d{4}`
allRegexps["uri"] = `[\w]+://[^/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?`
allRegexps["tel"] = `\+\d{1,4}?[-.\s]?\(?\d{1,3}?\)?[-.\s]?\d{1,4}[-.\s]?\d{1,4}[-.\s]?\d{1,9}`

以一种好的方式，我应该像其他基准测试作者一样使用棘手的正则表达式来检查算法的“弱点”。但我对引擎的底层细节不太了解，所以我使用了通用的正则表达式。这就是为什么我认为应该可以从实际的角度评估库的不同参数。

• 我们将使用包含匹配项的字符串，而不是静态文件，该字符串在内存中重复多次来模拟不同大小的文件：

var data = bytes.Repeat([] byte ( "123@mail.co nümbr=+71112223334 SSN:123-45-6789 http://1.1.1.1 3FZbgi29cpjq2GjdwV8eyHuJJnkLtktZc5 Й" ), config.repeatScanTimes)

• 除了对数据按顺序运行正则表达式之外，还将对正则表达式进行命名分组的单独运行，其中它们将采用以下形式：

`(?P<name_1>regexp_1)|(?P<name_2>regexp_2)|...|(?P<name_N>regexp_N)`

顺便说一句，Hyperscan 有一个特殊的功能，我们可以构建正则表达式数据库并将其用于数据。在基准测试中我将使用这种方法。

与Benchmark#1不同，对于每个正则表达式，我将测量查找结果的时间，而不考虑编译时间；最后，我们将以以下形式获得每个库和每个正则表达式的结果：

Generate data...
Test data size: 100.00MB
Run RURE:
  [bitcoin] count=1000000, mem=16007.26KB, time=2.11075s 
  [ssn] count=1000000, mem=16007.26KB, time=62.074ms 
  [uri] count=1000000, mem=16007.26KB, time=69.186ms 
  [tel] count=1000000, mem=16007.26KB, time=83.101ms 
  [email] count=1000000, mem=16007.26KB, time=172.915ms 
Total. Counted: 5000000, Memory: 80.04MB, Duration: 2.498027s
...

结果，我们有以下数据：

下图显示了所有正则表达式在顺序模式下并使用分组处理 100MB 数据的时间：

结论：

• 分组确实可以显着提高执行速度，但在某些情况下它可能会使情况变得更糟:)；
• 顺序处理中最快的是 — Rure，带有分组 — Re2；
• email某些正则表达式可能会导致某些库出现问题（需要在Regexp2和PCRE中查找）；
• 现在很难说有些解决方案比标准库快 180 倍，最大增益是x8-9。

3. 不匹配的正则表达式

在前面的案例中，我们模拟了数据中始终存在匹配的理想情况。但是，如果文本中没有匹配正则表达式怎么办，这会对性能产生多大影响？

在此测试中，我另外为 SSN 添加了5 个与数据不匹配的修改后的正则表达式。在本例中，SSN表示\d{3}-\d{2}-\d{4}正则表达式，并且Non-matching- \d{3}-\d{2}-\d{4}1。差别不大吧？但让我们看看它如何影响查找所有匹配项所需的时间：

下图显示了处理所有10 个正则表达式所需的时间（按Non-matching处理时间排序）：

结论：

• 这次是相同的：顺序处理中最快的是 — Rure，带有分组表达式 — Re2；
• PCRE再次不同，在顺序模式下处理正则表达式的时间是原来的2 倍；non-matching
• 有些算法在没有匹配项时速度要快得多（Re2、Hyperscan）；

4、内存消耗

现在让我们看看处理 100MB 文件时不同的解决方案消耗多少内存。下面，我提供了每个单独的正则表达式的结果以及消耗的内存总量：

下图显示了库处理10 个正则表达式（如上一个测试）所使用的内存，按“非数学”时间排序：

结论：

• Rure令人惊讶的是它几乎为零的内存消耗；
• Regexp2非常消耗资源，比其竞争对手消耗更多的内存；
• Re2尽管速度快，但并不是最节省内存的解决方案；
• Go 正则表达式有好的一面，在顺序模式下成本相对较低。

5. 正则表达式的最大数量

主要问题似乎已经得到解答。现在让我们看看可以使用不同解决方案编译的正则表达式的最大数量。在这种情况下，我们将采用单个正则表达式并分组重复多次。为此，我将使用URI正则表达式：

`[\w]+://[^/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]* ）？`

接下来，我列出了编译正则表达式的结果以及它们使用的内存。第一行中的数字是URI组中表达式的数量：

总结：

• 正如我们所看到的，一些解决方案对编译的正则表达式的大小有限制；
• Hyperscan不仅允许使用大量的正则表达式，而且还可以使用最少的内存来编译正则表达式；
• Regexp2和Go Regex具有相当的内存消耗，并且还允许编译大量正则表达式；
• Re2在编译时消耗的内存最多。

结论

我希望这对您了解Go中正则表达式的替代解决方案有所帮助，并且根据我提供的数据，每个人都可以自己得出一些结论，这将使您能够根据自己的情况选择最合适的正则表达式解决方案。

我们可以长期详细地比较这些库、它们使用的算法、它们最好/最差的一面。我只是想在最一般的情况下展示它们之间的区别。

因此，我建议您考虑rure-go正则表达式的最大加速，但如果您需要最简单的没有依赖项的库安装，那就是go-re2. 在处理大量正则表达式的情况下hyperscan将是一个不错的选择。另外，不要忘记在某些库中使用CGo的成本。