为什么在这个Perl正则表达式中，`\s+`比`\s\s*`快那么多？

Question

为什么在这个Perl正则表达式中，`\s+`比`\s\s*`快那么多？

56

为什么将\s*(甚至\s\s*)替换为\s+会显著提升此输入的速度？

use Benchmark qw(:all);
$x=(" " x 100000) . "_\n";
$count = 100;
timethese($count, {
    '/\s\s*\n/' => sub { $x =~ /\s\s*\n/ },
    '/\s+\n/' => sub { $x =~ /\s+\n/ },
});

在线版本链接

我注意到在我的代码中，一个慢速的正则表达式s/\s*\n\s*/\n/g - 当给定一个450KB的输入文件，其中有大量的空格和一些非空格字符，以及最后一个换行符时，该正则表达式会挂起并永远无法完成。

我本能地用 s/\s+\n/\n/g; s/\n\s+/\n/g; 替换了正则表达式并且一切都好了。

但为什么它会快那么多呢？经过使用 re Debug => "EXECUTE" 我注意到 \s+ 版本被优化为只运行一次: http://pastebin.com/0Ug6xPiQ

Matching REx "\s*\n" against "       _%n"
Matching stclass ANYOF{i}[\x09\x0a\x0c\x0d ][{non-utf8-latin1-all}{unicode_all}] against "       _%n" (9 bytes)
   0 <> <       _%n>         |  1:STAR(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   1 < > <      _%n>         |  1:STAR(3)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   2 <  > <     _%n>         |  1:STAR(3)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   3 <   > <    _%n>         |  1:STAR(3)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   4 <    > <   _%n>         |  1:STAR(3)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   5 <     > <  _%n>         |  1:STAR(3)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   6 <      > < _%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   8 <       _> <%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
   8 <       _> <%n>         |  3:  EXACT <\n>(5)
   9 <       _%n> <>         |  5:  END(0)
Match successful!

Matching REx "\s+\n" against "       _%n"
Matching stclass SPACE against "       _" (8 bytes)
   0 <> <       _%n>         |  1:PLUS(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...

我知道如果没有换行符，Perl 5.10+将立即使正则表达式失败（而不运行它）。我怀疑它是使用换行符的位置来减少搜索量。对于上述所有情况，它似乎巧妙地减少了涉及回溯的工作量（通常/\s*\n/与一串空格的字符串相对，需要指数时间）。有人能解释为什么\s+版本如此更快吗？

另外请注意，\s*?并不会提供任何加速。

- rjh

8

\s 匹配 \n 也不太有用。一个不是换行符的空白字符是 [^\S\n]，或者你可以使用 "horizontal whitespace" \h。 - Borodin

你可以将比较范围缩小到 /\s*\n/ 和 /\s+\n/ 查看实时演示。请注意，只有在字符串不匹配的情况下才会更快。如果匹配成功，则需要相同的时间。 - Thomas Ayoub

@ThomasAyoub 我认为这并没有缩小比较范围。\s\s* 应该与 \s+ 相同，而你发布的两个正则表达式是不同的。然而，我同意即使在你发布的这两个正则表达式之间的性能差异也令人惊讶！ - rjh

@Borodin [^\S\n]*\n 也很慢... - rjh

由于最近的停机事件（http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016），这似乎非常有趣。 - rjh

4个回答

20

当模式的开头有“plus”节点（例如\s+）且该节点无法匹配时，正则表达式引擎会跳到失败点并尝试再次匹配；另一方面，对于\s*，引擎每次只前进一个字符。

Yves Orton在这里很好地解释了这种优化：

引擎具有两种启动类优化模式：“尝试每个有效的起始位置”（doevery）和“翻转模式”（!doevery），在其中它仅尝试序列中的第一个有效起始位置。

考虑/(\d+)X/和字符串“123456Y”，现在我们知道如果匹配“123456”后未能匹配X，那么在匹配“23456”后我们也将无法匹配（假设没有禁用优化的恶意技巧存在），因此我们知道可以向前跳过直到检查/失败/，然后才开始寻找真正的匹配。这是翻转模式。 /\s+/触发翻转模式；/\s*/、/\s\s*/和/\s\s+/则不会。这种优化无法应用于像\s*这样的“星号”节点，因为它们可以匹配零个字符，因此序列中的某一点上的失败不能说明后面相同序列的失败。

您可以在每个正则表达式的调试输出中看到这一点。我用^突出显示了跳过的字符。比较一下这个（每次跳过四个字符）：

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d+x/'
   ...
   0 <> <123 456 78>         |  1:PLUS(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:PLUS(3)
      ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:PLUS(3)
         ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...

跳过一个或两个字符以到达此处：

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d*x/'
   ...
   0 <> <123 456 78>         |  1:STAR(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   1 <1> <23 456 789>        |  1:STAR(3)
      ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   2 <12> <3 456 789 >       |  1:STAR(3)
       ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:STAR(3)
        ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   5 <123 4> <56 789 x>      |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   6 <23 45> <6 789 x>       |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:STAR(3)
           ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   9 <23 456 7> <89 x>       |  1:STAR(3)
             ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
  10 <23 456 78> <9 x>       |  1:STAR(3)
              ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
  12 <23 456 789 > <x>       |  1:STAR(3)
               ^^
                                  POSIXD[\d] can match 0 times out of 2147483647...
  12 <23 456 789 > <x>       |  3:  EXACT <x>(5)
  13 <23 456 789 x> <>       |  5:  END(0)

请注意，优化不适用于/\s\s+/，因为\s+不在模式的开头。尽管/\s\s+/（逻辑上等同于/\s{2,}/）和/\s\s*/（逻辑上等同于/\s+/）可能都可以进行优化；不过，询问perl5-porters是否值得这样做可能是有意义的。

_{如果您感兴趣，可以通过设置PREGf_SKIP标志来启用“翻转翻转模式”，当正则表达式被编译时。请参阅regcomp.c的第7344行和第7405行以及regexec.c的第1585行中的代码，这些代码都来自于5.24.0版本的源代码。}

- ThisSuitIsBlackNot

谢谢，这正是我在寻找的答案（实际上深入挖掘了C源代码并解释了优化）。非常感谢！ - rjh

1

鉴于http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016，这似乎尤为重要！ - rjh

如果 R+ 比 RR 更好，为什么正则表达式编译器不在 AST 级别识别并替换 RR* 为 R+ 呢？ - Kaz

@Kaz 我在最后一段中提到了这一点。虽然可能可以添加该优化，但这需要 Perl 维护者付出很少的努力来实现。 - ThisSuitIsBlackNot

15

\s+\n 要求在 \n 前面的字符是一个 空格。

使用 use re qw(debug) 后，编译器会建立一个由已知数量的空格组成的字符串，直到遇到第一个 \n 的子字符串，然后检查该固定长度、仅包含空格的子字符串是否与剩余输入匹配。当搜索到 _ 时则会失败。无论输入中有多少个 _\n，都只需检查一次（根据调试输出）。

从这个角度来看，这几乎是可以预期的优化，利用了一个相当特定的搜索模式，并侥幸找到匹配的输入。但与其他引擎比较时，明显没有进行这种类型的分析。

对于 \s*\n 不是这样的。一旦找到 \n 并且前一个字符不是空格，搜索就不会失败，因为 \s* 允许没有任何字符。也没有固定长度的子字符串，只能采用回溯的方式尝试匹配。

- zdim

/\s\s*?\n/ 会受到回溯的影响吗？ - Zaid

2

@Zaid：在回溯方面，贪婪模式和非贪婪模式是相同的。唯一的区别是，贪婪模式将尽可能地开始为长，并缩短直到其余的正则表达式匹配，而非贪婪模式将尽可能地开始为短，并扩展直到其余的正则表达式匹配。 - Borodin

调试模式的输出表明引擎实际上是从左到右匹配\s*或\s+，而不是检查\n前面是否有_。我已经在源代码中添加了额外的日志记录，很明显那里有一个循环。 - nhahtdh

谢谢您的评论 - 我没有意识到以上内容的表达方式。我曾经怀疑它可能会从后往前检查并最初写了这个，但是一旦我查看了re=debug输出，我发现它确实是从左到右进行匹配（然后改变了帖子）。我的意思是它有一个固定长度的只包含空格的字符串（直接进行跟踪），它会碰到_。存在一个固定长度的“条棒”非常重要，所有这些都很快。（此外，此输入非常特殊。）我认为这已经足够优化了。我应该重新表达那句话，谢谢。 - zdim

7

我不确定正则表达式引擎的内部工作原理，但看起来它似乎没有意识到\s+与\s\s*在某种程度上是一样的，因为在第二个表达式中它会匹配一个空格然后试图匹配越来越多的空格，而在第一个表达式中，它会立即得出没有匹配的结论。使用use re qw( Debug );命令输出清楚地显示了这一点，使用了一个更短的字符串:test_re.pl

#!/usr/bin/env perl
use re qw(debug);

$x=(" " x 10) . "_\n";
print '-'x50 . "\n";
$x =~ /\s+\n/;
print '-'x50 . "\n";
$x =~ /\s\s*\n/;
print '-'x50 . "\n";

输出

Compiling REx "\s+\n"
Final program:
    1: PLUS (3)
    2:   SPACE (0)
    3: EXACT <\n> (5)
    5: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE plus minlen 2
Compiling REx "\s\s*\n"
Final program:
    1: SPACE (2)
    2: STAR (4)
    3:   SPACE (0)
    4: EXACT <\n> (6)
    6: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE minlen 2
--------------------------------------------------
Guessing start of match in sv for REx "\s+\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:PLUS(3)
                                  SPACE can match 10 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Guessing start of match in sv for REx "\s\s*\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s\s*\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:SPACE(2)
   1 < > <         _>        |  2:STAR(4)
                                  SPACE can match 9 times out of 2147483647...
                                  failed...
   1 < > <         _>        |  1:SPACE(2)
   2 <  > <        _>        |  2:STAR(4)
                                  SPACE can match 8 times out of 2147483647...
                                  failed...
   2 <  > <        _>        |  1:SPACE(2)
   3 <   > <       _%n>      |  2:STAR(4)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   3 <   > <       _%n>      |  1:SPACE(2)
   4 <    > <      _%n>      |  2:STAR(4)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   4 <    > <      _%n>      |  1:SPACE(2)
   5 <     > <     _%n>      |  2:STAR(4)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   5 <     > <     _%n>      |  1:SPACE(2)
   6 <      > <    _%n>      |  2:STAR(4)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   6 <      > <    _%n>      |  1:SPACE(2)
   7 <       > <   _%n>      |  2:STAR(4)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   7 <       > <   _%n>      |  1:SPACE(2)
   8 <        > <  _%n>      |  2:STAR(4)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   8 <        > <  _%n>      |  1:SPACE(2)
   9 <         > < _%n>      |  2:STAR(4)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   9 <         > < _%n>      |  1:SPACE(2)
  10 <          > <_%n>      |  2:STAR(4)
                                  SPACE can match 0 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Freeing REx: "\s+\n"
Freeing REx: "\s\s*\n"

- xxfelixxx

我已经在我的问题中附上了类似的调试输出，但感谢您的关注。我对它发生的原因很感兴趣 :) - rjh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas Ayoub · Accepted Answer

首先，即使结果正则表达式的含义不同，让我们将正则表达式简化为\s*0和\s+0，并使用(" " x 4) . "_0"作为输入。对于怀疑者，您可以在这里看到延迟仍然存在。

现在考虑以下代码：

$x = (" " x 4) . "_ 0";
$x =~ /\s*0/; # The slow line 
$x =~ /\s+0/; # The fast line

使用use re debugcolor;命令进行深入挖掘，我们可以得到以下输出结果：

Guessing start of match in sv for REx "\s*0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 0 check_at: 5 s: 0 endpos: 6 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
   0 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
   1 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 3 times out of 2147483647...
                                  failed...
   2 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 2 times out of 2147483647...
                                  failed...
   3 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 1 times out of 2147483647...
                                  failed...
   5 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 0 times out of 2147483647...
   5 <    _0>|  3:  EXACT <0>(5)
   6 <    _0>|  5:  END(0)
Match successful!

-----------------------

Guessing start of match in sv for REx "\s+0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 1 check_at: 5 s: 0 endpos: 5 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes)
   0 <    _0>|  1:PLUS(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed

Perl似乎被优化为失败。它首先查找常量字符串(只消耗O(N)的时间)。在这里，它会查找0：在偏移量5处发现浮动子字符串“0”... 然后，它将从正则表达式的变量部分开始，分别使用\s*和\s+与整个最小字符串进行匹配检查：

Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes) # Only 5 bytes because there should be at least 1 "\s" char

在这之后，它会寻找第一个符合 stclass 要求的位置，在这里是位置0。

\s*0：
- 从0开始，找到4个空格，然后失败；
- 从1开始，找到3个空格，然后失败；
- 从2开始，找到2个空格，然后失败；
- 从3开始，找到1个空格，然后失败；
- 从4开始，找到0个空格，然后不失败；
- 找到一个精确的 0
\s+0：
- 从0开始，找到4个空格，然后失败。由于没有匹配最小空格数，正则表达式立即失败。

如果你想在Perl正则表达式优化方面玩得开心，可以考虑以下正则表达式/ *\n和/ * \n。乍一看，它们看起来相同，意思也相同...但是如果你对(" " x 40000) . "_\n"运行它们，第一个将检查所有可能性，而第二个将寻找" \n"并立即失败。

在普通的、未经优化的正则表达式引擎中，这两个正则表达式都可能导致灾难性的回溯，因为它们需要在模式被推进时重试。然而，在上面的例子中，第二个不会在Perl中失败，因为它已经被优化为查找浮动子串"0%n"。

你可以在Jeff Atwood的博客上看到另一个例子。

还要注意，问题不在于\s的考虑，而是任何使用xx*而不是x+的模式，参见包含0s的示例和正则表达式爆炸性量词。

通过这样更简短的示例，行为是“可查找的”，但如果你开始使用复杂的模式，很难发现，例如：正则表达式挂起程序（100％ CPU使用率）。