Branch: refs/heads/yves/octet_trie_followups
Home: https://github.com/Perl/perl5
Commit: eb856ce6e4cb0cfd5837c658ef737d13852d6828
https://github.com/Perl/perl5/commit/eb856ce6e4cb0cfd5837c658ef737d13852d6828
Author: Yves Orton <[email protected]>
Date: 2026-10-11 (Sun, 11 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.
To unsubscribe from these emails, change your notification settings at
https://github.com/Perl/perl5/settings/notifications