regex - 为什么正则表达式/[\w\W] + x/i运行起来会非常慢？

Question

尝试:

time perl -E '$x="a" x 100000; $x =~ /[\w\W]+x/i'  

将运行很长时间(在我的笔记本上20秒)。没有/i，例如

time perl -E '$x="a" x 100000; $x =~ /[\w\W]+x/' 

在0.07秒内完成。

不管正则表达式[\w\W]没有多大意义，这种巨大的差异使我感到惊讶。

为什么会有如此大的差异？

编辑

更准确地说:

$ time perl -E '$x="a" x 100000; $x =~ /[\w\W]+x/i'  

real    0m19.479s
user    0m19.419s
sys 0m0.038s

我的perl

Summary of my perl5 (revision 5 version 20 subversion 3) configuration:

  Platform:
    osname=darwin, osvers=15.0.0, archname=darwin-2level
    uname='darwin nox.local 15.0.0 darwin kernel version 15.0.0: sat sep 19 15:53:46 pdt 2015; root:xnu-3247.10.11~1release_x86_64 x86_64 '
    config_args='-Dprefix=/opt/anyenv/envs/plenv/versions/5.20.3 -de -Dusedevel -A'eval:scriptdir=/opt/anyenv/envs/plenv/versions/5.20.3/bin''
    hint=recommended, useposix=true, d_sigaction=define
    useithreads=undef, usemultiplicity=undef
    use64bitint=define, use64bitall=define, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cc', ccflags ='-fno-common -DPERL_DARWIN -fno-strict-aliasing -pipe -fstack-protector -I/opt/local/include',
    optimize='-O3',
    cppflags='-fno-common -DPERL_DARWIN -fno-strict-aliasing -pipe -fstack-protector -I/opt/local/include'
    ccversion='', gccversion='4.2.1 Compatible Apple LLVM 7.0.0 (clang-700.1.76)', gccosandvers=''
    intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16
    ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='env MACOSX_DEPLOYMENT_TARGET=10.3 cc', ldflags =' -fstack-protector -L/opt/local/lib'
    libpth=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/clang/7.0.0/lib /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib /usr/lib /opt/local/lib
    libs=-lpthread -lgdbm -ldbm -ldl -lm -lutil -lc
    perllibs=-lpthread -ldl -lm -lutil -lc
    libc=, so=dylib, useshrplib=false, libperl=libperl.a
    gnulibc_version=''
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=bundle, d_dlsymun=undef, ccdlflags=' '
    cccdlflags=' ', lddlflags=' -bundle -undefined dynamic_lookup -L/opt/local/lib -fstack-protector'


Characteristics of this binary (from libperl): 
  Compile-time options: HAS_TIMES PERLIO_LAYERS PERL_DONT_CREATE_GVSV
                        PERL_HASH_FUNC_ONE_AT_A_TIME_HARD PERL_MALLOC_WRAP
                        PERL_NEW_COPY_ON_WRITE PERL_PRESERVE_IVUV
                        PERL_USE_DEVEL USE_64_BIT_ALL USE_64_BIT_INT
                        USE_LARGE_FILES USE_LOCALE USE_LOCALE_COLLATE
                        USE_LOCALE_CTYPE USE_LOCALE_NUMERIC USE_PERLIO
                        USE_PERL_ATOF
  Locally applied patches:
    Devel::PatchPerl 1.38
  Built under darwin
  Compiled at Oct 28 2015 14:46:19
  @INC:
    /opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/site_perl/5.20.3/darwin-2level
    /opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/site_perl/5.20.3
    /opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/5.20.3/darwin-2level
    /opt/anyenv/envs/plenv/versions/5.20.3/lib/perl5/5.20.3
    .

从问题的背景来看:实际代码将字符串与大量正则表达式(某种反垃圾邮件)匹配，因此我无法可靠地手动检查正则表达式数据库。真正的代码片段是

sub docheck {
    ...
    ...
    foreach my $regex (@$regexs) {
        if ( $_[0] =~ /$regex/i ) {

而[\w\W]+是10k正则表达式之一:(，例如:[\w\W]+medicine\.netfirms\.com-regex-DB可能需要清理-但...您知道:)

现在，代码已更改:

sub docheck {
    ...
    my $str = lc($_[0]);
    foreach my $regex (@$regexs) {
        if ( $str =~ /$regex/ ) {

所以避免/i。

Answer 1

TL; DR
在第二种情况下，优化器非常智能，并且意识到
字符串中没有"x"，因此无法进行匹配，并且会更早失败。
但是，对于/i情况，同时测试两个
大写和小写x，所以它继续进行并尝试匹配整个正则表达式。

调试
尽管我无法重现如此大的性能差异，但是针对区分大小写的匹配触发了优化。
让我们以'debug'模式运行它:
代码

use re 'debug';
$x="a" x 100000;
$x =~ /[\w\W]+x/;

您还可以将-Mre=debug添加到perl调用中。

输出

Compiling REx "[\w\W]+x"
Final program:
   1: PLUS (13)
   2:   ANYOF[\x{00}-\x{7F}][{non-utf8-latin1-all}{unicode_all}] (0)
  13: EXACT <x> (15)
  15: END (0)
floating "x" at 1..9223372036854775807 (checking floating) stclass ANYOF[\x{00}-\x{7F}][{non-utf8-latin1-all}{unicode_all}] plus minlen 2 
Matching REx "[\w\W]+x" against "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"...
Intuit: trying to determine minimum start position...
  Did not find floating substr "x"...
Match rejected by optimizer
Freeing REx: "[\w\W]+x"

并注意最后一部分:

Intuit: trying to determine minimum start position...
  Did not find floating substr "x"...
Match rejected by optimizer

优化器尝试查找"x"的第一个匹配项，由于找不到它，因此在正则表达式引擎甚至尝试匹配之前就拒绝匹配。
Perl正则表达式经过了优化，希望尽早失败而不是成功。

慢速情况
我无法在终端上重现相同的行为(Perl v5.20.2)，但在以后的优化中失败了，这可能是由于特定于版本的差异所致。但是，在这种情况下不会进行不区分大小写的"x"的优化。
不会触发此优化，因为它有超过一种匹配主题的可能性(小写的"x"和大写的"X")。

如果您对此优化内部知识感兴趣，请检查ThisSuitIsBlackNot's answer。

现在，在没有优化的情况下，正则表达式引擎理论上会尝试将"x"匹配为:

和

一起在[\w\W]+中进行所有可能的匹配(使用整个字符串，然后回溯1个字符，等等)。

主题字符串中的每个起始位置(99,999个位置)。

当然，还有其他优化措施可以减少此数量，但这就是为什么它这么慢的原因。请注意，它随着字符串的增加呈指数增长。
解决方法
如果您不特别要求x之前至少要有一个字符，则应使用/.*x/is，因为在第一个位置尝试匹配后它会失败(优化器实际上将.* anchor 定到文本的开头)。
*感谢@nhahtdh提出了这一点。
但是，对于可能出现此行为的更一般的情况，一种提高性能的选项是在其余代码之前检查"x"(作为独立条件或在同一正则表达式中):

$x =~ /(?:^(*COMMIT)(?=.*x))?[\w\W]+x/is;

(?:^ ... )?如果在字符串开头，则仅检查一次。

(?=.*x)如果前面有一个x

(*COMMIT)否则，它会回溯，并且 COMMIT 是控制动词，会使整个匹配失败。

这将运行得更快。