Branch: refs/heads/yves/octet_trie_followups
  Home:   https://github.com/Perl/perl5
  Commit: b1036c694c5435fa28597680badc4e6883e5f2a5
      
https://github.com/Perl/perl5/commit/b1036c694c5435fa28597680badc4e6883e5f2a5
  Author: Yves Orton <[email protected]>
  Date:   2026-10-15 (Thu, 15 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: a9c50358437c6289521d235113e8dd9c56b4a815
      
https://github.com/Perl/perl5/commit/a9c50358437c6289521d235113e8dd9c56b4a815
  Author: Yves Orton <[email protected]>
  Date:   2026-10-15 (Thu, 15 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: 1d0d90344861756a3da5af9961a95e37d1b875e3
      
https://github.com/Perl/perl5/commit/1d0d90344861756a3da5af9961a95e37d1b875e3
  Author: Yves Orton <[email protected]>
  Date:   2026-10-15 (Thu, 15 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: e910fa18bdd07a8b2d0fe9247c03938a3882b3c9
      
https://github.com/Perl/perl5/commit/e910fa18bdd07a8b2d0fe9247c03938a3882b3c9
  Author: Yves Orton <[email protected]>
  Date:   2026-10-15 (Thu, 15 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.


Compare: https://github.com/Perl/perl5/compare/5c5f7ed59b16...e910fa18bdd0

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

Reply via email to