为什么在这个Perl正则expression式里，\ s +`比`s \ s *`快得多？
为什么用\s+replace\s* （甚至\s\s* ）会导致此input的加速？
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/ }, });
链接到在线版本
我注意到一个缓慢的正则expression式s/\s*\n\s*/\n/g在我的代码中 – 当给出一个450KB的input文件，包含大量的空格和几个非空格在这里和最后一个换行符结束 – 正则expression式挂起，并没有完成。
我用s/\s+\n/\n/g; s/\n\s+/\n/g;直观地replace了正则expression式s/\s+\n/\n/g; s/\n\s+/\n/g; 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 +将立即失败正则expression式（不运行它）如果换行符不存在。 我怀疑它正在使用换行符的位置来减lesssearch量。 对于上面的所有情况，似乎巧妙地减less了涉及到的回溯（通常是/\s*\n/针对一串空格需要指数时间）。 任何人都可以提供洞察，为什么\s+版本是如此之快？
还要注意\s*? 不提供任何加速。
当一个模式开始处有一个“加号”节点（例如\s+ ）且节点不匹配时，正则expression式引擎会跳转到失败点并再次尝试; 与\s*相反，引擎一次只能提前一个字符。
Yves Orton 在这里很好地解释了这个优化：
开始类优化有两种模式，“尝试每个有效的开始位置”（doevery）和“触发器模式”（！doevery），它只在第一个有效的开始位置顺序。
考虑到/（\ d +）X /和string“123456Y”，现在我们知道如果我们在匹配“123456”后匹配X，那么在“23456”之后我们也将无法匹配（假设没有诡计，无论如何禁用优化），所以我们知道我们可以跳过，直到检查/失败/只开始寻找一个真正的匹配。 这是触发器模式。
/\s+/触发器触发器模式; /\s*/ ， /\s\s*/和/\s\s+/不。 这种优化不能应用于像\s*那样的“星形”节点，因为它们可以匹配零个字符，所以在一个序列中的一个点上的失败并不表示以后以相同的顺序失败。
你可以在debugging输出中看到每个正则expression式。 我用^标出了跳过的字符。 比较一下（一次跳过四个字符）：
$ 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+/ ）可能会被优化。 向每个搬运工询问是否值得这个努力是有意义的。
如果你有兴趣，可以通过在正则expression式编译时设置PREGf_SKIP标志来启用“触发器模式”。 请参阅regcomp.c中第7344和7405行的代码和5.24.0源代码中regexec.c的第1585行。
首先，即使得到的正则expression式不会保持相同的含义，让我们将正则expression式减less到\s*0和\s+0并使用(" " x 4) . "_0" (" " x 4) . "_0"作为input。 对于怀疑者，你可以在这里看到，滞后仍然存在。
现在让我们考虑下面的代码：
$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似乎对失败进行了优化 。 它将首先查找常量string（只消耗O（N））。 在这里，它会查找0 ： Found floating substr "0" at offset 5...
然后，它将从正则expression式的variables部分开始，相对于整个最小string，分别是\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开始，find4个空格然后失败;
- 从1开始，find3个空格然后失败;
- 从2开始，find2个空格然后失败;
- 从3开始，find1个空格然后失败;
- 从4开始，find0个空格然后不失败 ;
- find一个确切的
0
-
\s+0：- 从0开始，find4个空格然后失败。 由于空格的最小数量不匹配，正则expression式立即失败。
如果你想用Perl正则expression式优化，你可以考虑下面的正则expression式/ *\n和/ * \n 。 乍一看，它们看起来是一样的，具有相同的含义…但是，如果你运行它(" " x 40000) . "_\n" (" " x 40000) . "_\n"第一个将检查所有可能性，而第二个将查找" \n"并立即失败。
在一个香草，非优化的正则expression式引擎，这两个正则expression式可以导致灾难性的回溯，因为他们需要重试模式，因为它颠簸。 然而，在上面的例子中，第二个不会因为Perl而失败，因为它已经被优化以find floating substr "0%n"
你可以在Jeff Atwood的博客上看到另一个例子。
还要注意的是，这个问题不是考虑的问题，而是使用xx*而不是x+任何模式，请参见使用0的示例，也使用正则expression式爆炸性的量词
用这么简单的例子，行为是“可find的”，但是如果你开始玩复杂的模式，那么很难发现，例如： 正则expression式挂起程序（100％CPU使用率）
\s+\n要求\s+\n之前的字符是一个SPACE 。
根据use re qw(debug)的使用，编译规定它需要一个已知数目的空格的直接string，直到在input中首先检查的子字符\n 。 然后，它检查固定长度的仅空的子string对input的其余部分，失败，因为它。 无论input有多less空间，都可以检查。 （当有更多_\n每个被发现直接失败，每个debugging输出。）
这样看待它，这是一个你几乎期望的优化，利用一个相当具体的search模式，并用这个input。 除了与其他引擎相比，显然不做这种分析。
与\s*\n不是这种情况。 一旦find\n并且前一个字符不是空格，search就没有失败，因为\s*不允许任何内容（零个字符）。 也没有固定长度的子串，而且在回溯游戏中。
我不确定正则expression式引擎的内部结构，但是它看起来好像不能识别\s+在某种程度上与 \s\s* ，因为在第二个匹配的空间中，然后尝试以匹配日益增长的空间数量，而在第一个，它立即得出结论，没有匹配。
输出使用use re qw( Debug ); 清楚地显示了这一点，使用更短的string：
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"
