为什么正则表达式/ [\ 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正则表达式之一:(,例如:- 正则表达式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的答案.

现在,没有优化,正则表达式引擎理论上尝试匹配"x":

• 每个可能的匹配[\w\W]+(消耗整个字符串,然后回溯1个字符,另一个......等等),和
• 主题字符串中的每个起始位置(99,999个位置).

当然,还有其他优化可以减少这个数字,但这就是它如此缓慢的原因.请注意,它会随着较长的字符串呈指数级增长.

变通

如果你不特别要求在x之前至少有一个字符,你应该使用/.*x/is,因为它在第一个位置尝试匹配后失败(优化器实际上锚定.*到文本的开头).
_{*感谢@nhahtdh提出这个问题.}

但是,对于可能出现此行为的更一般情况,提高性能的一个选项是"x"在其余之前检查(作为独立条件或在相同的正则表达式中):

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

• (?:^... )?如果在字符串的开头,只检查一次.
• (?=.*x)如果有一个x提前
• (*COMMIT)否则,它会回溯并且COMMIT是一个控制动词,使整个匹配失败.

这将运行得更快.