moonbitlang / core / 6750

89%

push

github

perf(regex): keep a state's threads in an append-only array (#4271)

`ThreadSet` was a treap merged on every concatenation, so each derivative
step allocated a node per thread, rebuilt trees for `remove_duplicates`,
`remove_matches`, `split_at_first_match` and `assign_slot`, and iterated
through closures with a parent stack; about 40% of automaton construction
was allocation and reference-count teardown.

Threads now live in an `Array[Thread]` in priority order. Producers append
to an accumulator (ocaml-re's `rem`, but appending), so concatenation is
free and nested arrays exist only where a `Seq` thread needs one. Every
array reachable from a set under construction is owned by the current
`delta` call, so deduplication, match removal, splitting and slot
assignment compact in place; once a set is stored in a `State` it is never
mutated. The `remove_duplicates` scratch set lives on `Context` and is
cleared per step instead of allocated. Push order, the `ts_seq` collapse
rules, first-`End` truncation and the shared `seen` set are unchanged.

Native: construction of the 38-alternative pattern + 300 inputs
15.1 -> 9.8 ms (js 12.5 -> 8.3 ms); scan loops unchanged. No interface
change. Part of #4263.

Codex CLI review: "Every emitted Seq owns a fresh array. Splitting produces
separate arrays; no mutation reaches stored states ... All delta_* cases
preserve treap traversal order, including all three sequence preferences
and greedy/lazy repetition's different mark selection ... Compaction never
overwrites unread entries."

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

87 of 92 new or added lines in 3 files covered. (94.57%)

16470 of 18371 relevant lines covered (89.65%)

333747.18 hits per line