Branch: refs/heads/davem/slc
  Home:   https://github.com/Perl/perl5
  Commit: 0461c487a11a925e8794c74e3da5ccdcf3ca98c7
      
https://github.com/Perl/perl5/commit/0461c487a11a925e8794c74e3da5ccdcf3ca98c7
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M regcomp.c
    M regcomp.h
    M regcomp_debug.c
    M regcomp_internal.h
    M regcomp_study.c
    M regexec.c
    M t/re/pat.t

  Log Message:
  -----------
  regex: improve counting SLC WHILEM nodes

Some WHILEM nodes participate in the super-linear cache (SLC). This
commit improves and simplifies the code which generates the ids for
those nodes during compilation, along with a count of the total number
of such nodes.

The main visible difference from this commit is that the SLC is no
longer sometimes over-allocated. Consider this example on normal and
modified perls:

$ perl -Dr -e'qr/(aa?)*(bb?)*(cc?){1,5}(dd?)*/' 2>&1 | grep WHILEM
  17: WHILEM[1/4] (0)
  35: WHILEM[2/4] (0)
  53: WHILEM (0)
  71: WHILEM[3/4] (0)

$ ./perl -Dr -e'qr/(aa?)*(bb?)*(cc?){1,5}(dd?)*/' 2>&1 | grep WHILEM
  17: WHILEM[1/3] (0)
  35: WHILEM[2/3] (0)
  53: WHILEM (0)
  71: WHILEM[3/3] (0)

In this pattern there are four WHILEM nodes, but only three of them can
participate in the SLC. Previously the SLC code allocated (string
length) x 4 bits for the cache, even though only x 3 was needed.

The simplification is that there is a new field slc_whilem_seen added to
the regexp_internal struct which, during compilation, is incremented
each time an SLC-capable WHILEM node is identified, and then at run-time
is used in the calculation for allocating the cache.

Formerly, the U8 FLAGS() field of the WHILEM node stored two 4-bit
values: the node id and the total - i.e. the two values displayed in
'WHILEM[2/4]'.

But there is no point storing the *same* total value in every FLAGS()
field - just store it once in the regex_internal struct. So now the
FLAGS() field only holds the id, which in principle is now limited to
255 rather than 15 nodes (although this commit doesn't change that
limit).

Formerly, a count of the total number of WHILEM nodes seen was
accumulated in RExC_whilem_seen during parsing by reg(), which was then
capped to 15, and was subsequently used by study_chunk() as the value to
stuff into every FLAGS() field. Separately, study_chunk() maintained an
id count in the whilem_c field of the scan_data_t struct, which was also
copied to and from other scan_data_t structs when doing sub-scans. Both
of those fields have been eliminated.


  Commit: 2f91a6be29b95df5ad0f6b79eb4db6606d75f562
      
https://github.com/Perl/perl5/commit/2f91a6be29b95df5ad0f6b79eb4db6606d75f562
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M t/re/pat.t
    M t/re/re_tests

  Log Message:
  -----------
  regex: move SLC tests to pat.t

Move some tests for the super-linear cache from the generic
t/re/re_tests file into t/re/pat.t. This is in preparation for coming
modifications which can't be achieved within the standard re_tests
framework.

For now the actual tests are unchanged.


  Commit: 7a1ad982b5643bcd6cf64c2da92ac90063af3390
      
https://github.com/Perl/perl5/commit/7a1ad982b5643bcd6cf64c2da92ac90063af3390
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M t/re/pat.t

  Log Message:
  -----------
  regex SLC tests: use short cache delay

Update some tests in pat.t which exercise the super-linear cache.

Use the new ${^RE_SUPERLINEAR_CACHE_DELAY} facility to enable the cache
*immediately*. This will future-proof the tests against changes to the
cache-enabling delay algorithm, and also allows the first half of some
of the test patterns to be removed, which were only there to cause
enough backtracking to enable the cache.


  Commit: 1d29fbd18e8f041082a1257634c12c961b60b3c9
      
https://github.com/Perl/perl5/commit/1d29fbd18e8f041082a1257634c12c961b60b3c9
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M regexec.c

  Log Message:
  -----------
  regex: improve cur_eval debugging output

Standardise the debugging output which is emitted when cur_eval is
updated. Use the same message format in all instances, and include an
extra location which sets cur_eval but didn't emit debugging info.

Also correct the state name in a few debugging messages, e.g.
    "EVAL_AB_fail" => "EVAL_postponed_A/B_fail".


  Commit: cad50495be02261c206d127fa523482e1af84eab
      
https://github.com/Perl/perl5/commit/cad50495be02261c206d127fa523482e1af84eab
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M regexec.c
    M t/re/pat.t

  Log Message:
  -----------
  regex SLC: ignore inner patterns

There are two main issues with calling a separate sub-pattern via e.g.
(?1) or (??{ $subpattern_qr }) as regards the super-linear cache (SLC).

The first is that, in general, sub-patterns don't know their calling
environment - e.g. whether they're nested within another (...)* -
which means that some of the assumptions the regex compiler relied on
when compiling the inner regex may be voided. Also, sub-patterns will
have their own set of WHILEM ids which don't mean the same thing as
their caller, so can't be used on the same cache. The cache may also
need to be a different size.

