Branch: refs/heads/yves/new_trie
Home: https://github.com/Perl/perl5
Commit: 185027abd000c3d94f16be2cc121ac97db1f0fe7
https://github.com/Perl/perl5/commit/185027abd000c3d94f16be2cc121ac97db1f0fe7
Author: Yves Orton <[email protected]>
Date: 2026-08-26 (Wed, 26 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: 978df31061b7c90147c2cbbc346a2b0ee274e677
https://github.com/Perl/perl5/commit/978df31061b7c90147c2cbbc346a2b0ee274e677
Author: Yves Orton <[email protected]>
Date: 2026-08-26 (Wed, 26 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: 9d25c390a832bc1b0a987e35632fd377c47f9887
https://github.com/Perl/perl5/commit/9d25c390a832bc1b0a987e35632fd377c47f9887
Author: Yves Orton <[email protected]>
Date: 2026-08-26 (Wed, 26 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 perlvars.h
M pod/perldelta.pod
M pod/perldiag.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/lib/warnings/utf8
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
M utf8.h
Log Message:
-----------
regex engine - compile tries using utf8 octets as the internal encoding
The point of this patch is to simplify the trie compiler by switching
from using a trie based on codepoints to one based on the UTF-8 octets
representing those codepoints, regardless of the actual pattern
encoding. This single conceptual change unlocks a cascade of further
simplifications. In this model every trie now uses the same 256-entry
"alphabet" (NOTE: to repeate what is hopefully obvious, "alphabet" is
the maximum possible transitions can that occur from a given state in
the trie's transition table not a reference to the size of Unicode),
so we no longer need the old codepoint remapping tables, reverse maps,
wide-character maps, and indeed quite a bit of other stuff. Along the
way we also simplify the trie opcodes by getting rid of the inline
character-class trie forms which were complicating the code for little
benefit.
The change in alphabet size and no longer using the codepoint to id
mapping means that we need to do less traversals over the candidate
"words" we need to store, which in turn also makes the old table
representation less useful as we now have relatively wide states compared
to the average beofre. At the same time the smaller alphabet actually
makes the list representation more practical as the upper size of each
state list is reduced. It also proved that simpler code was more efficient
and so we now use only the list compiler and this patch removes the old
table compiler entirely.
Since we no longer need to build the codepoint mapping tables, we can
build sparse octet transition lists in one pass and use a more efficient
algorithm to pack those lists into the compact transition table used by
the executor. The list and table compressors are also tuned to avoid
unnecessary work, including by retaining per-state octet bounds for the
delayed Aho-Corasick construction.
The Aho-Corasick start-class construction has also been modified along
the same lines as the trie code, and now is more efficient due to
information passed through from the initial trie building phase.
This patch also includes improvements to the prefix extraction
algorithm, including safe extraction of complete UTF-8 prefixes and
prefixes from jump tries.
This patch also tries to keep source encoding, folding, and trie
representation separate in the code. We encode normalized codepoints as
UTF-8, and match non-folded UTF-8 input directly as existing UTF-8
octets. To faciliate this we also add a new table PL_native_octet_utf8,
which is populated at startup with the UTF-8 representation of each
native octet, so that the common native-to-UTF-8 conversions do not have
to be performed repeatedly while building or matching a trie. Trie
indexes and related counters are widened to U32 where required.
The tests cover native and UTF-8 tries, folding, overlapping and
duplicate words, jump continuations, prefix extraction, and Aho-Corasick
start classes. A trie benchmark suite was added with dumbbench support,
together with single-process profiling modes so that the complete qr//
compiler path can be exercised repeatedly and matching can be profiled
after compiling an expression once.
The locale warning tests are updated because the improved prefix
handling now collapses the affected alternation into a single EXACTFLU8
node instead of retaining it as a trie, thus producing fewer warnings.
On this system, the latest benchmark compared this branch against
blead using the same build configuration, default trie settings,
and Dumbbench. The values below are seconds per child; ratios are
branch / blead.
compile match
case branch blead ratio branch blead ratio
ascii-common-prefix .1014 .1033 .98x .0242 .0297 .82x
ascii-wide-alphabet .1181 .1204 .98x .0295 .0362 .81x
latin1-native .1051 .1130 .93x .0236 .0270 .87x
utf8-wide-codepoints .1105 .1186 .93x .0263 .0340 .77x
mixed-ascii-and-wide .1096 .1174 .93x .0301 .0369 .82x
unicode-folding .1192 .1338 .89x .0333 .0384 .87x
latin1-folding .1168 .1297 .90x .0300 .0343 .87x
overlap-prefixes .1367 .1575 .87x .0596 .0754 .79x
overlap-middle .1517 .1926 .79x .0305 .0469 .65x
jump-continuations .1249 .1422 .88x .0323 .0450 .72x
jump-accepting-prefix .1124 .1326 .85x .0308 .0411 .75x
duplicate-overlap .1004 .1259 .80x .0363 .0455 .80x
For the large-alternation benchmark, the branch was also compared with its
trie disabled. On the branch-only corpus, using 8 alternation counts from
10 through 1280 and 4 padding lengths from 10 through 80, the non-trie model
was dominated by the alternation-count/padding interaction, while the trie
model was dominated by its constant term. At 1280 alternatives and 80
padding characters, the non-trie case took 1.149000 seconds per match and
the trie case took 0.012024 seconds, a 95.56x speedup.
Compare: https://github.com/Perl/perl5/compare/f1b6cecc929d...9d25c390a832
To unsubscribe from these emails, change your notification settings at
https://github.com/Perl/perl5/settings/notifications
