Branch: refs/heads/yves/octet_trie_followups
  Home:   https://github.com/Perl/perl5
  Commit: 20d2fde9a4078fb174967036b65204710a73a953
      
https://github.com/Perl/perl5/commit/20d2fde9a4078fb174967036b65204710a73a953
  Author: Yves Orton <[email protected]>
  Date:   2026-10-14 (Wed, 14 Oct 2026)

  Changed paths:
    M pod/perldelta.pod
    M regcomp.c
    M regcomp.h
    M regcomp_trie.c
    M regexec.c
    M t/re/pat.t

  Log Message:
  -----------
  regex: accelerate Aho-Corasick scans with octet prefilters

complement Aho-Corasick matching, which can be slow, with various optimized
prefilters to find likely start points. These prefilters include a
Boyer-Moore-Horspool (BMH) shift tables of the words in the Aho-Corasick/Trie,
which can allow us to scan the string without actually looking at every octet,
along with a unified bitmap which allows us to track the legal start octets in
both latin-1 and utf8 in one data structure.

We also include a special optimization to handle long runs of characters that
cant start a match. Repeated sequences of 1, 2, 4, or 8 octet length which
cannot start are skipped at UV processing speeds. Giving very high throughput.

This combination allows us to handle most of the awkward cases at high
speed, and very often process the string at very high throughput.  A BMH
shift table can allow us to scan the string by looking at far less than
every character, potentially every Kth character, where K could be up to
255 in an extreme case.

Also includes some other minor cleanup, like avoid point-ring updates on
failed root transitions (point-ring updates how we know where a sequence
started). Another minor optimization is to reject Latin-1 targets when every
"word" requires a code point above 255.

Partial fix for https://github.com/Perl/perl5/issues/24934


  Commit: 4ce08dba21766a2e28569fa9c8ffc20311239f45
      
https://github.com/Perl/perl5/commit/4ce08dba21766a2e28569fa9c8ffc20311239f45
  Author: Yves Orton <[email protected]>
  Date:   2026-10-14 (Wed, 14 Oct 2026)

  Changed paths:
    M pod/perldelta.pod
    M regcomp.h
    M regcomp_trie.c
    M regexec.c
    M t/re/pat.t

  Log Message:
  -----------
  regex: use start-octet maps for folded Aho-Corasick tries

Build a conservative map of original target starts for folded tries. Use
inverse fold closures for their initial codepoints and include codepoints
whose multi-character folds begin with a possible initial folded character.
Extra candidates are safe because AC applies the actual folding rules
independently.

Leave both BMH (Boyer-Moore-Horspool) tables zero for folded tries. Their
folded octet offsets cannot describe shifts in the original target. Instead we
use the map and repeated-window scanner only at the root, with no buffered
fold or encoded transition octets required.

Also adds additional tests covering simple and multi-character folds, target
encodings, and /u, /d, /a, and /aa restrictions.

Resolves: https://github.com/Perl/perl5/issues/24935


  Commit: 7871c3ef476b9999f5a91ecf03cf96585e794fd6
      
https://github.com/Perl/perl5/commit/7871c3ef476b9999f5a91ecf03cf96585e794fd6
  Author: Yves Orton <[email protected]>
  Date:   2026-10-14 (Wed, 14 Oct 2026)

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

  Log Message:
  -----------
  regex: stop folded start-class scans at end of UTF-8 input

Require an input character before trying a nonempty folded literal start
class.  HOP3c clamps the candidate limit to the current position when too few
characters remain.  At the end of a UTF-8 target, UTF8_SAFE_SKIP returns zero,
so the scanner otherwise retries the same failed match indefinitely.

This can occur on a subsequent /g attempt after a successful match when trie
prefix extraction leaves a folded literal start class. The reproducer also
hangs in unchanged blead. It does not use the Aho-Corasick prefilter.

Final fix for: https://github.com/Perl/perl5/issues/24934


  Commit: 5c5f7ed59b16ab890e9cc0427c7e519457b8212a
      
https://github.com/Perl/perl5/commit/5c5f7ed59b16ab890e9cc0427c7e519457b8212a
  Author: Yves Orton <[email protected]>
  Date:   2026-10-14 (Wed, 14 Oct 2026)

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

  Log Message:
  -----------
  regex: use the repeat scanner for all BMH shifts

