Я заметил something weird при тестировании простого скрипта Perl, который должен отфильтровывать имена файлов, начиная с определенных префиксов.Почему добавление еще одной альтернативы делает мое регулярное выражение более чем в 600 раз медленнее?
В принципе, я построение регулярных выражений, как это:
my $regex = join "|", map quotemeta, @prefixes;
$regex = qr/^($regex)/; # anchor the regex and precompile it
Здесь, в сценарии я первоначально испытанным, @prefixes состоит из 32-символьных шестнадцатеричных строк. Я обнаружил, что все прошло хорошо и гладко до 6 552 префиксов —, но как только я попробовал 6 553, время исполнения the script подскочило в более чем 25 (от 1,8 секунды до 51 секунды)!
Я играл с ним и построил следующий ориентир. Первоначально я использовал 32-символьные шестнадцатеричные строки, как в моей оригинальной программе, но обнаружил, что если бы я сократил длину строк до 8 символов, пороговое значение переместилось выше — в 16383, фактически —, в то время как коэффициент замедления резко вырос еще выше: регулярное выражение с 16383 альтернативами почти в 650 раз медленнее, чем у только с 16382!
#!/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% --
Примечание разницы скорости, 64703%.
Моя первоначальная догадка, основанная на численном совпадении 6553 & approx; 2 /10, было то, что это могло быть своего рода произвольным пределом внутри движка регулярных выражений Perl, или, может быть, там может быть какой-то массив из 10-байтных структур, который был ограничен 64 КБ, или что-то. Но тот факт, что пороговое число альтернатив зависит от их длины, делает вещи более запутанными.
(С другой стороны, это явно не только длина регулярного выражения: исходное регулярное выражение с 6 553 32-байтовыми альтернативами было 2 + 6 553 × 33 = 216,251 байта, а одно с 16383 8- байтовые альтернативы - это только 2 + 16,383 × 9 = 147,450 байт.)
Что вызывает этот странный прыжок в времени согласования регулярных выражений и почему это происходит в этой конкретной точке?
Другим возможным фактором (т. Е. Может быть не весь рисунок) является структура данных регулярного выражения, которая становится достаточно большой, чтобы они больше не вписывались в ваш кеш L1/L2/L3 ... – twalberg
Хотя я чувствую, что этот вопрос очень хорошо заслуживает ответа, я также чувствую, что для практических целей вы должны использовать поиск по карте вместо регулярного выражения элемента 16k. –
@ Mr.Llama: Конечно. Первоначальный сценарий был около 500 альтернатив, для которых решение регулярных выражений отлично работает. Мне было просто интересно, как это будет масштабироваться. –