Once while working on a system that was reading gigs of data and running regexps against it in large chunks. I discovered that a significant part of the time of my runtime was going to running my regular expressions. They weren't overly complex and weren't as good as I'd make them if I were doing the same thing today. I was matching against a string that was around a megabyte and doing it a few million times.

Two improvements really helped out. Getting a simpler, smarter regexp and removing all my capturing. It turns out that even with a dirt simple regexp with almost no backtracking I still wasn't fast enough. It's when I removed all my capturing that I finally hit paydirt. It turns out that perl's regexp engine makes a memcpy (or something similar) of the string so that $1 and similar variables can continue to work even if the source is altered or thrown away.

$str = 'Hulk hate classless system with means of manufacturing given t
+o working class! Hulk crush puny Marxists!';
if ( $str =~ /Hulk hate (\w+)/ ) {
    $str = '';
    my $word = $1;
}

[download]

The above snippet shows that for $1 to work the information that was matched has to be fetched from someplace other than $str. That place is some variable internal to the perl interpreter. The penalty is if $str was really large then I've just spent time making really large copies.

I can avoid that penalty if I use offsets. $-[0] contains the offset into the string where the match started and $+[0] contains the offset where the match ended. $1 isn't going to be set so I'll need to use substr() to fetch just the part I need. In the above example I know the match starts at $-[0], skips ten characters then I want whatever is from there on til $+[0].

if ( $str =~ /Hulk hate \w+/ ) {
    # $-[0] == 0
    # $+[0] == 19
    my $word = substr $str, $-[0] + 10, $+[0] - $-[0] + 10;
    # $word is now 'classless'

=pod

[An update. Hue-Bond points out that I should have said $+[0] - $-[0] 
+- 10 instead. Whoops. I just leave this as a note to how easy it is t
+o get this stuff wrong when you do it by hand. This is the kind of er
+ror you could find yourself in when you try this optimization. You we
+re warned]

=cut

}

[download]

The optimization saved me real time. It made my process at least an hour or so faster. It went from uh... 3ish hours down to a little over an hour. The code will be difficult to maintain if you do this. Kids, don't make your source code crappy like I did unless you find you really need to. One of your primary goals as a programmer is to reduce unnecessary complexity and if you use this technique it had better be worth it.

In reply to An optimization of last resort: eliminate capturing from your regexps by diotalevi

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.