What is the advantage of unroll the loop compared to shorter regex notation with quantified alternatives?

by

The difference between the two patterns is potential efficiency.

The (exp1 | exp2)* pattern contains an alternation that automatically disables some internal regex matching optimization. Also, this regex tries to match the pattern at each location in the string.

The (exp1 * (exp2 exp1*)*) expression is written acc. to the unroll-the-loop principle:

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, the exp1 in your example is normal part that is most common, and exp2 is expected to be less frequent. In that case, the efficiency of the unrolled pattern can be really, much higher than that of the other regex since the normal* part will grab the whole chunks of input without any need to stop and check each location.

Let’s see a simple "([^"\\]|\\.)*" regex test against "some text here": there are 35 steps involved:

enter image description here

Unrolling it as "[^"\\]*(\\.[^"\\]*)*" gives a boost to 6 steps as there is much less backtracking.

enter image description here

NOTE that the number of steps at regex101.com does not directly mean one regex is more efficient than another, however, the debug table shows where backtracking occurs, and backtracking is resource consuming.

Let’s then test the pattern efficiency with JS benchmark.js:

var suite = new Benchmark.Suite();
Benchmark = window.Benchmark;
suite
  .add('Regular RegExp test', function() {
      '"some text here"'.match(/"([^"\\]|\\.)*"/);
    })
  .add('Unrolled RegExp test', function() {
      '"some text here"'.match(/"[^"\\]*(\\.[^"\\]*)*"/);
    })
  .on('cycle', function(event) {
    console.log(String(event.target));
  })
  .on('complete', function() {
    console.log('Fastest is ' + this.filter('fastest').map('name'));
  })
  .run({ 'async': true });
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.13.1/lodash.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.1/platform.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.0/benchmark.js"></script>

Results:

Regular RegExp test x 9,295,393 ops/sec ±0.69% (64 runs sampled)
Unrolled RegExp test x 12,176,227 ops/sec ±1.17% (64 runs sampled)
Fastest is Unrolled RegExp test

Also, since unroll the loop concept is not language specific, here is an online PHP test (regular pattern yielding ~0.45, and unrolled one yielding ~0.22 results).

Also see Unroll Loop, when to use.

More Related Contents:

  1. Find particular string from URL in JavaScript
  2. Regex for Email Address along with name format [duplicate]
  3. Negative lookbehind equivalent in JavaScript
  4. Remove not alphanumeric characters from string
  5. Password REGEX with min 6 chars, at least one letter and one number and may contain special characters
  6. Regex created via new RegExp(myString) not working (backslashes)
  7. Regular Expression | Leap Years and More
  8. How to write regex to validate dates?
  9. Replacing   from javascript dom text node
  10. Javascript – Regex to validate date format [duplicate]
  11. Replacing the nth instance of a regex match in Javascript
  12. How to extract a string using JavaScript Regex?
  13. JavaScript Regex Global Match Groups
  14. How can I put [] (square brackets) in RegExp javascript?
  15. What does the regular expression /_/g mean?
  16. Highlight current page in jquery
  17. Highlight word in HTML text (but not markup)
  18. All characters in a string must match regex
  19. RegEx to match stuff between parentheses
  20. Regex eError when using {1}+ possessive quantifier in JavaScript regex
  21. Check if string contains only letters in javascript
  22. regular expression to validate datetime format (MM/DD/YYYY) [duplicate]
  23. Regex JavaScript image file extension [closed]
  24. Removing backslashes from strings in javascript
  25. Why this regex is not working for german words?
  26. Remove everything within script and style tags
  27. URL regex validation
  28. I would like to mimick conditionals in javascript regex
  29. Get text between two rounded brackets
  30. Preg_match to regex equivalent expression to match any Unicode letters

Leave a Comment