Unroll Loop, when to use

by

What is Unroll-the-loop

See this Unroll the loop technique source:

This optimisation thechnique is used to optimize repeated alternation of the form (expr1|expr2|...)*. These expression are not uncommon, and the use of another repetition inside an alternation may also leads to super-linear match. Super-linear match arise from the underterministic expression (a*)*.

The unrolling the loop technique is based on the hypothesis that in most case, you kown in a repeteated alternation, which case should be the most usual and which one is exceptional. We will called the first one, the normal case and the second one, the special case. The general syntax of the unrolling the loop technique could then be written as:

normal* ( special normal* )*

So, this is an optimization technique where alternations are turned into linearly matching atoms.

This makes these unrolled patterns very efficient since they involve less backtracking.

Current Scenario

Your MINISTÉRIO[\s\S]*?PÁG is a non-unrolled pattern while MINISTÉRIO[^P]*(?:P(?!ÁG)[^P]*)*PÁG is. See the demos (both saved with PCRE option to show the number of steps in the box above. Regex performance is different across regex engines, but this will tell you exactly the performance difference). Add more text after text: the first regex will start requiring more steps to finish, the second one will only show more steps after adding P. So, in texts where the character you used in the known part is not common, unrolled patterns are very efficient.

See the Difference between .*?, .* and [^"]*+ quantifiers section in my answer to understand how lazy matching works (your [\s\S]*? is the same as .*? with a DOTALL modifier in languages that allow a . to match a newline, too).

Performance Question

Is the lazy matching pattern always slow and inefficient? It is not always so. With very short strings, lazy dot matching is usually better (1-10 symbols). When we talk about long inputs, where there can be the leading delimiter, and no trailing one, this may lead to excessive backtracking leading to time out issues.

Use unrolled patterns when you have arbitrary inputs of potentially long length and where there may be no match.

Use lazy matching when your input is controlled, you know there will always be a match, some known set log formats, or the like.

Bonus: Commonly Unrolled patterns

  1. Tempered greedy tokens

  2. Regular string literals ("String\u0020:\"text\""): "[^"\\]*(?:\\.[^"\\]*)*"

  3. Multiline comment regex (/* Comments */): /\*[^*]*\*+(?:[^/*][^*]*\*+)*/

  4. @<...>@ comment regex: @<[^>]*(?:>[^@]*)*@

More Related Contents:

  1. Regex – To allow numeric, only characters R, N, X, B, @ [closed]
  2. Find particular string from URL in JavaScript
  3. Regex for Email Address along with name format [duplicate]
  4. JavaScript regex multiline text between two tags
  5. Case insensitive regex in JavaScript
  6. I want to remove double quotes from a String
  7. Count number of matches of a regex in Javascript
  8. Password REGEX with min 6 chars, at least one letter and one number and may contain special characters
  9. Regex created via new RegExp(myString) not working (backslashes)
  10. Replace a Regex capture group with uppercase in Javascript
  11. Regular Expression | Leap Years and More
  12. Matching exact string with JavaScript
  13. Finding Plus Sign in Regular Expression
  14. Combining regular expressions in Javascript
  15. Regex to Match Symbols: !$%^&*()_+|~-=`{}[]:”;’?,./
  16. Javascript regex returning true.. then false.. then true.. etc [duplicate]
  17. RegEx: How can I match all numbers greater than 49?
  18. How can I replace newlines/line breaks with spaces in javascript?
  19. How do I split a string by whitespace and ignoring leading and trailing whitespace into an array of words using a regular expression?
  20. Remove specific HTML tag with its content from javascript string
  21. Can I use a regular expression in querySelectorAll?
  22. Regex remove repeated characters from a string by javascript
  23. Regex only capturing last instance of capture group in match
  24. Javascript RegExp for splitting text into sentences and keeping the delimiter
  25. Commenting Regular Expressions
  26. JavaScript Regex to match a URL in a field of text
  27. How can I use regex to get all the characters after a specific character, e.g. comma (“,”)
  28. Extract keyword from Google search in Javascript
  29. Regex matching emoticons
  30. Regex: only alphanumeric but not if this is pure numeric

Leave a Comment