The second issue is that WHILEM nodes to the left of of the sub-pattern
call can no longer rely on the rest-of-pattern always being the same
(technically (?1) can be relied on, but (??{...}) certainly can't).

Both those issues are currently addressed by setting
reginfo->poscache_maxiter back to zero at the start of, the end of, and
when stack-popping from executing, the sub-pattern. This has the effect
of resetting both the cache countdown, and of clearing/resetting the
whole cache once the countdown has finished.

Some time soon I intend to move to an implementation where there is a
separate countdown and cache per WHILEM node rather than a global
per-match countdown. This commit and the next one are intended to move
away from relying on setting poscache_maxiter back to zero, which is a
crude technique anyway. It also potentially has problems if the reset
countdown finishes and actually re-enables the cache while executing the
inner pattern.

This commit addresses the first issue, while the next commit will
address the second.

This commit makes use of the existing cur_eval variable, which becomes
non-NULL during a call to a separate sub-pattern. The rule is simple:
skip setting a cache entry if cur_eval is true.

This commit still keeps the poscache_maxiter = 0 mechanism in place for
now as that is still needed for the second issue, addressed in the next
commit.


  Commit: fd1d59c1bed36cc2553da44c0338f05e81c069cb
      
https://github.com/Perl/perl5/commit/fd1d59c1bed36cc2553da44c0338f05e81c069cb
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M regexec.c
    M regexp.h
    M t/re/pat.t

  Log Message:
  -----------
  regex SLC: better ignore non-regular tails

This is the second of two commits to change the implementation of the
super-linear cache when it comes to non-regular items like \1 and
(??{...}).

See the previous commit message for an overview.

In contrast to that previous commit which disabled the cache while a
sub-pattern was being executed, this commit changes how the
rest-of-pattern tail is handled. Formerly when encountering something
like \1 or (?(cond)yes|no), the SLC countdown was reset so that the SLC
wouldn't be engaged for a while. More strictly, when encountering
sub-patterns like (?1) or (??{ $sub_qr }}), maxiter was set to zero so
that both a new countdown was triggered and the existing cache would be
zeroed out. Trying to prove that that approach is correct and efficient
is hard.

This commit takes a different approach. A new local boolean variable
seen_nonregular is added, which is set whenever a non-regular node such
as \1 is seen. It is used to veto setting cache entries. See the
update to perlreguts.pod in this commit for the full technical details.

This commit also removes all the setting of poscache_iter or
poscache_maxiter to zero, which was the previous crude way of
temporarily disabling the cache. This commit and the previous one
collectively have replaced that mechanism.


  Commit: 0f3f00fa88d27d4c02c99c02ea20d9c58c22a4af
      
https://github.com/Perl/perl5/commit/0f3f00fa88d27d4c02c99c02ea20d9c58c22a4af
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M regexec.c
    M regexp.h

  Log Message:
  -----------
  regex: SLC: eliminate realloc(), poscache_size

Two commits ago, the super-linear cache was changed to be disabled when
calling an inner sub-pattern (e.g. via /(??{$sub_qr })/ ). This means
that it is no longer possible for an inner pattern to allocate the SLC,
then when control returns to the outer pattern, for a different-sized
cache to be needed (or vice-versa).

Also, the previous commit eliminated resetting reginfo->poscache_maxiter
to signal that the cache should be re-zeroed and/or resized, so we
should never be in the position of wanting to malloc() a cache but
finding it was already allocated and needing to re-zero it.

So this commit eliminates the size check and realloc(), and replaces
it with a simple assert that the cache hasn't already been allocated.
Since we never need to know the cache's old size now, this commit
also eliminates the reginfo->poscache_size field.


  Commit: b0d1c050dc5a8d01cdc3be1b268758f712938287
      
https://github.com/Perl/perl5/commit/b0d1c050dc5a8d01cdc3be1b268758f712938287
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M t/re/pat_rt_report.t

  Log Message:
  -----------
  regex: SLC: skip sensitive test

A test in pat_rt_report.t counts the number of quantifier iterations it
executes. This test is sensitive to how quickly the super-linear cache
kicks in, so skip the test if the default delay has been overridden.

Note that before the start of this branch, building and running a perl
with the cache delay artificially lowered with
PERL_RE_SUPERLINEAR_CACHE_DELAY=1 caused a number of failures. As of
this commit, all tests pass.

The main failure (apart from the false positive fixed by this commit)
was that with an SLC countdown of exactly 1, it was possible to skip
resizing the cache when returning to an outer pattern from a smaller
(i.e. less WHILEM nodes) sub-pattern. Since inner sub-patterns don't do
cache now and so the cache is never resized, this is no longer an issue.


  Commit: e13fc553b63ae8e3219884ab3b7252215927be2e
      
https://github.com/Perl/perl5/commit/e13fc553b63ae8e3219884ab3b7252215927be2e
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M regcomp.c
    M regcomp.h
    M regexec.c
    M regexp.h
    M t/perf/benchmarks
    M t/re/pat.t

  Log Message:
  -----------
  regex: make super-linear cache per quantifier

