为什么添加一个替代品使我的正则表达式慢600多倍？

Question

在测试一个简单的Perl脚本时,我发现了一些奇怪的东西,它应该过滤掉以某些前缀开头的文件名.

基本上,我正在构建一个这样的正则表达式:

my $regex = join "|", map quotemeta, @prefixes;
$regex = qr/^($regex)/;   # anchor the regex and precompile it

这里,在我最初测试的场景中,@prefixes由32个字符的十六进制字符串组成.我发现一切都运行良好而顺畅,最多可达6,552个前缀 - 但是一旦我尝试了6,553,脚本的执行时间就会超过25(从1.8秒到51秒)!

我玩了它,并构建了以下基准.我最初使用32个字符的十六进制字符串,就像在我的原始程序中一样,但发现如果我将字符串的长度减少到只有8个字符,则阈值移动得更高 - 实际上是16,383 - 而减速因子得到了显着的提升更高的是:有16,383个替代品的正则表达式比只有16,382个的正则表达式慢近650倍!

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(timethese cmpthese);

my $count = shift || 10;

our @items = map unpack("H8", pack "V", $_), 0..99999;

our $nA = 16382; our $reA = join "|", @items[1 .. $nA];
our $nB = 16383; our $reB = join "|", @items[1 .. $nB];

$_ = qr/^($_)/ for $reA, $reB;  # anchor and compile regex

my $results = timethese( $count, {
    $nA => q{ our (@items, $nA, $reA); $nA == grep /$reA/, @items or die; },
    $nB => q{ our (@items, $nB, $reB); $nB == grep /$reB/, @items or die; },
} );
cmpthese( $results );

以下是使用Perl(v5.18.2)在我的笔记本电脑上运行此基准测试的结果:

Benchmark: timing 10 iterations of 16382, 16383...
     16382:  2 wallclock secs ( 1.79 usr +  0.00 sys =  1.79 CPU) @  5.59/s (n=10)
     16383: 1163 wallclock secs (1157.28 usr +  2.70 sys = 1159.98 CPU) @  0.01/s (n=10)
      s/iter  16383  16382
16383    116     --  -100%
16382  0.179 64703%     --

注意64,703%的速度差异.

我最初的预感,基于数值巧合的是,6553≈2 ^16个/10,是这可能已经某种类型的任意限制Perl的正则表达式引擎中,也许有可能有某种10的阵列字节结构限制为64 kB,或者​​其他东西.但是,替代品的阈值数量取决于它们的长度这一事实使事情变得更加混乱.

(另一方面,它显然也不仅仅是正则表达式的长度;原始正则表达式为6,553个32字节替代方案是2 + 6,553×33 = 216,251字节长,而具有16,383个8字节替代方案的那个只有2 + 16,383×9 = 147,450字节长.)

在正则表达式匹配时间内导致这种奇怪跳跃的原因是什么？为什么会在特定点发生？

Answer 1

很长一段时间,perl的TRIE优化还没有应用于正则表达式的初始编译产生longjmp而不是jmp(我认为)指令(这取决于交替的数量和所涉及的字符串的总长度以及其他是什么(早期？)在正则表达式中).

看看之间的区别:

perl -we'use re "debug"; qr/@{[join"|","a".."afhd"]}/'

和

perl -we'use re "debug"; qr/@{[join"|","a".."afhe"]}/'

您可以将交替分解为较小的块并单独预编译,例如(??{$rxa})|(??{$rxb})|(??{$rxc}).