Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Performance penalty of using qr//

by Athanasius (Archbishop)
on Dec 21, 2017 at 03:47 UTC ( [id://1205956]=perlquestion: print w/replies, xml ) Need Help??

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

Hello all, and Merry Christmas!

I recently came across some old code in which I used a longish regular expression twice within a loop. So I thought, “Aha! here’s an opportunity for optimisation using qr//.” After all, the documentation (qr/STRING/msixpodualn under “Regexp Quote-Like Operators” in perlop) says:

Since Perl may compile the pattern at the moment of execution of the qr() operator, using qr() may have speed advantages in some situations ...

But the result was more than disappointing:

use strict; use warnings; use Benchmark qw( cmpthese timethese ); use constant TARGET => 1_389_019_170; my $r = timethese ( 5, { use_re => sub { my $ans1 = use_re(); $ans1 == TARGET or die $ans1; }, use_qr => sub { my $ans2 = use_qr(); $ans2 == TARGET or die $ans2; }, use_str => sub { my $ans3 = use_str(); $ans3 == TARGET or die $ans3; } } ); cmpthese $r; sub use_re { for (my $n = 1_010_101_030; $n <= 1_389_026_623; ) { my $s = $n * $n; return $n if $s =~ /^1\d2\d3\d4\d5\d6\d7\d8\d900$/; $n += 40; $s = $n * $n; return $n if $s =~ /^1\d2\d3\d4\d5\d6\d7\d8\d900$/; $n += 60; } die; } sub use_qr { my $re = qr/^1\d2\d3\d4\d5\d6\d7\d8\d900$/; for (my $n = 1_010_101_030; $n <= 1_389_026_623; ) { my $s = $n * $n; return $n if $s =~ $re; $n += 40; $s = $n * $n; return $n if $s =~ $re; $n += 60; } die; } sub use_str { my $str = '^1\d2\d3\d4\d5\d6\d7\d8\d900$'; for (my $n = 1_010_101_030; $n <= 1_389_026_623; ) { my $s = $n * $n; return $n if $s =~ /$str/; $n += 40; $s = $n * $n; return $n if $s =~ /$str/; $n += 60; } die; }

Typical output:

12:50 >perl 1846_SoPW.pl Benchmark: timing 5 iterations of use_qr, use_re, use_str... use_qr: 57 wallclock secs (53.19 usr + 0.06 sys = 53.25 CPU) @ 0 +.09/s (n=5) use_re: 22 wallclock secs (22.03 usr + 0.00 sys = 22.03 CPU) @ 0 +.23/s (n=5) use_str: 26 wallclock secs (25.81 usr + 0.00 sys = 25.81 CPU) @ 0 +.19/s (n=5) s/iter use_qr use_str use_re use_qr 10.7 -- -52% -59% use_str 5.16 106% -- -15% use_re 4.41 142% 17% -- 12:54 >

(I obtained similar results across my various 64-bit Strawberry Perl versions: 5.18.2, 5.20.2, 5.22.2, 5.24.0, and 5.26.0.)

I note in the documentation that the string returned by qr// “magically differs from a string containing the same characters”, so I’m guessing the additional overhead is due to the “magic” in some way, but I still find the result surprising. So, my questions:

  • Is this a known issue? Is it documented? (Yes, I looked.)
  • Can anyone explain why qr// incurs such a significant performance penalty in my example?
  • Is there an alternative (say, a CPAN module) that can provide the functionality of qr// without the overhead?

Thanks,

Athanasius <°(((><contra mundum Iustus alius egestas vitae, eros Piratica,

Replies are listed 'Best First'.
Re: Performance penalty of using qr//
by dave_the_m (Monsignor) on Dec 21, 2017 at 12:44 UTC
    The problem is actually to do with (potential) captures. Currently, capture information (the information that is used to create the values of $1 et al when accessed) is stored as part of the regex object. This model doesn't work well when the same regex can be used in multiple places. This code:
    $r = qr/(.)/; "a" =~ $r; print "$1\n"; { "b" =~ $r; print "$1\n"; } print "$1\n";
    outputs:
    a b a
    Thus a single regex object has to be associated with multiple capture sets, which change as scopes are exited.

    The current workaround for this is to duplicate the qr// object each time it's executed, which is sub-optimal. Unfortunately fixing this properly is non-trivial.

    Dave.

      Um ... so ... when is the sometime the optimization kicks in? Can it be measured?
        Um ... so ... when is the sometime the optimization kicks in
        What optimisation are you referring to?

        Dave.

Re: Performance penalty of using qr//
by BrowserUk (Patriarch) on Dec 21, 2017 at 08:59 UTC

    FTR: I encountered (and probably described/reported it here, but I don't remember for sure), a similar disappointment many years ago.

    My recollection of it is that a variable built using qr// was always reinterpreted at the point of interpolation into another qr// or a larger regex.

    My conclusion was that like the /o modifier on regex, it was either never implemented, or was removed by an early bug fix.

    See also 971076, but I'm almost sure there should be an earlier thread.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
    In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit
Re: Performance penalty of using qr//
by choroba (Cardinal) on Dec 21, 2017 at 16:22 UTC
    See also /o is dead, long live qr//! and Re: Never. I'm sure there was another thread with benchmarks, it shouldn't be older than two or three years, but I can't find it now.

    ($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord }map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
Re: Performance penalty of using qr//
by LanX (Saint) on Dec 21, 2017 at 04:11 UTC
    Sorry, your benchmark is too complicated, I can't easily tell how often the inner loop is executed.

    If it's just several times then your results may be explained by the overhead to initialize qr.

    Another guess is to try $s =~ /$re/; instead of $s =~ $re; (which is admittedly counterintuitive)

    Can't test, sorry.

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)
    Wikisyntax for the Monastery

      Hi LanX,

      The inner for loops are each executed 3,789,182 times.

      And yes, I originally had $s =~ /$re/ instead of $s =~ $re — it made no appreciable difference.

      Update: Deparsing suggests that Perl adds the slashes anyway:

      16:57 >perl -we "my $q = qr/^(\d+)$/; 123 =~ $q; print qq[$1\n];" 123 16:57 >perl -MO=Deparse -we "my $q = qr/^(\d+)$/; 123 =~ $q; print qq[ +$1\n];" BEGIN { $^W = 1; } my $q = qr/^(\d+)$/; 123 =~ /$q/; print "$1\n"; -e syntax OK 16:57 >

      Cheers,

      Athanasius <°(((><contra mundum Iustus alius egestas vitae, eros Piratica,

        hmm .... could be a regression.

        If for some reason the scalar falls back to string interpolation instead of using the compilated code this could explain the penalty and wouldn't break the tests.

        A simplified benchmark for all platforms x versions would be nice.

        Cheers Rolf
        (addicted to the Perl Programming Language and ☆☆☆☆ :)
        Wikisyntax for the Monastery

Re: Performance penalty of using qr//
by Eily (Monsignor) on Dec 21, 2017 at 10:32 UTC

    With this version of use_str:

    sub use_str { my $re = qr/^1\d2\d3\d4\d5\d6\d7\d8\d900$/; for (my $n = 1_010_101_030; $n <= 1_389_026_623; ) { # stringify the qr regex my $str = "$re"; my $s = $n * $n; return $n if $s =~ /$str/; # recompiled each time I guess? $n += 40; $s = $n * $n; return $n if $s =~ /$str/; $n += 60; } die; }
    I get:
    Benchmark: timing 5 iterations of use_qr, use_re, use_str... use_qr: 33 wallclock secs (33.62 usr + 0.00 sys = 33.62 CPU) @ 0 +.15/s (n=5) use_re: 18 wallclock secs (17.14 usr + 0.00 sys = 17.14 CPU) @ 0 +.29/s (n=5) use_str: 25 wallclock secs (24.99 usr + 0.00 sys = 24.99 CPU) @ 0 +.20/s (n=5) s/iter use_qr use_str use_re use_qr 6.72 -- -26% -49% use_str 5.00 35% -- -31% use_re 3.43 96% 46% -- Appuyez sur une touche pour continuer...
    So this looks like perl is doing even worse with qr than it would by recompiling the stringified version on each iteration (unless I'm missing some optimization, but I tried adding dummy logic like rand(100) < 100 to prevent perl from noticing that the expression are constants, and didn't see significant changes)?

    Edit: perl v5.20 here BTW

Re: Performance penalty of using qr//
by kcott (Archbishop) on Dec 22, 2017 at 06:19 UTC

    G'day Athanasius,

    I decided to look at this from a slightly different angle. Instead of involving complex routines and matches, I picked a regex match that was so simple that an 'eq' comparison would be, in normal code, a better choice:

    'X' =~ /^X$/

    I ran this benchmark, using that match as a base, but incorporating a whole series of variations: with/without 'qr//', the 'o' modifier, and many types of variables.

    #!/usr/bin/env perl use 5.010; use strict; use warnings; use Benchmark 'cmpthese'; use constant STRING => 'X'; use constant CONST_RE => qr{^X$}; my $my_re = qr{^X$}; state $state_re = qr{^X$}; our $our_re = qr{^X$}; local $main::local_re = qr{^X$}; cmpthese 0 => { re_str => sub { STRING =~ '^X$' }, re_re => sub { STRING =~ /^X$/ }, re_re_o => sub { STRING =~ /^X$/o }, re_qr => sub { STRING =~ qr{^X$} }, re_qr_o => sub { STRING =~ qr{^X$}o }, qr_my => sub { STRING =~ $my_re }, qr_my_re => sub { STRING =~ /$my_re/ }, qr_my_re_o => sub { STRING =~ /$my_re/o }, qr_state => sub { STRING =~ $state_re }, qr_state_re => sub { STRING =~ /$state_re/ }, qr_state_re_o => sub { STRING =~ /$state_re/o }, qr_our => sub { STRING =~ $our_re }, qr_our_re => sub { STRING =~ /$our_re/ }, qr_our_re_o => sub { STRING =~ /$our_re/o }, qr_const => sub { STRING =~ CONST_RE }, qr_const_re => sub { STRING =~ /${\CONST_RE()}/ }, qr_const_re_o => sub { STRING =~ /${\CONST_RE()}/o }, qr_local => sub { STRING =~ $main::local_re }, qr_local_re => sub { STRING =~ /$main::local_re/ }, qr_local_re_o => sub { STRING =~ /$main::local_re/o }, };

    [I was aware that "qr_const_re" and "qr_const_re_o" might produce bogus results due to the additional reference and dereference operations; however, I left them in purely out of curiosity.]

    Here's the results just showing the rates. (The complete results are in a spoiler at the end of my post.)

    Rate re_qr 550709/s re_qr_o 560597/s qr_local 1061718/s qr_const_re 1065053/s qr_state 1065891/s qr_local_re 1077507/s qr_our 1089135/s qr_state_re 1089138/s qr_my_re 1092539/s qr_my 1096982/s qr_our_re 1101420/s qr_state_re_o 4073421/s qr_local_re_o 4085064/s qr_my_re_o 4279146/s qr_const_re_o 4293130/s qr_our_re_o 4302931/s re_re_o 4647519/s qr_const 4745450/s re_re 4748039/s re_str 4814042/s

    Some of those numbers are too close to call with respect to what was faster than what; however, this general trend appears to emerge (fastest to slowest):

    1. '^X$', /^X$/ and, when created at compile time, qr{^X$}.
    2. All that used the 'o' modifier (except for qr{^X$}o).
    3. Those using variables assigned with qr{^X$}; either as $var or /$var/.
    4. Clearly the slowest of all: qr{^X$} and qr{^X$}o (created at runtime).

    I ran that a few times. The specific order changed a bit but the general trend I've indicated seemed to hold.

    In light of ++dave_the_m's input, I'd like to see how captures might affect those results. I don't have time to do this myself now: perhaps you, or someone else, would care to tinker.

    The full results are in the spoiler, below. I needed to stretch the console window to 220 characters to avoid wrapping.

    Rate re_qr re_qr_o qr_local qr_const_re qr_state qr +_local_re qr_our qr_state_re qr_my_re qr_my qr_our_re qr_state_re_o q +r_local_re_o qr_my_re_o qr_const_re_o qr_our_re_o re_re_o qr_const re +_re re_str re_qr 550709/s -- -2% -48% -48% -48% + -49% -49% -49% -50% -50% -50% -86% + -87% -87% -87% -87% -88% -88% - +88% -89% re_qr_o 560597/s 2% -- -47% -47% -47% + -48% -49% -49% -49% -49% -49% -86% + -86% -87% -87% -87% -88% -88% - +88% -88% qr_local 1061718/s 93% 89% -- -0% -0% + -1% -3% -3% -3% -3% -4% -74% + -74% -75% -75% -75% -77% -78% - +78% -78% qr_const_re 1065053/s 93% 90% 0% -- -0% + -1% -2% -2% -3% -3% -3% -74% + -74% -75% -75% -75% -77% -78% - +78% -78% qr_state 1065891/s 94% 90% 0% 0% -- + -1% -2% -2% -2% -3% -3% -74% + -74% -75% -75% -75% -77% -78% - +78% -78% qr_local_re 1077507/s 96% 92% 1% 1% 1% + -- -1% -1% -1% -2% -2% -74% + -74% -75% -75% -75% -77% -77% - +77% -78% qr_our 1089135/s 98% 94% 3% 2% 2% + 1% -- -0% -0% -1% -1% -73% + -73% -75% -75% -75% -77% -77% - +77% -77% qr_state_re 1089138/s 98% 94% 3% 2% 2% + 1% 0% -- -0% -1% -1% -73% + -73% -75% -75% -75% -77% -77% - +77% -77% qr_my_re 1092539/s 98% 95% 3% 3% 2% + 1% 0% 0% -- -0% -1% -73% + -73% -74% -75% -75% -76% -77% - +77% -77% qr_my 1096982/s 99% 96% 3% 3% 3% + 2% 1% 1% 0% -- -0% -73% + -73% -74% -74% -75% -76% -77% - +77% -77% qr_our_re 1101420/s 100% 96% 4% 3% 3% + 2% 1% 1% 1% 0% -- -73% + -73% -74% -74% -74% -76% -77% - +77% -77% qr_state_re_o 4073421/s 640% 627% 284% 282% 282% + 278% 274% 274% 273% 271% 270% -- + -0% -5% -5% -5% -12% -14% - +14% -15% qr_local_re_o 4085064/s 642% 629% 285% 284% 283% + 279% 275% 275% 274% 272% 271% 0% + -- -5% -5% -5% -12% -14% - +14% -15% qr_my_re_o 4279146/s 677% 663% 303% 302% 301% + 297% 293% 293% 292% 290% 289% 5% + 5% -- -0% -1% -8% -10% - +10% -11% qr_const_re_o 4293130/s 680% 666% 304% 303% 303% + 298% 294% 294% 293% 291% 290% 5% + 5% 0% -- -0% -8% -10% - +10% -11% qr_our_re_o 4302931/s 681% 668% 305% 304% 304% + 299% 295% 295% 294% 292% 291% 6% + 5% 1% 0% -- -7% -9% +-9% -11% re_re_o 4647519/s 744% 729% 338% 336% 336% + 331% 327% 327% 325% 324% 322% 14% + 14% 9% 8% 8% -- -2% +-2% -3% qr_const 4745450/s 762% 746% 347% 346% 345% + 340% 336% 336% 334% 333% 331% 16% + 16% 11% 11% 10% 2% -- +-0% -1% re_re 4748039/s 762% 747% 347% 346% 345% + 341% 336% 336% 335% 333% 331% 17% + 16% 11% 11% 10% 2% 0% + -- -1% re_str 4814042/s 774% 759% 353% 352% 352% + 347% 342% 342% 341% 339% 337% 18% + 18% 13% 12% 12% 4% 1% + 1% --

    — Ken

Re: Performance penalty of using qr//
by vr (Curate) on Dec 21, 2017 at 10:53 UTC

    I wonder about "(OBJECT,FAKE)" and why "MOTHER_RE" is there, and so maybe with pre-compiled qr Perl has to follow this chain to top mother each time it tries to match.

    >perl -MDevel::Peek -E "Dump qr/x/" SV = IV(0x2fda530) at 0x2fda540 REFCNT = 1 FLAGS = (TEMP,ROK) RV = 0x2fda588 SV = REGEXP(0x266a378) at 0x2fda588 REFCNT = 1 FLAGS = (OBJECT,FAKE) PV = 0x26d66a8 "(?^u:x)" CUR = 7 STASH = 0x2656a50 "Regexp" COMPFLAGS = 0x100 () EXTFLAGS = 0x680100 (CHECK_ALL,USE_INTUIT_NOML,USE_INTUIT_ML) ENGINE = 0x6e1a9ee0 (STANDARD) INTFLAGS = 0x0 () NPARENS = 0 LASTPAREN = 0 LASTCLOSEPAREN = 0 MINLEN = 1 MINLENRET = 1 GOFS = 0 PRE_PREFIX = 5 SUBLEN = 0 SUBOFFSET = 0 SUBCOFFSET = 0 SUBBEG = 0x0 MOTHER_RE = 0x26626f8 SV = REGEXP(0x267aff0) at 0x26626f8 REFCNT = 2 FLAGS = () PV = 0x26d66a8 "(?^u:x)" CUR = 7 COMPFLAGS = 0x100 () EXTFLAGS = 0x680100 (CHECK_ALL,USE_INTUIT_NOML,USE_INTUIT_ML) ENGINE = 0x6e1a9ee0 (STANDARD) INTFLAGS = 0x0 () NPARENS = 0 LASTPAREN = 0 LASTCLOSEPAREN = 0 MINLEN = 1 MINLENRET = 1 GOFS = 0 PRE_PREFIX = 5 SUBLEN = 0 SUBOFFSET = 0 SUBCOFFSET = 0 SUBBEG = 0x0 MOTHER_RE = 0x0 PAREN_NAMES = 0x0 SUBSTRS = 0x26b20b8 PPRIVATE = 0x26c16e8 OFFS = 0x26c3878 QR_ANONCV = 0x0 SAVED_COPY = 0x0 PAREN_NAMES = 0x0 SUBSTRS = 0x26b3238 PPRIVATE = 0x26c16e8 OFFS = 0x26c3ab8 QR_ANONCV = 0x0 SAVED_COPY = 0x0

    p.s. BTW, to answer 1205970, $re is compiled once, either checking debug output, or "hoisting" first line of subroutine to top of the script, performance remains the same.

Re: Performance penalty of using qr// (the stupid way)
by Anonymous Monk on Dec 21, 2017 at 07:24 UTC

    But the result was more than disappointing:

    Same here, the benchmark doesn't run for me it simply dies

    Also you're using qr (compile regex) the stupid way sub blah { my $re = qr...;

    But you're not alone, see qr//i versus m//i

      the benchmark doesn't run for me it simply dies

      You’re probably running a 32-bit version of Perl. I did mention that my testing was confined to 64-bit versions, but I should have emphasised this as a requirement. Sorry.

      Also you're using qr (compile regex) the stupid way

      Thanks for the link, but I don’t understand what you’re getting at. What would the clever way be?

      Athanasius <°(((><contra mundum Iustus alius egestas vitae, eros Piratica,

        compile once and cache as intended? That is  our $re; $re ||= qr...;

        im afk atm ; you might gain some insight about when regex are compiled using

        re  use re 'debug';

Re: Performance penalty of using qr//
by Jenda (Abbot) on Dec 22, 2017 at 00:08 UTC

    IMNSHO, there's no point in using qr// for regexps that are not built out of string in variables. If the whole regex is static, Perl is clever enough to optimize it. It's only if the code contains things like $foo =~ /bar$baz\wbat/ that Perl needs some help in deciding whether it needs to compile the regex again or whether it can reuse the one from the previous iteration.

    Jenda
    Enoch was right!
    Enjoy the last years of Rome.

        And? It's irrelevant whether you interpolate a string or a qr// compiled regexp into a regexp. How's that in disagreement with what I wrote?

        Jenda
        Enoch was right!
        Enjoy the last years of Rome.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1205956]
Approved by LanX
Front-paged by LanX
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2024-03-28 17:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found