Slowdown in 5.10.0 regexes with atomic patterns #9751
Comments
From @nwc10Moritz Lenz mailed p5p in 479DE845.20803@casella.verplant.org Following up on a perlmonks thread: https://www.perlmonks.org/?node_id=664545 Summary: some regexps with atomic groups are much slower on 5.10.0 than Dave notes: +ve superlinear cache issue |
From p5p@spam.wizbit.beBisect from the thread: (from andreas) ----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---- ----EOF ($?='0')---- ----EOF ($?='0')---- Change 27903 by davem@davem-cyril on 2006/04/19 13:56:07 regmatch(): make IFMATCH use PUSH_STACK rather than fake |
|
p5p@spam.wizbit.be - Status changed from 'new' to 'open' |
From @schwernThis is a duplicate of 58280. |
From @nwc10On Sat Jul 11 02:04:13 2009, schwern wrote:
It does seem to be related. Comparing a perl built immediately before $ /home/nick/Sandpit/snap5.9.x-perl-5.8.0-7777-g20f9f80/bin/perl5.9.4 58280 $ /home/nick/Sandpit/snap5.9.x-perl-5.8.0-7777-g20f9f80/bin/perl5.9.4 66106 (perls admittedly not ideal, as built with -DDEBUGGING and without any ./Configure ... -Dnoextensions=IPC/SysV && perl -i -ne 'print unless change 27093 is regmatch(): make IFMATCH use PUSH_STACK rather than fake recursion ) Nicholas Clark |
From @hvds"Nicholas Clark via RT" <perlbug-followup@perl.org> wrote: I investigated this a bit, using the test cases: .. and the two perls 5.8.8 and blead.[1] The -Dr differences show that in all 4 cases we turn on superlinear caching: I'll look through the code to try to understand why this fails, but Hugo [1] The artificial '[bc]' is to avoid TRIE conversion, so as to keep the [2] In this case tries are also a big lose: 'aa|b' takes 50-100% longer |
From @hvdshv@crypt.org wrote: Ah no, it's a bit trickier than that. I've confused myself quite a bit, so some of the below may be wrong. 1. The superlinear cache is an optimisation specific to a single opcode, 1a. In the first program the B pattern is /\d/, while in the second it 2. Once superlinearity is detected, and the cache is enabled, cache bits 3. When wrapped in the cut operator (?>...), the backtracking doesn't This is why the second program exhibits exponential behaviour in blead. 4. In 5.8.8, we supported caching of either failure or success - we 5. That dual-mode cache was removed in patch #28571), because as far I don't have a clear idea how to fix this: I feel the right answer may Dave, I think most of the current version of this code is yours - does Hugo |
From @obra~dupe of 58280. Removing as a 5.12 blocker. |
#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
use Benchmark qw(cmpthese);
my $str = "bea" x 100;
my $re = qr/(?:be|ea|a)/;
cmpthese(-2, {
atomic1 => sub { die if $str =~ m/(?>$re+)\d/ },
atomic2 => sub { die if $str =~ m/(?>$re)+\d/ },
normal => sub { die if $str =~ m/$re+\d/ },
posessive => sub { die if $str =~ m/$re++\d/ },
});
__END__ |
toddr
added
the
Closable?
|
On Tue, 4 Feb 2020 at 23:44, Todd Rinaldo ***@***.***> wrote:
#!/usr/bin/perluse strict;use warnings;use 5.010;use Benchmark qw(cmpthese);
my $str = "bea" x 100;my $re = qr/(?:be|ea|a)/;
cmpthese(-2, {
atomic1 => sub { die if $str =~ m/(?>$re+)\d/ },
atomic2 => sub { die if $str =~ m/(?>$re)+\d/ },
normal => sub { die if $str =~ m/$re+\d/ },
posessive => sub { die if $str =~ m/$re++\d/ },
});
Before we can address this ticket we need to remove the confusion from it.
Possessive and atomic1 are literally identical. They produce exactly the
same regexp program, any observed difference in their performance is a
timing artifact or a byproduct of this code recompiling the regex over and
over during the benchmark.
So that leaves three patterns to consider. normal, atomic1, normal, atomic2.
The next thing to do is run them under C<use re 'debug';> and compare their
output.
$ perl re.pl normal > normal.out 2>&1
$ perl re.pl atomic1 > atomic1.out 2>&1
$ perl re.pl atomic2 > atomic2.out 2>&1
To do this it helps to pass the output thorugh a normalizing filter so that
irrelevant differences dont confuse things:
perl -lpe's/\(\d+\)//; s/\d+://; s/\|\s+([A-Z])/|$1/; s/\|\s*\d+\|/ \| /;'
normal.out > normal.cln
perl -lpe's/\(\d+\)//; s/\d+://; s/\|\s+([A-Z])/|$1/; s/\|\s*\d+\|/ \| /;'
atomic1.out > atomic1.cln
perl -lpe's/\(\d+\)//; s/\d+://; s/\|\s+([A-Z])/|$1/; s/\|\s*\d+\|/ \| /;'
atomic2.out > atomic2.cln
Then you can diff.
If you look at the three cases normal and atomic2 are very similar. The
(?>...) essentially doesn't do anything in the atomic2 pattern, and our
benchmark shows that the performance is not very different.
atomic2 8253/s
normal 9635/s
And we can see this in the diff as well:
```diff
-Compiling REx "(?^:(?:be|ea|a))+\d"
+Compiling REx "(?>(?^:(?:be|ea|a)))+\d"
Final program:
CURLYX[0]{1,INFTY}
+ SUSPEND
TRIE-EXACT[abe]
<be>
<ea>
<a>
+ SUCCEED
+ TAIL
WHILEM[1/1]
NOTHING
POSIXU[\d]
END
minlen 2
-Matching REx "(?^:(?:be|ea|a))+\d" against
"beabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabea"...
+Matching REx "(?>(?^:(?:be|ea|a)))+\d" against
"beabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabeabea"...
0 <> <beabeabeab> | CURLYX[0]{1,INFTY}
0 <> <beabeabeab> | WHILEM[1/1]
| WHILEM: matched 0 out of 1..65535
+ 0 <> <beabeabeab> | SUSPEND
0 <> <beabeabeab> | TRIE-EXACT[abe]
0 <> <beabeabeab> | TRIE: State: 1 Accepted: N TRIE:
Charid: 1 CP: 62 After State: 2
1 <b> <eabeabeabe> | TRIE: State: 2 Accepted: N TRIE:
Charid: 2 CP: 65 After State: 3
@@ -29,16 +33,22 @@
| TRIE: got 1 possible matches
| TRIE matched word #1, continuing
| TRIE: only one match left,
short-circuiting: #1 <be>
+ 2 <be> <abeabeabea> | SUCCEED
+ | SUCCEED: subpattern success...
```
So basically the slowdown is from executing the extra SUSPEND/SUCCEED pair,
which is pretty much expected. Maybe SUSPEND can be optimized a bit, but
there isn't much to see here.
So that means we need to compare normal and atomic1, which reveals far too
many differences to include in this mail.
One of the *key* differences is that in the normal case we see this:
WHILEM: (cache) already tried at this position...
which we do not see at all from atomic1. So, something about SUSPEND
disables the super-linear cache. If there is a bug we should focus on this.
On the other hand, these are extremely stupid patterns. They are
unanchored, which is part of the reason the super-linear cache is
important. Every time we fail to match, the regex engine advances the start
point by a character and tries it again. The recursive regexp engine design
we use is not capable (without *great* effort which is unlikely to be every
provided) to determine that anything that matches (be|ea|a) *cannot* *ever*
match \d. Now, we humans are quite capable of this analytical task with
almost no effort at all, which reveals that this pattern would be *greatly*
helped by a (*SKIP) directive.
So, yes, there is a bug here we should figure out. Why does SUSPEND
break/disable the super-linear cache?
But ultimately the use of SUSPEND/possessive match here is simply not the
right thing to do, and doesn't help that much with an unanchored pattern
anyway.
$ perl re_bm.pl
Rate possessive atomic1 atomic2 normal skip
possessive 660/s -- -0% -95% -96% -96%
atomic1 663/s 0% -- -95% -96% -96%
atomic2 13460/s 1939% 1929% -- -15% -26%
normal 15761/s 2287% 2276% 17% -- -14%
skip 18266/s 2667% 2654% 36% 16% --
$ cat re_bm.pl
#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
use Benchmark qw(cmpthese);
my $str = "bea" x 100;
my $re = qr/(?:be|ea|a)/;
cmpthese(-2, {
atomic1 => sub { die if $str =~ m/(?>$re+)\d/o },
possessive => sub { die if $str =~ m/$re++\d/o },
atomic2 => sub { die if $str =~ m/(?>$re)+\d/o },
normal => sub { die if $str =~ m/$re+\d/o },
skip => sub { die if $str =~ m/$re(*SKIP)\d/o },
});
$ cat re.pl
#!/usr/bin/perl
use strict;
use warnings;
use re 'debug';
my $str = "bea" x 100;
my $re = qr/(?:be|ea|a)/;
my $type= shift || "normal";
print "type= $type\n";
if ($type eq "atomic1") {
$str =~ m/(?>$re+)\d/;
} elsif ($type eq "atomic2"){
$str =~ m/(?>$re)+\d/;
} elsif ($type eq "normal") {
$str =~ m/$re+\d/;
} elsif ($type eq "possessive") {
$str =~ m/$re++\d/;
} elsif ($type eq "skip") {
$str =~ m/$re+(*SKIP)\d/;
}
$ cat re_bm_qr.pl
#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
use Benchmark qw(cmpthese);
my $str = "bea" x 100;
my $re = qr/(?:be|ea|a)/;
my $atomic1= qr/(?>$re+)\d/;
my $atomic2= qr/(?>$re)+\d/;
my $possessive= qr/$re++\d/;
my $normal= qr/$re+\d/;
my $skip= qr/$re+(*SKIP)\d/;
cmpthese(-2, {
atomic1 => sub { die if $str =~ m/$atomic1/o },
possessive => sub { die if $str =~ m/$possessive/o },
atomic2 => sub { die if $str =~ m/$atomic2/o },
normal => sub { die if $str =~ m/$normal/o },
skip => sub { die if $str =~ m/$skip/o },
});
$ perl re_bm_qr.pl
Rate possessive atomic1 atomic2 normal skip
possessive 682/s -- -0% -95% -96% -99%
atomic1 684/s 0% -- -95% -96% -99%
atomic2 14166/s 1976% 1972% -- -15% -87%
normal 16665/s 2343% 2338% 18% -- -84%
skip 106189/s 15464% 15433% 650% 537% --
$ cat re_bm_qr_anch.pl
#!/usr/bin/perl
use strict;
use warnings;
use 5.010;
use Benchmark qw(cmpthese);
my $str = "bea" x 100;
my $re = qr/(?:be|ea|a)/;
my $atomic1= qr/^(?>$re+)\d/;
my $atomic2= qr/^(?>$re)+\d/;
my $possessive= qr/^$re++\d/;
my $normal= qr/^$re+\d/;
my $skip= qr/^$re+(*SKIP)\d/;
cmpthese(-2, {
atomic1 => sub { die if $str =~ m/$atomic1/o },
possessive => sub { die if $str =~ m/$possessive/o },
atomic2 => sub { die if $str =~ m/$atomic2/o },
normal => sub { die if $str =~ m/$normal/o },
skip => sub { die if $str =~ m/$skip/o },
});
$ perl re_bm_qr_anch.pl
Rate atomic2 normal possessive atomic1 skip
atomic2 63150/s -- -19% -37% -39% -41%
normal 78442/s 24% -- -22% -25% -26%
possessive 100604/s 59% 28% -- -4% -6%
atomic1 104259/s 65% 33% 4% -- -2%
skip 106684/s 69% 36% 6% 2% --
Cheers,
yves
…--
perl -Mre=debug -e "/just|another|perl|hacker/"
|
toddr
removed
the
Closable?
|
I'll summarize all of the above with this quote from @demerphq from it
But ultimately the use of SUSPEND/possessive match here is simply not the |
|
Although I probably should eat my words on this:
It occurs me to me reading this today that if the code is TRIE'd then we can. We can't generally, in the sense that if 'be', 'ea' and 'a' are arbitrary patterns, but as written we /could/ tell that they cant match \d. Not sure how much it would help, and if the extra compile time would justify it. But in theory provided the alternation can be converted to a TRIE we could. But it seems to me reading this now that we should be investigating the core point, why does SUSPEND disable the super linear cache? |
|
On Thu, Apr 14, 2022 at 07:43:03AM -0700, Yves Orton wrote:
But it seems to me reading this now that we should be investigating the
core point, why does SUSPEND disable the super linear cache?
I can't speak for SUSPEND directly, but in general the cache is disabled
for the types of pattern elements which can break the assumption that
if a particular CURLYX/WHILEM with infinite upper bound failed once at
position N in the string, then it will fail at that position any other
time we might try. So if we ever reach that combo of CURLYX number (up to
16 of them) and position in the string (as indicated by a bit set in the
S-L cache), then there's no point continuing, as we're sure it will fail at
some point further along in the pattern. A lot of the "non-regularly" bits
of regexes, like \1, breach this assumption, and so their presence
disables the cache.
…--
The crew of the Enterprise encounter an alien life form which is
surprisingly neither humanoid nor made from pure energy.
-- Things That Never Happen in "Star Trek" #22
|
Migrated from rt.perl.org#66106 (status was 'open')
Searchable as RT66106$
The text was updated successfully, but these errors were encountered: