moonbitlang / core / 6769

89%

push

github

perf(regex): flat per-symbol membership table for Chr nodes (#4269)

* perf(regex): flat per-symbol membership table for Chr nodes

`Chr` nodes held a `RecharSet` (an interval tree) and `delta_expr` walked
it with `contains` for every Chr node of every thread on every transition,
about 5% of automaton construction in a native profile. Character sets
reach the automaton after symbolization, so their elements are dense
symbol ids; `Chr` now holds a `SymbolSet`, a `FixedArray[Bool]` indexed by
symbol built once in `e_cset`, and membership is an unsigned range check
plus one load. `e_copy` shares the immutable table between copies, and
`-1` (the end-of-input marker used for the final transition) is never a
member, as before.

Construction of the 38-alternative benchmark pattern plus 300 inputs:
native 15.1 -> 14.5 ms; scan loops unchanged. No interface change.
Part of #4263.

Codex CLI review: "The sole production e_cset caller passes symbolized
sets ... Ordered intervals make last_interval.hi + 1 sufficient; inclusive
filling preserves membership and gaps. e_copy assigns fresh IDs and safely
shares tables: no code mutates them after construction."

Signed-off-by: Codex CLI <codex@openai.com>
Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>

* use bit vector instead of FixedArray[Bool]

---------

Signed-off-by: Codex CLI <codex@openai.com>
Co-authored-by: Claude Fable 5.1 <noreply@anthropic.com>
Co-authored-by: 文宇祥 <hackwaly@qq.com>

14 of 15 new or added lines in 2 files covered. (93.33%)

16486 of 18381 relevant lines covered (89.69%)

333532.69 hits per line