develooper Front page | perl.perl5.porters | Postings from August 2012

[perl #114636] Pathological performance problem with RegExp engine

Thread Next
From:
James E Keenan via RT
Date:
August 29, 2012 17:51
Subject:
[perl #114636] Pathological performance problem with RegExp engine
Message ID:
rt-3.6.HEAD-11172-1346287905-1503.114636-15-0@perl.org
On Tue Aug 28 00:52:27 2012, malch@malch.com wrote:
> This is a bug report for perl from malch@malch.com,
> generated with the help of perlbug 1.39 running under perl 5.12.3.
> 
> 
> This problem has also been reproduced on
> 
> * ActivePerl 5.14.2 on Windows 7 64-bit
> 
> * Perl 5.8.8 built for i686-linux
> 
> The following RegExp does not match and indeed it should not.
> However, execution requires more than 120 seconds of CPU and
> this increases exponentially as $string is lengthened.
> 
> 
> $string=q~
>
/#20Char#20Char1/Span/#20Char#20Char2/Span/#20Char#20Char3/Span/#20Char#20Char4/Span/#20Char#20Char5/Span/#20Char#20Char6/Span/Table#20of#20Figures/P/InlineShape/Figure/Default/P/References#20Char/Span/HeadTOC/P/DropCap/Figure/CM66/P/CM67#20Char/Span/Outline/Span/Subscript/Span/Superscript/Span/TableTitle#20Char/Span/Figure#20Heading#20Char/Span/Albany2/P/CM17/P/Caption/P/TOA/TOC/Page#20Number/Span/TOF/TOC/Emphasis/Span/Strikeout/Span/Body#20Char/Span/TextBox/Div/Heading#201/H1/heading#201/P/Heading#202/H2/heading#202/P/Heading#203/H3/Normal/P/h
> ~;
> $pdf='\s*(/\S+\s*){0,5}/xxx';
> if ($string=~m/$pdf/is) {
>    print "Hit\n";
> } else {
>    print "Miss\n";
> }
> 

Confirmed on 5.16.0 on Linux/i386.  Observed that the big difference is
between:

$pdf='\s*(/\S+\s*){0,5}/xxx';

and either:

$pdf='\s*(/\S+\s*){0,1}/xxx';

or:

$pdf='\s*(/\S+\s*)?/xxx';

Thank you very much.
Jim Keenan


---
via perlbug:  queue: perl5 status: new
https://rt.perl.org:443/rt3/Ticket/Display.html?id=114636

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