Почему регулярное выражение /[\ w\W] + x/i будет чрезвычайно медленным для запуска?

Ответ 1

TL; DR

Во втором случае оптимизатор довольно умный и реализует там no "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" и, поскольку он не может его найти, он отклоняет соответствие до того, как движок regex даже попытается его выполнить.

Регулятор Perl оптимизирован для того, чтобы скорее сбой как можно раньше, чем для успеха.

Медленный случай

Я не могу воспроизвести одно и то же поведение на моем конце (Perl v5.20.2), он не работает при более поздней оптимизации, вероятно, из-за различий в версии. Однако оптимизация для нечувствительности к регистру "x" в этом случае не происходит.

Эта оптимизация не запускается, поскольку она имеет более одной возможности для совпадения объекта (как в нижнем регистре "x", так и в верхнем регистре "x").

• Отметьте ThisSuitIsBlackNot ответ, если вы заинтересованы в этой оптимизации.

Теперь, без оптимизации, двигатель регулярных выражений теоретически пытается сопоставить "x" для:

• каждое возможное совпадение в [\w\W]+ (потребляющее всю строку, затем обратное отслеживание 1 char и другое... и т.д.) и
• каждое исходное положение в строке темы (99 999 позиций).

Конечно, есть и другие оптимизации, которые уменьшают это число, но почему это так медленно. Обратите внимание, что он увеличивается экспоненциально с более длинными строками.

Работа вокруг

Если вам не требуется, чтобы перед x был хотя бы один символ, вы должны использовать /.*x/is, поскольку он не работает после попытки совпадения в первой позиции (оптимизатор фактически привязывает .* к началу текст).
_{* Благодаря @nhahtdh для этого.}

Однако для более общего случая, когда такое поведение может возникнуть, одним из вариантов повышения производительности является проверка для "x" перед остальными (либо как независимое условие, либо в том же регулярном выражении):

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

• (?:^... )? Проверяет только один раз, если в начале строки.
• (?=.*x) Если есть x впереди
• (*COMMIT) В противном случае он возвращается и COMMIT - это контрольный глагол, который приводит к сбою всего матча.

Это будет работать намного быстрее.

Ответ 2

Мариано в точности правка: разница в производительности - благодаря оптимизатору. Чтобы узнать, почему оптимизатор запускается в одном случае, но не другой, требуется погружение в исходный код Perl.

Большая часть кода оптимизатора опирается на две части данных о шаблоне:

• самая длинная фиксированная подстрока и

• самая длинная плавающая подстрока

Это объясняется в комментариях в regcomp.c в источнике Perl:

Во время оптимизации мы... [получите] информацию о     какие строки ДОЛЖНЫ появляться в шаблоне. Мы ищем самый длинный     строка, которая должна отображаться в фиксированном месте, и мы ищем     длинная строка, которая может отображаться в плавающей позиции. Так, например,     в шаблоне:

/FOO[xX]A.*B[xX]BAR/

Оба "FOO" и "A" являются фиксированными строками. Оба "B" и "BAR" являются плавающими     (потому что они следуют за конструкцией. *). study_chunk будет идентифицировать     как FOO, так и BAR как самые длинные фиксированные и плавающие строки соответственно.

(от Perl 5.22.0)

Почему оптимизатор использует эти подстроки? Потому что гораздо проще быстро выполнить сбой, когда вы можете выполнять простые сравнения строк и длины, вместо того, чтобы запускать полный механизм регулярных выражений.

Итак, с /.+x/ имеем:

• самая длинная фиксированная подстрока: none
• самая длинная плавающая подстрока: x

И с /.+x/i мы имеем:

• самая длинная фиксированная подстрока: none
• самая длинная плавающая подстрока: none (сложение флагов означает, что мы больше не работаем с простой литеральной строкой)

Теперь, когда шаблон скомпилирован, который содержит литеральную строку (фиксированную или плавающую), в скомпилированном регулярном выражении устанавливается специальный флаг RXf_USE_INTUIT. Когда выполняется регулярное выражение, этот флаг запускает процедуру оптимизации под названием re_intuit_start(), которая находится в regexec.c:

/* re_intuit_start():
 *
 * Based on some optimiser hints, try to find the earliest position in the
 * string where the regex could match.
 *
 * ...
 *
 * The basic idea of re_intuit_start() is to use some known information
 * about the pattern, namely:
 *
 *   a) the longest known anchored substring (i.e. one that at a
 *      constant offset from the beginning of the pattern; but not
 *      necessarily at a fixed offset from the beginning of the
 *      string);
 *   b) the longest floating substring (i.e. one that not at a constant
 *      offset from the beginning of the pattern);
 *   c) Whether the pattern is anchored to the string; either
 *      an absolute anchor: /^../, or anchored to \n: /^.../m,
 *      or anchored to pos(): /\G/;
 *   d) A start class: a real or synthetic character class which
 *      represents which characters are legal at the start of the pattern;
 *
 * to either quickly reject the match, or to find the earliest position
 * within the string at which the pattern might match, thus avoiding
 * running the full NFA engine at those earlier locations, only to
 * eventually fail and retry further along.

С /.+x/ запускается re_intuit_start() и выполняет поиск строки, которая соответствует самой длинной плавающей подстроке (x). Когда ему не удается найти какой-либо x s, полное совпадение может быть немедленно отклонено.

С /.+x/i, с другой стороны, re_intuit_start() никогда не срабатывает, поэтому мы теряем свою неудачную оптимизацию.