Branch: refs/heads/yves/new_trie
Home: https://github.com/Perl/perl5
Commit: 0a4a6593ececf0bb5fd72941603e5462aabeb37e
https://github.com/Perl/perl5/commit/0a4a6593ececf0bb5fd72941603e5462aabeb37e
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:
-----------
regex engine - widen trie word indexes to U32
Commit: 22d7635bcfa6597e13dabea491401f04d01289a8
https://github.com/Perl/perl5/commit/22d7635bcfa6597e13dabea491401f04d01289a8
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.
Commit: fac9c3a5b95b40f0a2011ccb3f5978c80963bce9
https://github.com/Perl/perl5/commit/fac9c3a5b95b40f0a2011ccb3f5978c80963bce9
Author: Yves Orton <[email protected]>
Date: 2026-08-26 (Wed, 26 Aug 2026)
Changed paths:
M regcomp.h
M regcomp_debug.c
M regcomp_study.c
M regcomp_trie.c
Log Message:
-----------
regex engine - tidy trie construction
Remove the obsolete stored trie debug bitmap. The debug dump can derive the
set of used octets from the final transition table when it needs to display the
table, so this information does not need to remain in the trie data.
Rename the remaining trie list field and related variables from forid to octet,
and use descriptive names for transition indexes. Clarify the list insertion,
source encoding, and UTF-8 buffer sizing logic while keeping the existing
locale exact-node handling unchanged.
make_test passes.
Commit: d5c2e8b6bd0a5dd6ac6948b94731b251efd10a4e
https://github.com/Perl/perl5/commit/d5c2e8b6bd0a5dd6ac6948b94731b251efd10a4e
Author: Yves Orton <[email protected]>
Date: 2026-08-26 (Wed, 26 Aug 2026)
Changed paths:
M regcomp_study.c
Log Message:
-----------
regex engine - apply jump correction during trie study
Apply the jump correction when study_chunk follows jump-trie continuations,
just as the executor does. Without this, prefix-extracted jump tries can make
study_chunk follow an invalid regnode pointer.
ASAN test_reonly passes.
Commit: a3c60376cc17027a8ed861fc694d1aa6932a03e2
https://github.com/Perl/perl5/commit/a3c60376cc17027a8ed861fc694d1aa6932a03e2
Author: Yves Orton <[email protected]>
Date: 2026-08-26 (Wed, 26 Aug 2026)
Changed paths:
M regcomp_debug.c
M regcomp_study.c
M regcomp_trie.c
Log Message:
-----------
regex engine - clarify trie data allocation and word counts
Use word_count to distinguish the number of trie words from the total octet
count, and document the lifetime of temporary list storage versus the
persistent compressed trie. Clarify that UTF-8 detection in diagnostic output
is not used to classify trie input.
Compare: https://github.com/Perl/perl5/compare/57fd31d22468...a3c60376cc17
To unsubscribe from these emails, change your notification settings at
https://github.com/Perl/perl5/settings/notifications
