[Perl/perl5] b56123: regex engine - get rid of 16 bit values, use 32 bi...

  Branch: refs/heads/yves/new_trie
  Home:   https://github.com/Perl/perl5
  Commit: b56123c433d6dc8fb1f3a4279a1abe23b52f9ad6
      https://github.com/Perl/perl5/commit/b56123c433d6dc8fb1f3a4279a1abe23b52f9ad6
  Author: Yves Orton <[email protected]>
  Date:   2026-08-14 (Fri, 14 Aug 2026)

  Changed paths:
    M regcomp.h
    M regcomp_trie.c
    M regexec.c

  Log Message:
  -----------
  regex engine - get rid of 16 bit values, use 32 bit values for charid

For now anyway. Maybe in the future we should just switch to double compiling, or maybe compiling on demand, and generate both a utf8
octet trie and a latin-1 version as well.


  Commit: 846d5cf55ef790bb3ff536297011bf64532cf566
      https://github.com/Perl/perl5/commit/846d5cf55ef790bb3ff536297011bf64532cf566
  Author: Yves Orton <[email protected]>
  Date:   2026-08-14 (Fri, 14 Aug 2026)

  Changed paths:
    M regcomp.h
    M regcomp_trie.c
    M regexec.c
    M regexp.h

  Log Message:
  -----------
  Widen trie word indexes to U32


  Commit: f1b6cecc929d7df187749ab88956dca8e13cc0c2
      https://github.com/Perl/perl5/commit/f1b6cecc929d7df187749ab88956dca8e13cc0c2
  Author: Yves Orton <[email protected]>
  Date:   2026-08-15 (Sat, 15 Aug 2026)

  Changed paths:
    M MANIFEST
    M charclass_invlists.inc
    M embed.fnc
    M embed.h
    M ext/re/t/regop.t
    M lib/unicore/uni_keywords.pl
    M perl.c
    M perl.h
    M pod/perldelta.pod
    M pod/perlreguts.pod
    M proto.h
    M regcomp.c
    M regcomp.h
    M regcomp.sym
    M regcomp_debug.c
    M regcomp_study.c
    M regcomp_trie.c
    M regen/mk_invlists.pl
    M regexec.c
    M regexp_constants.h
    M regnodes.h
    M t/lib/warnings/regexec
    M t/re/opt.t
    A t/re/trie_bench.pl
    A t/re/trie_bench.t
    A t/re/trie_byte.t
    M uni_keywords.h

  Log Message:
  -----------
  regex engine - compile tries using octets

The trie compiler now builds trie transitions from the octets of the
UTF-8 representation of the pattern. This gives every trie the same
256-octet alphabet and removes the need to represent Unicode codepoints
as entries in a potentially very large transition alphabet.

There is a special case for patterns whose codepoints are all ASCII: the
ASCII and UTF-8 representations use the same octets, so they naturally
share the same trie representation. Other low-page and native-string
cases are handled as encoding details around this common UTF-8-byte
representation, rather than as different trie formats.

Encoding-specific matching rules, including native versus UTF-8 behavior
and case folding, are handled independently of the fact that trie
transitions are stored as UTF-8 octets. This keeps the representation
uniform while preserving the existing matching semantics.

Trie construction now uses the list representation throughout and
converts it directly to the compressed transition form used by the
executor. The old flat table construction path, character maps, reverse
character map, wide character map, and inline-charclass trie op variants
are removed. This eliminates a substantial amount of special handling
for Unicode transitions and makes the implementation easier to maintain
and prove correct.

Trie indexes and related counters are widened to U32 where required,
while the debug bitmap is kept as U8 data. Prefix extraction tracks
encoded-byte and source-codepoint lengths so that UTF-8 prefixes are not
split in the middle of a codepoint. Debug trie dumps now describe the
octet alphabet and omit columns that are not present in the pattern.

The regular expression internals version now identifies the octet-trie
implementation, and the perldelta and regex internals documentation
describe the new representation. Tests cover native and UTF-8 byte
tries, updated diagnostics, and benchmark the scaling of large
alternations with different amounts of padding.

On this system, the normal seven-case corpus was measured with dumbbench
using an untouched default configuration in both blead and this branch.
The measured compile and match phase means were 0.109703 and 0.027088
seconds for blead, versus 0.103755 and 0.026573 seconds for the branch.
This is a change of -5.4% and -1.9%, respectively.

The branch was also measured with its trie disabled. The branch trie
versus off change was +25.2% for compilation and -17.9% for matching.
These numbers describe this small normal corpus; the large-alternation
workload is where the asymptotic difference is most clear.

On the branch-only large-alternation corpus, with 8 alternation counts
from 10 through 1280 and 4 padding lengths from 10 through 80, the off
model was dominated by the interaction term (n_alt * n_pad), with R^2 =
1.000 and an interaction t-statistic of 131.14. The trie model was
dominated by const, with R^2 = 0.502 and an interaction
t-statistic of -0.12. At 1280 alternations and 80 padding
characters, off took 1.149000 seconds per child and trie took
0.012024 seconds, a 95.56x speedup.

The benchmark uses dumbbench and optionally Statistics::Regression. When
these are not available, it reports the corresponding cpanm command
needed to install them.


Compare: https://github.com/Perl/perl5/compare/b56123c433d6%5E...f1b6cecc929d

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