We can use the repeated sequence scanner whenever the start map rejects
an octet, regardless of its BMH (Boyer-Moore-Horspool) shift. Once we have
checked a full UV of octets that cannot start a match, an identical UV
cannot contain a start either. The BMH shift does not enter into that
proof. We do this at the AC root, with no pending folded or encoded input.

Restricting this to shifts zero and one meant that /walrus|cat/ never
used the repeat scanner on a long run of A's. A has a shift of three,
so we kept looking up the shift and moving forward three octets at a
time. We now establish the rejected window and scan in UV sized chunks.

This makes a big difference for that case. On Linux x86_64 with GCC 13.3,
-O2, no debugging and no threads, three scans of 200 million A octets
followed by cat take:

    previous patch    0.489 s
    this patch        0.048 s
    blead             1.807 s
    Perl 5.44         0.331 s

These are medians of three trials with matching build settings. The
previous patch numbers are from the preceding benchmark run.

There is a cost on nonrepeating input. For /abcdefgh|ijklmnop/, 32 scans
of 1 MiB of deterministic random uppercase ASCII increase from 0.0101 s
to 0.0302 s. We check octets while establishing the window that BMH could
otherwise skip. We should look into probing for repetition before doing
this for larger shifts.


  Commit: 6770b2eb5ee78ac47cd6e57696ea822b7932e12c
      
https://github.com/Perl/perl5/commit/6770b2eb5ee78ac47cd6e57696ea822b7932e12c
  Author: Yves Orton <[email protected]>
  Date:   2026-10-14 (Wed, 14 Oct 2026)

  Changed paths:
    M embed.fnc
    M embed.h
    M ext/re/t/regop.pl
    M ext/re/t/regop.t
    M pod/perldelta.pod
    M pod/perlreguts.pod
    M proto.h
    M regcomp.c
    M regcomp.h
    M regcomp.sym
    M regcomp_study.c
    M regcomp_trie.c
    M regexec.c
    M regnodes.h
    M t/re/anyof.t
    M t/re/re_tests

  Log Message:
  -----------
  regcomp: let invariant literals join folded nodes and tries

Add EXACT_INV and EXACT_INV_REQ8 to identify text which participates in no
Unicode case fold.  These nodes execute like EXACT and EXACT_REQ8, but the
optimizer can safely join their text to a folded literal.

We have long split non-folding text out of folded literals so the
fixed-substring optimizer can use it.  However, that split has also prevented
otherwise compatible alternatives from forming a complete trie.  It also
interacts with an optimization we do that turns a folded single character into
a character class, which can prevent more powerful TRIE style optimizations
from happening.  For example, /foo|bar|a_word|_qux/i should compile into one
TRIE-EXACTFU containing all four words.

Part of the problem is that we were splitting the nodes out as EXACT,
which is actually subtly not ideal.  The problem is that EXACT nodes
created normally may (and very often do) contain content that would fold
if it were merged into an EXACTFU for instance.  EXACT_INV however are
EXACTish nodes (from the point of view of fixed string extraction) but which
contain content that behaves the same folded or not, and which can be safely
merged together with (more or less) any other EXACT type.  By splitting
EXACT into "exact stuff you can NOT merge with any folding types" and
"exact stuff you CAN merge with folding types", we can undo the split
later on, merging the EXACT_INV nodes together with whatever they are next to.

Thus during study we leave invariant pieces separate until the substring and
length logic has seen them.  Then we join each piece to its compatible
predecessor, carring a merge-left flag forward after a successful join so that
the join cascades, meaning that

        EXACTFU     "foo"
        EXACT_INV   "_"
        EXACTFU     "bar"
        EXACT_INV   "_"
        EXACTFU     "baz"

becomes one folded EXACTFU containing "foo_bar_baz".

Only globally invariant characters get the new types.  In particular, a
ligature whose fold to ASCII is excluded by /aa stays EXACT_REQ8.  Marking it
invariant would let a neighboring /u literal absorb it and change its
matching rules.

Includes regression tests for the reported trie, cascading joins before and 
after a
nested alternation, single-letter continuations, sharp-S class alternatives,
scoped /aa folding, and mixed narrow and wide invariants.

Fixes #19953.


Compare: https://github.com/Perl/perl5/compare/eb856ce6e4cb...6770b2eb5ee7

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

Reply via email to