develooper Front page | perl.perl5.porters | Postings from February 2008

Re: Slowdown in 5.10.0 regexes with atomic patterns

Thread Previous | Thread Next
From:
Moritz Lenz
Date:
February 6, 2008 04:20
Subject:
Re: Slowdown in 5.10.0 regexes with atomic patterns
Message ID:
47A96A8A.8080101@casella.verplant.org
Dave Mitchell wrote:
> On Mon, Jan 28, 2008 at 11:50:23PM +0100, Andreas J. Koenig wrote:
>> >>>>> On Mon, 28 Jan 2008 15:35:49 +0100, Moritz Lenz <moritz@casella.verplant.org> said:
>> 
>>   > Andreas, could you please use your magic binary search to find out which
>>   > patch introduced the slowdown?
>> 
>> ----Program----
>> use strict;
>> use warnings;
>> my $str = "bea" x 100;
>> my $re = qr/(?:be|ea|a)/;
>> use Benchmark qw(timeit);
>> use Time::HiRes qw(time);
>> my $start = time;
>> timeit(500, sub { die if $str =~ m/(?>$re+)\d/ });
>> my $x = time - $start;
>> print $x, "\n";
>> 
>> ----Output of .../p3BBpDI/perl-5.9.3@27902/bin/perl----
>> 0.653790950775146
>> 
>> ----EOF ($?='0')----
>> ----Output of .../pcL5RMw/perl-5.9.3@27903/bin/perl----
>> 23.4941339492798
>> 
>> ----EOF ($?='0')----
>> 
>> Change 27903 by davem@davem-cyril on 2006/04/19 13:56:07
>> 
>>         regmatch(): make IFMATCH use PUSH_STACK rather than fake recursion
> 
> It's fundamentally due to the fact that I removed the +ve superlinear cache
> code (leaving only the -ve version), on the grounds that I couldn't work
> out how it could ever be triggered, and that none of the existing test
> suite triggered it, and that it was getting in the way of me making the regex
> engine non-recursive.
> 
> Now someone's found a test case, so I'll have to think of a way of
> re-adding the +ve cache :-)

Actually I don't know if it's worth the trouble, because the regex isn't
really useful for anything - normally such a regexp would either be
anchored (in which case it doesn't show that slowdown), or as dmq
pointed out, it would contain a (*COMMIT) before the \d.

So until somebody finds an example from the wild (and not one
hand-crafted to measure performance of atomic groups) I'd consider that
an academic problem.

Moritz

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