develooper Front page | perl.perl5.porters | Postings from March 2011

Re: [perl #76546] regex engine slowdown bug

Thread Previous | Thread Next
From:
demerphq
Date:
March 31, 2011 01:16
Subject:
Re: [perl #76546] regex engine slowdown bug
Message ID:
AANLkTi=6y1CN-WqCKhz1qagLAeWkC6UQV3AL56x_zBXD@mail.gmail.com
On 24 July 2010 17:46, Dave Mitchell <davem@iabyn.com> wrote:
> The original of this bug report didn't make it to the p5p mailing
> list; presumably because the original test script included 0.5Mb of sample
> HTML. The following demonstrates the same slowdown while generating its
> own sample HTMl data:
>
>    #!/usr/bin/perl
>    use Time::HiRes qw( time );
>
>    my $html = qq{<div class="boo">\n} x 30_000;
>
>    sub try {
>        my ($re) = @_;
>        my $t = time;
>        $html =~ /$re/;
>        warn sprintf "%7.4f sec, regexp is %s\n", time-$t, $re;
>    }
>
>    try(qr{<div class="marketsort[^>]*(?-i:>)\s*}ms);
>    try(qr{<div class="marketsort[^>]*(?:>)\s*}ims);
>    try(qr{<div class="marketsort[^>]*(?-i:>)}ims);
>    try(qr{<div\sclass="marketsort[^>]*(?-i:>)\s*}ims);
>    try(qr{<div class="marketsort[^>]*(?-i:>)\s*}ims);
>    warn "FINISHED\n";
>
> which on blead gives:
>
>     0.0004 sec, regexp is (?ms-xi:<div class="marketsort[^>]*(?-i:>)\s*)
>     0.0041 sec, regexp is (?msi-x:<div class="marketsort[^>]*(?:>)\s*)
>     0.0048 sec, regexp is (?msi-x:<div class="marketsort[^>]*(?-i:>))
>     0.0163 sec, regexp is (?msi-x:<div\sclass="marketsort[^>]*(?-i:>)\s*)
>    61.5914 sec, regexp is (?msi-x:<div class="marketsort[^>]*(?-i:>)\s*)
>    FINISHED
>
> The time of the last pattern is quadratic on RHS of 'x' in the $html
> assignment.
>
> I haven't looked into any further than that.

We never fixed the superlinear cache bug that was broken some time
around when the engine was derecursivized.

Id bet a dollar this is related.

Yves


-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About