Benchmark: timing 100000 iterations of 1, 2, 3...
1: 22 wallclock secs @ 4553.73/s
2: 13 wallclock secs @ 7575.76/s
3: 15 wallclock secs @ 6765.90/s
[download]

I'll let the experts (if they want) explain why this is, in terms of how the regex parser operates, but my guess is that 2 is faster because most characters are not opening angle brackets, so the [^<]* absorbs them.

I also have the feeling that the comparison may change when confronted with real data, because of the length and contents of whatever is inside the <div> tags.

Update: and of course, all of this only applies to the Perl implementation of regular expressions, so these results are probably mostly useless, because different JavaScript implementations could do things differently.

--ZZamboni

use strict;
use Benchmark;

my $str=q(this is some text
<div class="blockqte">a block <span>quote</span></div>
some more text <b>maybe</b> some other tags
<div class="blockqte">another block</div>
we end here);

sub method1 { my $s=shift;
 $s=~s@<div class="blockqte">((?:[^<]|<\/?s)*)<\/div>@<pre>$1</pre>@g;
}

sub method2 { my $s=shift;
 $s=~s@<div class="blockqte">((?:[^<]*|<\/?s)*)<\/div>@<pre>$1</pre>@g
+;
}

sub method3 { my $s=shift;
 $s=~s@<div class="blockqte">((?:.|\n)*?)<\/div>@<pre>$1</pre>@g;
}

timethese(100000, {'1' => sub { method1($str) },
                   '2' => sub { method2($str) },
                   '3' => sub { method3($str) }});
[download]

(3) will speed up if you replace "(?:.|\n)" with something simpler such as "[\s\S]", or best, add the "s" option to your regex and just use ".".

(1) is slower than (2) because (1) has to dispatch a lot more regex opcodes. That is, (2) can just hang out in the "[^<]*" opcode while it gobbles quite a few characters while (1) has to leave "[^<]" for each character (leaving the alternation/parens to move to the "*" then come back in through the alternation/parens to get back to the "[^<]").

You are correct (to my understanding) about the disadvantage of (3). But (3) has an advantage in that it is simpler than (1) and (2).

According to ZZamboni's benchmarks, (3)'s disadvantage is only slightly greater than its advantage and slight compared to (1)'s disadvantage. But I suspect this is all rather dependant on the input used in the benchmarks. In particular, the length of the text to be matched and the frequency of <span> tag pairs within it will affect the relative performance characteristics.

As for other alternatives, I see no reason to not simplify things greatly to:

s#<div class="blockqte">#<pre>#g;
s#</div>#</pre>#g;
[download]

Finally, many regex libraries are built around deterministic finite state automata, which means that different regexes run at much closer to the same speed (though more complex ones take longer to compile), but memory consumption can grow out of bounds. So Java's regex performance characteristics could be drastically different than Perl's.

The JavaScript RE spec is modelled after Perl and includes full support for backreferences. Therefore they cannot use a DFA style engine.

tye, well there is a reason not to simplify like you suggested:

s#<div class="blockqte">#<pre>#g;  # this is OK
s#</div>#</pre>#g;                 # this creates the problems
[download]

you replace all </div> with </pre> and if I understood it correctly, not all the <div> tags have the attribute class="blockqte" and should be replaced ... ;-)

-- Hofmator

    m{<div\s+class\s*=\s*"blockqte"\s*>((?:[^<]+|</?s)*)</div>}
[download]

-- Abigail

Hi Abigail. Thank you for the advise. Could you please explain to this neophyte why changing the nested * to a nested + makes so much of a difference. Mark.

  $parser->get_tag("div");
[download]