Vennis has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

While looking at performance of a script of mine, i tested an iteration script, i found out that using a little bit more complex Regular Expressions isn't equal or faster, even though it's code is smaller (and looks nicer).

I realize this is a minor test and a fast conclusion, i hope anyone can tell me why this difference is and maybe tell me if you have experienced such differences yourself ?

Did i test this wrongly? Or would it seriously be an option to fragment a complex RE for better performance (if possible) ? 

for($i=0;$i<100000;$i++){
    if("test$i" =~ /(est|\d)/){
        # do stuff;
    }
}

is at least 20% slower (+/- 3s vs 2.3s yes, slow machine :-) then: 

for($i=0;$i<100000;$i++){
    if("test$i" =~ /est/ || "test$i" =~ /\d/){
        # do stuff;
    }
}

[download]

Replies are listed 'Best First'.
Re: RE performance
by RMGir (Prior) on Sep 04, 2002 at 12:34 UTC
    Try it without the () in your first regex. The RE engine has to do a bit of setup work every time it enters or leaves a capturing () set during its passage through the candidate string, so they add a lot of overhead.

    Also, your "||" version isn't very fair, since the /est/ always matches, meaning the /\d/ test is never made. But it is interesting how much faster the "constant" match for est is as opposed to the match for est|\d.

    Oh, and use Benchmark: 

    #!/usr/bin/perl -w

use strict;
use Benchmark qw(cmpthese);

my $i=0;

sub capture {
    "test$i"=~/(est|\d)/;
}

sub noCapture {
    "test$i"=~/(?:est|\d)/;
}

sub noParens {
    "test$i"=~/est|\d/;
}

sub twoRegexen {
    "test$i"=~/est/ || "test$i"=~/\d/;
}

