5

我正在考虑改进。我目前正在对日志文件进行大量文本处理。

我并不是说 PCRE 慢/快或任何其他实现。

我编写的语言主要是 Perl。我知道它有一个强大的正则表达式引擎,而且我知道它比 PCRE 更具表现力。

我有这样的想法,即在 C++ 中制作一个小型正则表达式引擎,将正则表达式编译为原始 nasm。

我知道 PCRE 非常复杂,我的假设是我可以跳过 PCRE 在不必要的处理方面所做的很多事情。我当然可以让它比 Perl 更快,因为它使用类似 vm 的操作码和各种可以被认为是开销的东西。

前段时间我已经开始实施了。我不会在这里发布它,因为我没有任何问题,我可以将它执行到最后并获得一个能够进行捕获、能够解释+ * ^ $、字符类的正则表达式引擎(虽然我还没有完成了我将正则表达式转换为汇编语言的部分)

这是个好主意还是坏主意?在达到良好性能方面会出现什么问题?

tl;dr => 可以生成本机程序集的 C++ 迷你正则表达式引擎比已建立的正则表达式实现更快吗?

4

4 回答 4

6

我认为这个问题的答案很明显。理想情况下,是的,它可能是。但是,即使你在这类事情上非常聪明,也需要付出很大的开发努力才能达到这样的程度,在大多数情况下,你只比可用的库稍微好一点——甚至更长的时间来工作的错误。所以没有太大意义。

于 2013-03-25T05:00:46.713 回答
6

Perl 的正则表达式很快,但不是非常快。请参阅Russ Cox 对 Perl 与 Thompson 风格的正则表达式引擎的分析,以获得关于性能差异的令人瞠目结舌的演示,以及如何正确执行此操作的理论。

如果你不想实现 Thompson/Cox 的方案,你应该考虑Ragel,一个非常快的正则表达式处理器。Ragel 努力构建高效的自动机,然后为目标编译器语言生成代码。它让编译器完成将“转换为机器代码”的艰苦工作。

它很可能是您正在考虑构建的引擎。

如果这些还不够好,您应该追踪 IBM 最近在极速流匹配器方面的工作。我认为Davide Pasetto的论文可能是相关的。

于 2013-03-25T05:10:01.083 回答
3

做一个基准测试。采用一个非常简单的正则表达式,但您通常会使用它。然后制作该正则表达式的硬编码版本。比较使用实际数量的数据,其中操作需要足够长的时间才能加快速度。

我认为任何好的正则表达式引擎的内部循环都已经非常优化,使用了最先进的文本匹配算法,并且经过优化可以快速完成。当表达式不是微不足道的(例如 char 类)时,祝您使用自己的代码更快。

显然存在开销,您可以按照自己的方式对内容进行硬编码并实现良好的线性加速,其他条件相同。但这对于拥有好的算法是次要的,如果您不熟悉算法复杂性的概念,请先阅读它


但是有一个关键的事情,这几乎是真正使用的一个亮点。正则表达式引擎必须正确。它必须以零误报找到它的假设。如果您获得错误匹配或错过匹配,则可能会发生不好的事情,例如数据损坏。您如何对自己的引擎有足够的信心来敢于使用它?

创造一个乐趣,当然。对于实际生产使用...嗯...


如果您可能是认真的,则需要从一开始就进行自动化测试。对于正则表达式之类的东西,您还需要对测试进行代码覆盖率分析。由于您将拥有确定性的输入和输出,没有用户输入或任何内容,因此最终您应该瞄准代码的相关部分 100% 覆盖,包括引擎和测试正则表达式的生成代码。哦,当目标是速度时,也不要忘记自动基准测试!当然,你想开始编码而不关心这些东西,这很好,但是从一开始就设置基础设施,当你测试你的代码时,把它写成自动化测试,抵制手动进行临时测试的冲动(除了作为编写自动化测试用例的步骤)。如果你做对了,你的项目成功的机会就会大得多。

对于生成的代码,LLVM可能是您想要使用的,而不是某些特定 CPU 的汇编程序。

于 2013-03-25T05:26:41.013 回答
2

您可能会从编译为机器指令的正则表达式中挤出更多的性能。这样做是否有意义完全取决于您如何摊销成本。

如果您正试图达到解析日志文件的特定目标并有一个截止日期,那么在您证明现有库(包括Google 的 RE2)对您来说太慢之前,考虑这一点可能没有意义。在确定它是瓶颈之前担心你的 RE 性能是过早优化的典型案例。

但是,如果您想将此作为一项挑战和学习练习,并且没有迫在眉睫的最后期限,那么一定要试一试。做好大量工作的准备,别忘了写很多测试用例,因为会有bug。您的正则表达式引擎将成为整个工作产品的关键基础,您不能承受它在生产中的不当行为。

祝你好运!

于 2013-03-25T05:19:22.517 回答