Before this commit there was a single super-linear cache (SLC) per regex
execution. Consider for example a pattern such as the following

    /(...)*(...)*(...)*/

which has three SLC-compatible quantifiers. When matched against a 1
Mbyte string, the initial countdown would be set to 3E6, then after that
many WHILEM nodes had been executed, a single cache containing 3E6 bits
would be allocated.

Following this commit, there is a separate 1E6 countdown per WHILEM
node, then an individual 1E6 bit cache is allocated per node.

For a pattern where not all the quantifiers go super-linear, this has
the twin advantages that the SLC kicks in quicker (resulting in less
wasted iterations) and the amount of memory allocated is smaller.

As a concrete example, this match:

           "aa;bbbbbbbbbbbbbbbbbbbb;cc"
        =~ /^(aa?)*;(bb?)*bbbbbbbbbbbbbbbbbb;(cc?)*$/;

only goes super-linear in the second of the three '*' quantifiers.
Previously, running this pattern caused 122 WHILEM executions and
allocated 3*26 bits of cache. Now it's 71 and 1*26.

For longer strings, time and memory savings can become significant.

See the changes to perlreguts.pod contained in this commit for the
details of how the new system works.

Some of the commits prior to this one simplified things, such as
guaranteeing that a cache never needs to be re-allocated to a larger
size. In turn, this has made it possible to make some of the code in
this commit simpler or more efficient. For example ST.slc_bytep is now a
direct pointer to a byte in the cache, whereas previously
ST.cache_offset was an offset, which required more calculations on the
fly when setting a cache bit in CacheSayNO.

This commit also adds a depth field to the regexp_internal struct,
analogous to the CvDEPTH() field of a CV. This makes makes it easier to
detect whether a regex is being executed recursively; for example:

    sub f { ....; /....(?{ f($i-1) }) .../ }

This might turn out to be useful to simplify other things in the engine
(like capture offsets possibly), which currently have messy workarounds.


  Commit: bb4e410fa2a88da57fc68539f1dad46f495ee8d4
      
https://github.com/Perl/perl5/commit/bb4e410fa2a88da57fc68539f1dad46f495ee8d4
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M regexec.c
    M t/perf/benchmarks
    M t/re/pat_rt_report.t

  Log Message:
  -----------
  regex: super-linear cache; shorter countdown

The countdown initiated by each WHILEM node is a guess of when the match
will start to go super-linear. It is currently set to to the length of
the string.

This commit changes the countdown to instead be equal to the length of
the *remaining* string. This may make the cache kick in sooner when the
string is long but the super-linear backtracking behaviour is only
happening towards the end of the string. See the code in the added
benchmark entry for an example.

This if of course just a heuristic. This commit will cause some patterns
to allocate a cache where before they didn't, while making other
patterns needlessly backtrack less. But now that a 1/Nth size cache is
allocated per WHILEM node rather than a single monolithic cache per
regex run, getting this guess wrong is less harmful.

Note that this doesn't affect the size of the cache: that still gets
allocated a bit per string byte, because a later iteration of a WHILEM
node might be at an earlier string position.

A test in t/re/pat_rt_report.t is annoyingly sensitive to the number
of backtracking iterations. My final fix for this test is to ignore how
many iterations it does, but instead make sure that for any iterations
it *does* do, @- always has two elements. (In the original bug report,
it sometimes had a spurious undef third element.)


  Commit: cc611faf1bcc0680d5420f29d90ae73df6c8c15e
      
https://github.com/Perl/perl5/commit/cc611faf1bcc0680d5420f29d90ae73df6c8c15e
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perlreguts.pod
    M regcomp_study.c

  Log Message:
  -----------
  regex: increase 15->30 max super-linear cache node

There is currently a limit of 15 on the number of WHILEM nodes which can
participate in the super-linear cache. This used to be a hard limit, as
the node index was stored in the upper 4-bits of the 8-bit FLAGS()
field of the node.

Now the index uses all 8 bits, so there is a theoretical hard upper
limit of 255. This commit increases the actual limit from 15 to 30.

A higher limit means that more quantifiers in very complex patterns can
make use of the cache, so less backtracking might ensue. The downside is
that more cache memory may be allocated, although the cache is now
allocated per-node, so it won't necessarily use more memory.

By not going immediately to 255, this commit is a cautious first step.


  Commit: b04c5c7660a607110d73f592c6758279ad8429ff
      
https://github.com/Perl/perl5/commit/b04c5c7660a607110d73f592c6758279ad8429ff
  Author: David Mitchell <[email protected]>
  Date:   2026-09-27 (Sun, 27 Sep 2026)

  Changed paths:
    M pod/perldelta.pod

  Log Message:
  -----------
  perldelta: performance of regex super-linear cache


Compare: https://github.com/Perl/perl5/compare/e85306177f7c...b04c5c7660a6

To unsubscribe from these emails, change your notification settings at 
https://github.com/Perl/perl5/settings/notifications

Reply via email to