Почему добавление еще одной альтернативы делает мое регулярное выражение более чем в 600 раз медленнее?

Я заметил нечто странное при тестировании простого Perl script, который должен отфильтровывать имена файлов, начиная с определенных префиксов.

В принципе, я создаю регулярное выражение, подобное этому:

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

Здесь, в первоначальном тестировании, @prefixes состоит из 32-символьных шестнадцатеричных строк. Я обнаружил, что все работает красиво и гладко до 6552 префиксов — но как только я попробовал 6 553, время выполнения script подскочило более чем на 25 (от 1,8 секунды до 51 секунды)!

Я играл с ним и построил следующий тест. Первоначально я использовал 32-символьные шестнадцатеричные строки, как в моей исходной программе, но обнаружил, что если бы я сократил длину строк до 8 символов, пороговое значение переместилось выше — до 16383, на самом деле; в то время как коэффициент замедления еще больше повысился: регулярное выражение с 16383 альтернативами почти в 650 раз медленнее, чем у только с 16 382!

#!/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 & approx; 2 ¹⁶/10, заключалось в том, что это может быть какой-то произвольный лимит в движке регулярных выражений Perl, или, может быть, там может быть какой-то массив из 10-байтных структур, который был ограничено до 64 кБ или что-то в этом роде. Но тот факт, что пороговое число альтернатив зависит от их длины, делает вещи более запутанными.

(С другой стороны, это явно не только длина регулярного выражения: исходное регулярное выражение с 6553 32-байтными альтернативами было 2 + 6 553 и раз; 33 = 216,251 байта, а одно с 16383 8- байтовые альтернативы - всего 2 + 16,383 & times; 9 = 147,450 байт.)

Что вызывает этот странный прыжок в времени согласования регулярных выражений и почему это происходит в этой конкретной точке?

Ответ 1