Branch: refs/heads/davem/intuit_anchored
Home: https://github.com/Perl/perl5
Commit: 4d2f908abe3c7081a026a0cce8ba3e506d561fa1
https://github.com/Perl/perl5/commit/4d2f908abe3c7081a026a0cce8ba3e506d561fa1
Author: David Mitchell <[email protected]>
Date: 2026-06-24 (Wed, 24 Jun 2026)
Changed paths:
M regexec.c
M t/perf/benchmarks
Log Message:
-----------
regex: fail quicker for anchored patterns
GH #24272
This commit speeds up certain pattern matches which are expected to
fail; i.e. they now fail more quickly. It also makes a few cases slower.
It does this by altering how intuit() makes use of the fixed and
floating substrings in the presence of an absolute anchor.
It also adds many new regex benchmark entries.
Background:
Often the regex engine uses an initial "intuit" stage where, during
pattern compilation the longest anchored and floating substrings in the
pattern are identified and pre-processed. Then at run time, it quickly
scans the target string for those two patterns using Fast Boyer Moore
(FBM). This scan can either find ("intuit") the minimum start position
to run the main regex engine from, or reject the match completely if not
found.
For example,
/...abc.*wxyz/
has an anchored substring 'abc' which must match at offset 3,
and a floating substring 'wxyz' which must match at offset 6..infinity.
FBM has the useful property whereby when looking for a substring of
length N, it ideally only has to read every N'th byte in the target
string when scanning for the substring. So the longer the substring, the
more efficient the scan (in general).
Because of this FBM property, the intuit() code favours using the longest
out of the anchored and floating substrings first: this is designated as
the 'check' substring in the code. It searches for the check substring,
and if a candidate if found, it then looks for the other of the
anchored/floating with suitable start/end constraints based on the first
match (It's referred to as 'other' in the code.) If that fails, it goes
back to looking for the 'check' substring again further along the target
string.
When the pattern includes an absolute anchor such as /^/, /\A/ or /\G/
(as opposed to /^/m which can be anchored in many places), then intuit()
behaves differently. It's no longer looking for a suitable starting
point: the starting point has to be at the beginning of the string for
/\A/ or at pos() for /\G/. Instead, intuit() is just being used as a
fast-fail check before potentially running the full regex engine.
(intuit() has some other checks too, such as looking for a known synthetic
character class as the start of the pattern, which I haven't discussed
here to keep things simple.)
The issue:
The intent of the existing intuit code for the absolute anchor case
appears to be to just look for the anchored string at a fixed offset
(i.e. just using memNE() rather than scanning with FBM) as a quick-fail
option, but has a design flaw. It basically does:
if the 'check' substring is the anchored string (i.e. its min==max),
then do memNE() with it at the fixed offset, and return success/fail
immediately. Otherwise do a normal FBM scan of check then other.
Unfortunately, if the floating substr is the longest, and thus is picked
at pattern compile time as 'check', then this quick test will be skipped,
and the full FBM will be run on 'check' and then 'other'.
In the original bug report, this was causing code like this to take too
long to fail:
$_ = ' ' x 10_000_000;
for my $i (1..10_000) {
/\A .. abc .*? defghi /x;
}
This was because it was uselessly scanning a huge string for 'defghi'
when it could have quickly rejected the match just by checking for the
lack of string 'abc' at fixed offset 2.
The fix in this commit is to just always use only the *anchored* substring
(if present), rather than only using it if it is the longest and doing
the full check/other scan otherwise.
The original report in GH #24272 actually concerned \G rather than \A,
and how it had got slower from 5.20.0 onwards. In fact before 5.20,
the regex engine didn't use intuit in the presence of \G; since then it
has, resulting in speedups when length(anchored) > length(floating), and
buggy slowdowns otherwise. I.e. since 5.20, \A and \G now have similar
performance trade-offs.
There is still the issue of what intuit() should do in the case of
successfully locating the anchored substring: whether to also FBM scan
for the floating substring for a further possible quick-fail. This is a
trade-off, and in this fix I have chosen *not* to also scan for
floating. I.e. if intuit() matches the fixed substring, then control is
immediately passed to the regex engine (well, after an stcass check
anyway), which will then try to match e.g. '.*?abc' using the usual STAR
and EXACT nodes.
By having intuit *not* scan for float after finding fixed in an anchored
pattern, the following main performance trade-offs occur:
1) if the float is present, e.g. in
"abc". ('-'- x1_000_000) . "def" = @/^abc.*def/
then this choice avoids scanning a long strong for "def" using FBM,
finding it, only to then running the regex engine and find it again. The
initial FBM is a waste of time. So my choice is a win here.
2) if the float isn't present but the main regex will reject quickly
anyway, e.g. in
"abc". ('-'- x1_000_000)" = @/^abc\w+.*def/
then the main engine never scans for "def" because the \w+ fails early
on. SP doing a full FBM scan for "def" will typically have been an
expensive waste of time for a string pf significant length. So my choice
is a big win here for long strings.
3) if the float isn't present but the main regex won't reject quickly
e.g. in
"abc". ('-'- x1_000_000)" = @/^abc.*def/
then the main engine scans the *whole* string for "def" using the
inefficient (relative to FBM) method before eventually failing. In the
benchmarks added with this commit, this is about 50 times slower in
terms of instruction count than if "def" had been searched for and
failed using FBM in intuit. So my choice is a big loss here.
Ultimately, intuit() is all about guesswork and trade-offs. But it's a
bit of mess, and ideally in the longer term it would be integrated more
closely with the main engine. For example each EXACT node in the engine
aught to have a pre-computed (or on-the-fly and cached) FBM table,
possibly integrated with the character(s) which precede it, e,g.
/\d+cdef/ might have some sort of modified FBM that quickly scans for
"<digit>cdef". At the moment intuit feels a bit like a water bed;
optimise by pushing down on corner and another area pops up.
Also, intuit could probably benefit from some of its optimisation
choices being influenced by the length of the target string.
This commit also adds about 1100 benchmarks to t/perf/benchmarks, most
of which are algorithmically generated permutations of fixed and
floating substrings, synthetic class, and anchor, which collectively
exercise the main (but not all) pathways through intuit(), and the main
trade-offs.
Of those benchmarks, 6 are 50x slower after this commit (they represent
case 3 above); a further 6 are about 25% slower; they represent case (2)
above, except that if the strings in the benchmarks had been a lot
longer (i.e. Mb, as in the code in the original bug report), then they
would have started being faster instead; about 1000 are unchanged, and
about 180 are faster (between 101% and 412%).
Commit: 8a28c66452ef0ccbe7d3be7982915e5442eabbc7
https://github.com/Perl/perl5/commit/8a28c66452ef0ccbe7d3be7982915e5442eabbc7
Author: David Mitchell <[email protected]>
Date: 2026-06-24 (Wed, 24 Jun 2026)
Changed paths:
M pod/perldelta.pod
Log Message:
-----------
perldelta entry for regex intuit performnce fix
Compare: https://github.com/Perl/perl5/compare/4d2f908abe3c%5E...8a28c66452ef
To unsubscribe from these emails, change your notification settings at
https://github.com/Perl/perl5/settings/notifications