cmpthese(-3,
        {
            capture   => \&capture,
            noCapture => \&noCapture,
            noParens => \&noParens,
            twoRegexen => \&twoRegexen,
        }
     );

    [download]
    Results (with 5.6.1, I'm sure 5.8.0 would be somewhat different): 
    $ perl testRegexen.pl
Benchmark: running capture, noCapture, noParens, twoRegexen, each for 
+at least 3
 CPU seconds...
   capture:  4 wallclock secs ( 3.18 usr +  0.00 sys =  3.18 CPU) @ 72
+8822.24/s (n=2320570)
 noCapture:  2 wallclock secs ( 3.10 usr +  0.01 sys =  3.11 CPU) @ 82
+7692.26/s (n=2576606)
  noParens:  4 wallclock secs ( 3.14 usr +  0.01 sys =  3.15 CPU) @ 87
+1936.55/s (n=2748344)
twoRegexen:  4 wallclock secs ( 3.41 usr + -0.00 sys =  3.41 CPU) @ 14
+78048.90/s  (n=5047537)
                Rate    capture  noCapture   noParens twoRegexen
capture     728822/s         --       -12%       -16%       -51%
noCapture   827692/s        14%         --        -5%       -44%
noParens    871937/s        20%         5%         --       -41%
twoRegexen 1478049/s       103%        79%        70%         --

    [download]

    --
    Mike

    Edit: Oops, when I added the noParens case I forgot to put it into the cmpthese call here, although I'd put it into my test script.

[reply]
[d/l]
[select]

      On perl 5.8.0 i686-linux-thread-multi with debugging:

      $ perl  testRegexen.pl
Benchmark: running capture, noCapture, noParens, twoRegexen for at lea
+st 3 CPU seconds...
   capture:  4 wallclock secs ( 3.20 usr +  0.00 sys =  3.20 CPU) @ 14
+1750.00/s (n=453600)
 noCapture:  3 wallclock secs ( 3.04 usr +  0.02 sys =  3.06 CPU) @ 27
+9933.01/s (n=856595)
  noParens:  1 wallclock secs ( 3.34 usr +  0.00 sys =  3.34 CPU) @ 26
+1686.53/s (n=874033)
twoRegexen:  5 wallclock secs ( 3.41 usr +  0.01 sys =  3.42 CPU) @ 54
+0171.35/s (n=1847386)
               Rate    capture   noParens  noCapture twoRegexen
capture    141750/s         --       -46%       -49%       -74%
noParens   261687/s        85%         --        -7%       -52%
noCapture  279933/s        97%         7%         --       -48%
twoRegexen 540171/s       281%       106%        93%         --
$

      [download]

      Update: perl -Dr output, per request:

      Read more... (2 kB)

      After Compline,
      Zaxo

[reply]
[d/l]
[select]
        Thanks!

        Isn't it strange that the noCapture case is faster than the noParens??

        Here's what use re 'debug' gets me for the 4 regex variants: 

        Compiling REx `(est|\d)'
size 10 first at 3
   1: OPEN1(3)
   3:   BRANCH(6)
   4:     EXACT <est>(8)
   6:   BRANCH(8)
   7:     DIGIT(8)
   8: CLOSE1(10)
  10: END(0)
minlen 1
Compiling REx `(?:est|\d)'
size 7
   1: BRANCH(4)
   2:   EXACT <est>(7)
   4: BRANCH(6)
   5:   DIGIT(7)
   6: TAIL(7)
   7: END(0)
minlen 1
Compiling REx `est|\d'
size 6
   1: BRANCH(4)
   2:   EXACT <est>(6)
   4: BRANCH(6)
   5:   DIGIT(6)
   6: END(0)
minlen 1
Compiling REx `est'
size 3 first at 1
   1: EXACT <est>(3)
   3: END(0)
anchored `est' at 0 (checking anchored isall) minlen 3
Compiling REx `\d'
size 2 first at 1
   1: DIGIT(2)
   2: END(0)
stclass `DIGIT' minlen 1

        [download]
        The TAIL(7) on the noCapture case looks redundant to me; maybe that's something they fixed in 5.8.0?

        What happens if you look at those regexes under 5.8.0 with -Dr or use re 'debug', please?

        ( Edit: Zaxo did this just above, and got the same results, except he gets offsets. No idea what those mean...)
        --
        Mike

[reply]
[d/l]
Re: RE performance
by PetaMem (Priest) on Sep 04, 2002 at 12:23 UTC
    Hi,

    My guess is, that your speedup comes from the "optimization" you get by the || operator. If the "test$i" =~ /est/ piece gives a true value (and it does always in your example), no need to evaluate the second part. Thus you "significantly" simplified the regexp.

    Bye
     PetaMem

[reply]
[d/l]
      This sounds logic, but this next test, still shows more or less 20% difference. 
      for($i=0;$i<100000;$i++){
    if("test$i" =~ /(dest|\d)/){
        # do stuff;
    }
}

for($i=0;$i<100000;$i++){
    if("test$i" =~ /dest/ || "test$i" =~ /\d/){
        # do stuff;
    }
}

      [download]
[reply]
[d/l]
Re: RE performance
by demerphq (Chancellor) on Sep 04, 2002 at 17:07 UTC
    Heh, a crash course in benchmarking eh? ;-)

    Well personally my analysis of why the || version is faster is this (and i await correction by japhy or some other god...)

    Lets say the string we are matching against is "test100"

    so with /(est|\d)/ it would first check 'e' against 't' fail, and then test 'e' to is if its in [0-9] (its not smart enough to know it isn't unfortunately) which it isnt of course, (also this test is much more expensive than testing against a constant char). It would then test 'e' against 'e' and (so on and) find the match. So the result is 4 constant char tests and 1 char class test, we also have some minor overhead doing the option transition.

    With /est/ it would test the 'e' against the 't' fail the match and then match as before. Result 4 constant char tests, no char class tests, no option transitions. (And this ignores potential optimizations that the boyer-moore algorithm may or may not contribute to this case). Since the first match succeeds it the second regex never executes and no char class matching is performed.

    I reversed the order of the text so that instead of being test100 it would be 100test (as well as adding reverse versions of the tests), and even then your "faster" version _is_ actually faster. This makes me think that boyer moore _is_ actually kicking in and providing more optimizations than I describe here. Also its interesting that slower2 is about the same speed as faster2.

    Read more... (2 kB)

    Although you should keep in mind that this benchmark is pretty misleading. It doesnt test against "live" data, nor does it include scenarios where there is no match, things like that. When you use some more "realistic" data you get the opposite results.

    Read more... (1366 Bytes)

    Benchmark: running faster, faster2, slower, slower2, each for at least
+ 5 CPU seconds...
    faster:  4 wallclock secs ( 5.25 usr +  0.00 sys =  5.25 CPU) @ 10
+3837.90/s (n=545149)
   faster2:  6 wallclock secs ( 5.24 usr +  0.00 sys =  5.24 CPU) @ 10
+3939.83/s (n=544125)
    slower:  5 wallclock secs ( 5.25 usr +  0.00 sys =  5.25 CPU) @ 13
+3356.57/s (n=700122)
   slower2:  5 wallclock secs ( 5.28 usr +  0.00 sys =  5.28 CPU) @ 13
+2805.94/s (n=701481)
            Rate  faster faster2 slower2  slower
faster  103838/s      --     -0%    -22%    -22%
faster2 103940/s      0%      --    -22%    -22%
slower2 132806/s     28%     28%      --     -0%
slower  133357/s     28%     28%      0%      --

    [download]
    HTH

    Yves / DeMerphq
    ---
    Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)

[reply]
[d/l]
[select]
      Thank you! This clears up a lot for me.

      It also tought me a lot about Benchmarking more properly.

[reply]

Back to Seekers of Perl Wisdom