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

Question

Requirement : Two expressions, exp1 and exp2, we need to match one or more of both. So I came up with,

(exp1 | exp2)*

However in some places, I see the below being used,

(exp1 * (exp2 exp1*)*)

What is the difference between the two? When would you use one over the other?

Hopefully a fiddle will make this more clear,

var regex1 = /^"([\x00-!#-[\]-\x7f]|\\")*"$/;
var regex2 = /^"([\x00-!#-[\]-\x7f]*(\\"[\x00-!#-[\]-\x7f]*)*)"$/;

var str = '"foo \\"bar\\" baz"';
var r1 = regex1.exec(str);
var r2 = regex2.exec(str);

EDIT: It looks like there is a difference in behavior between the two apporaches when we capture the groups. The second approach captures the entire string while the first approach captures only the last matching group. See updated fiddle.

Answer 1

What is the difference between the two?

The difference between them is how they exactly match a particular given input. If you think of these as two functions in terms of input and output they are the equivalent, but how the function works to produce the output (match) is different. Both of these regular expressions (exp1 | exp2)* and (exp1 * (exp2 exp1*)*) will match the exact same input. In other-words you can say they are semantically equivalent in terms of the given input and a match (output).

When would you use one over the other?

Edit

The second regular expression (exp1 * (exp2 exp1*)*) is more optimal due to the loop unrolling technique. See @Wiktor Stribiżew's answer.

---

Proof

One way to prove if two regular expressions are equivalent is to see if they have the same DFA. Using this converter, here are the following DFAs of the regular expressions.

(Note: a = exp1 and b = exp2)

(a*(ba*)*)

(a|b)*

Notice that the first DFA is the same as the second one? The only difference is that the first one isn't minimized. Here is a crud fix to show the minimization of the first DFA:

Answer 2

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:

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

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.