Как повысить производительность регулярного выражения .NET?

Question

У меня есть регулярное выражение, которое анализирует (очень небольшое) подмножество языка шаблонов Razor. Недавно я добавил еще несколько правил в регулярное выражение, которые значительно замедлили его выполнение. Мне интересно: существуют ли определенные регулярные выражения, которые, как известно, медленны? Существует ли реструктуризация шаблона, который я использую, чтобы поддерживать читаемость и, тем не менее, повысить производительность? Примечание. Я подтвердил, что это повышение производительности происходит после компиляции.

Вот картина:

new Regex(
       @" (?<escape> \@\@)" 
      + @"| (?<comment> \@\* (([^\*]\@) | (\*[^\@]) | .)* \*\@)" 
      + @"| (?<using> \@using \s+ (?<namespace> [\w\.]+) (\s*;)?)" 

      // captures expressions of the form "foreach (var [var] in [expression]) { <text>" 
/* ---> */  + @"| (?<foreach> \@foreach \s* \(\s* var \s+ (?<var> \w+) \s+ in \s+ (?<expressionValue> [\w\.]+) \s* \) \s* \{ \s* <text>)" 

      // captures expressions of the form "if ([expression]) { <text>" 
/* ---> */  + @"| (?<if> \@if \s* \(\s* (?<expressionValue> [\w\.]+) \s* \) \s* \{ \s* <text>)" 

      // captures the close of a razor text block 
      + @"| (?<endBlock> </text> \s* \})" 

      // an expression of the form @([(int)] a.b.c) 
      + @"| (?<parenAtExpression> \@\(\s* (?<castToInt> \(int\)\s*)? (?<expressionValue> [\w\.]+) \s* \))" 
      + @"| (?<atExpression> \@ (?<expressionValue> [\w\.]+))" 
/* ---> */  + @"| (?<literal> ([^\@<]+|[^\@]))", 
      RegexOptions.IgnorePatternWhitespace | RegexOptions.Multiline | RegexOptions.ExplicitCapture | RegexOptions.Compiled); 

/* ---> */указывает на новые "правила", которые вызвали замедление.

Answer 1

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

Некоторые мысли:

мне не нравится суб-шаблон на второй линии, которая пытается соответствовать комментарии, и я не думаю, что он будет работать правильно.

Я вижу, что вы пытаетесь сделать с (([^\*]\@) | (\*[^\@]) | .)* - позволяют @ и * в пределах комментариев до тех пор, пока они не предшествуют * или после @ соответственно. Но из-за кванта группы * и третьего варианта . суб-шаблон будет с удовольствием соответствовать *@, поэтому рендеринг остальных вариантов будет лишним.

И если предположить, что подмножество Бритвы вы пытаетесь соответствовать не позволяет многострочные комментарии, я предлагаю для второй линии

+ @"| (?<comment> @\*.*?\*@)" 

т.е. лениво сопрягать любые символы (но символ новой строки), пока первый *@ встречается , Вы используете RegexOptions.ExplicitCapture, что означает, что захватываются только названные группы, поэтому отсутствие () не должно быть проблемой.

Я также не люблю подзаголовок ([^\@<]+|[^\@]) в последней строке, что соответствует ([^\@<]+|<). [^\@<]+ будет с жадностью соответствовать концу строки, если она не встречает @ или <.

Я не вижу никаких смежных суб-шаблонов, которые будут совпадать с тем же текстом, который является обычным виновником чрезмерного обратного отслеживания, но все \s* кажутся подозрительными из-за их жадности и гибкости, в том числе соответствия ничего и новой строки. Возможно, вы можете изменить некоторые из \s* на [ \t]*, где вы знаете, что не хотите соответствовать символам новой строки, например, возможно, перед открывающей скобкой после if.

Я заметил, что nhahtdh предложила использовать атомную группировку, чтобы предотвратить откат двигателя в ранее согласованном состоянии, и это, безусловно, что-то стоит поэкспериментировать, поскольку это почти наверняка чрезмерное отступление, вызванное тем, что двигатель больше не может найти что приводит к замедлению.

Что вы пытаетесь достичь с помощью опции RegexOptions.Multiline? Вы не собираетесь использовать ^ или $, поэтому он не будет иметь никакого эффекта.

Уклонение от @ не нужно.

Answer 2

Как уже упоминалось, вы можете улучшить читаемость путем удаления ненужных побегов (например, спасаясь @ или избежать символов в стороне от \ внутри класса символов, например, с помощью [^*] вместо [^\*]).

Вот некоторые идеи для улучшения производительности:

Заказать ваши различные варианты так, что наиболее вероятными из них приходят в первую очередь.

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

Удалить ненужную с возвратами

Не концовку вашей «с помощью» альтернатива: @"| (?<using> \@using \s+ (?<namespace> [\w\.]+) (\s*;)?)"

Если по какой-то причине у вас есть большое количество пробелов, но не закрывает ; в конце А, используя line, механизм регулярного выражения должен возвращаться через каждый символ пробела, пока он окончательно не решит, что он не может соответствовать (\s*;). В вашем случае (\s*;)? может быть заменен на \s*;?, чтобы предотвратить откат в этих сценариях.

Кроме того, вы можете использовать атомные группы (?> ... ) для предотвращения возвратов через кванторы (например * и +). Это действительно помогает повысить производительность, если вы не найдете соответствия. Например, ваша альтернатива «foreach» содержит \s* \(\s*. Если вы найдете текст "foreach var...", альтернатива «foreach» будет жадно соответствовать всем пробелам после foreach, а затем сбой, если он не найдет открытие (. Затем он будет возвращаться, один символ пробела за раз, и попытаться сопоставить ( в предыдущей позиции, пока он не подтвердит, что он не может соответствовать этой строке. Использование атомной группы (?>\s*)\( заставит механизм regex не отступать через \ s *, если он соответствует, что позволяет регулярному выражению сбой быстрее.

Будь осторожны при использовании их, хотя, так как они могут привести к непредвиденным сбоям при использовании в неправильном месте (например, '(?>,*); никогда ничего не соответствует, из-за жадные .* сопоставления всех символов (включая ;) и атомную группировку (?> ... ) Предотвращение повторного движения одного из символов регулярного выражения в соответствии с окончанием ;).

«Разверните цикл» на некоторых ваших альтернативах, таких как альтернатива «комментариев» (также полезно, если вы планируете добавить альтернативу для строк).

Например: @"| (?<comment> \@\* (([^\*]\@) | (\*[^\@]) | .)* \*\@)"

Может быть заменен @"| (?<comment> @\* [^*]* (\*+[^@][^*]*)* \*+@)"

Новое регулярное выражение сводится к:

1. @\*: Найти начало комментария @*
2. [^*]*: Read все «обычные символы» (все, что не является * becaus е, что может означать конец комментария)
3. (\*+[^@][^*]*)*: включают любые нетерминальный * комментарию
   • (\*+[^@]: Если мы находим *, гарантировать, что любая строка * с не заканчивается в @
   • [^*]*: Вернитесь к чтению все "нормальные символы"
   • )*: Loop возвращается к началу, если мы находим еще *
4. \*+@: Наконец, возьмите конец комментария *@ быть осторожным, чтобы включать в себя любые дополнительные *

Вы можете найти много больше идей для повышения эффективности ваших регулярных выражений от Jeffrey Friedl-х Mastering Regular Expressions (3rd Edition).