Repository navigation
Description
Severity: Critical · Effort: Medium/Large · Expected effect: 4.75× measured for determinize() on a DFA (against a deep copy); 3–6× target there, 1.3–3× target on deterministic product, difference and membership
Scope: determinize(), Nfa::is_deterministic(), Nfa::read_word_det() and Nfa::is_in_lang(), algorithms::product(), lang_difference(), and union_det_complete().
Problem
Mata sends deterministic automata through the NFA machinery. On a DFA, determinize() wraps every state in a one-element StateSet, resets and refills a SynchronizedExistentialSymbolPostIterator per state, builds a fresh StateSet per symbol with unify_targets(), hashes it in subset_map->find(), hashes and copies it again on insertion, and adds each result transition with a sorted insert. A local Release probe (GCC 15.2, -O3 -DNDEBUG, commit bb63f4e) on a 5,000-state, 40,000-transition complete DFA measured 6.43 ms for determinize() against 1.35 ms for a deep copy, a 4.75× gap. Copying made 45,005 allocations; determinizing made 180,045. The determinization loop is unchanged on devel.
Callers already work around this by hand: replace.cc guards determinize() with if (!regex.is_deterministic()) at L290 and L327. is_deterministic() is one O(n + number of symbol posts) scan with no allocation. That is cheap next to determinize(), but not next to reading a short word, so checking at every entry is not a general answer. The library has no way to remember that an automaton was already checked.
The scalar word reader exists: read_word_det() returns std::optional<State>, documents its result as undefined on an NFA, and is exposed in Python. is_in_lang() never uses it and builds a StateSet per letter through post() even when the automaton is a DFA. read_word_det() looks up successors through StatePost::find(Symbol), which writes a function-local static (#731).
Products do not specialize either. algorithms::product() constructs a SynchronizedUniversalIterator(2) per product state and a SymbolPost per symbol, even when both sides have one target per symbol. #742 measured a 3.9M-state deterministic product and found it unchanged by its fixes, so the deterministic case needs its own path. lang_difference() hashes StateSets for both operands in unordered_set<StateSet>, although on two DFAs every set has at most one element. union_det_complete() checks its preconditions only with MATA_ASSERT and then runs the generic product.
Proposed change
- DFA dispatch in
determinize(). At entry, ifaut.is_deterministic(), run a scalar DFS with astd::vector<State>renaming and a stack. Pop a state, walk its symbol posts in order, give a new ID to each unseen target, push it, andemplace_backthe single-target post. This reproduces the generic output exactly: same state numbering, unreachable states dropped, same finals. Checked on devel againstdeterminize()on 3,000 random partial DFAs (1–40 states, 1–5 symbols, with unreachable states): identical delta, initial and final sets every time. Whensubset_mapis requested, insert{q} → idfor each reachedqin the same pass. Whenmacrostate_discoveris given, call it with the singleton set right after emitting the transition that discovered the state, as the generic path does, and stop at the same point (it is not called at all when the delta is empty). - Language-only callers skip renumbering. Add an internal
as_dfa(const Nfa&)/as_dfa(Nfa&&)that returns the input unchanged (copied or moved) when it is a DFA and determinizes otherwise. Use it where only the language matters: the complement pipeline (complement(): direct path for DFAs, one fused subset pass for NFAs #802), minimization (minimize(): make an input-aware"auto"strategy the default instead of Brzozowski #800), and the two guards inreplace.cc. The measured 1.35 ms copy is this path. - Scalar successor. Add
std::optional<State> successor(State, Symbol)implemented with alower_boundover the state post, so it does not go throughStatePost::find. Use it inread_word_det(). Letis_in_lang()dispatch to it when the automaton is certified deterministic and eitheruse_epsilonis false or the automaton has no ε-transitions. - DFA×DFA product and difference. Add kernels that walk the two sorted state posts with two pointers and emit one target per symbol. Keep product-state IDs in the existing
TwoDimensionalMap. For difference, the right-hand side is a scalar state or the implicit sink of its completion, so no set is hashed. Add a DFA×NFA variant (scalar state plus interned macrostate from macrostate interning (Subset construction: intern macrostates once, with stable IDs and cached hashes #783)) only after the DFA×DFA kernels are correct. Dispatch once at entry and keep the generic code as the fallback. - Determinism certificate. Define
DeterminismCertificate { epoch, has_epsilon }bound to the delta mutation epoch from Delta metadata (Delta: O(1)empty()and transition count, epoch-cached structural properties #805). Install it on the outputs of subset construction, Hopcroft, deterministic complement and DFA products. Invalidate it on any mutable access to the delta. Until Delta metadata (Delta: O(1)empty()and transition count, epoch-cached structural properties #805) lands, provide an uncachedDfaViewthat runsis_deterministic()once at operation entry. That is enough fordeterminize(), where the scan is cheap compared with the work saved. - Turn the
MATA_ASSERTs inunion_det_complete()into checks that throw, or route the function through the DFA×DFA kernel after one validation.
Explanation and worked example
What Mata forgets. After determinization, Mata knows that the output has one initial state and at most one target per (state, symbol). Later operations either scan the graph again to rediscover this or ignore it and wrap every state in a singleton set. A certificate records "this exact delta version was checked and is deterministic", so later operations can use scalar code.
Example. Determinizing a DFA whose current state is 17 creates the macrostate {17}, hashes that one-element vector, looks it up in the subset map, and creates {23} for its a successor. The scalar path reads successor(17, a) = 23, checks renaming[23], and appends one transition. If the caller asked for the subset map, {23} → renaming[23] is inserted once.
Why the scalar DFS gives the same numbering. The generic loop uses its worklist as a stack. It assigns an ID when a target is first seen, in increasing symbol order, and processes the most recently pushed state next. A scalar DFS with the same push and pop order visits and numbers states identically, so tests that compare Deltas keep passing.
| Input and path | Representation |
|---|---|
| DFA×DFA product | Pair of scalar state IDs |
| DFA×NFA product | Scalar ID plus interned macrostate ID |
| NFA×NFA product | Two generic sets |
| Word read on a DFA | One optional scalar successor per letter |
Why not call is_deterministic() at every entry. For determinize() that is fine, since the scan is small next to the work it saves. For membership of a short word, the scan would dominate. A certificate bound to a mutation epoch removes the repeated scan. Safe builders install it and mutation clears it.
Why dispatch outside the loop. An if (deterministic) inside the state and symbol loops costs a branch per step and mixes two sets of invariants. Pick the kernel at entry. An "almost DFA", with one nondeterministic post near the end, must fail validation and take the generic path.
Step-by-step execution plan
Read first: determinize(), is_deterministic(), read_word_det(), is_in_lang(), product.cc, lang_difference(), the determinize tests in tests/nfa/nfa.cc, and every place that mutates delta. List which operations preserve determinism and which invalidate it.
- Add benchmarks for DFA, almost-DFA and NFA inputs:
determinize,is_in_langon short and long words, DFA×DFA intersection andlang_difference. Record time and allocation counts. - Implement the scalar DFS in
determinize(). Add golden tests for numbering, unreachable states, an empty delta,subset_map,macrostate_discoverstopping early, and ε used as a letter. Add a randomized test comparing it with the generic path on DFAs, as in the check above. - Add
as_dfa()for language-only callers and switchreplace.ccto it. - Add the
lower_bound-basedsuccessor(), use it inread_word_det(), and add theis_in_lang()dispatch behind aDfaViewcheck first. - Implement DFA×DFA intersection and difference. Compare them with the generic operations by
are_equivalentand, where numbering is contractual, by exact structure. - Define the certificate and its invalidation once the mutation epoch from Delta metadata (
Delta: O(1)empty()and transition count, epoch-cached structural properties #805) exists. Property-test that no sequence ofadd/remove/mutable_state_post/append/move leaves a stale certificate accepted, in Release as well. - Install certificates on deterministic outputs and use them in
is_in_lang()and the product dispatch. Benchmark certified hit, validation miss, almost-DFA fallback, and repeated calls in a pipeline. - Add the DFA×NFA kernel only if the benchmarks show a case for it.
Dependencies and hand-off: Delta metadata (#805) for caching; the uncached DfaView and the determinize() dispatch can land before it. Minimization (#800) and complement (#802) are the main consumers. Macrostate interning (#783) is needed only for DFA×NFA.
Definition of done: no subset machinery runs on a DFA in determinize(), its output is identical to the generic path, stale certificates are impossible, almost-DFAs fall back correctly, and the measured determinize(DFA) time approaches copy cost.
Expected result and validation
Target 3–6× for determinize() on DFAs and 1.3–3× for deterministic product, difference and membership. The measured deep-copy path gave 4.75×. The exact-numbering DFS does somewhat more work than a copy, while moving an rvalue through as_dfa() avoids the copy entirely. Validate on DFA, almost-DFA and NFA inputs separately. Cover caller-supplied subset maps, callback order, empty and multiple initial states, partial transition functions, ε used as a letter, and certificate invalidation after every mutating API.
Related: #738 and #752 (faster generic determinization; complementary), #742 (generic product; its measurements show no gain on deterministic products), #731 (static buffer in StatePost::find).
Activity
nfa: +fix Close epsilon on both sides and share one closure routine
nfa: +feat Complement DFAs directly and drop foreign symbols
nfa: +refactor Dispatch deterministic automata to scalar fast paths
nfa: +fix Close epsilon on both sides and share one closure routine
nfa: +feat Complement DFAs directly and drop foreign symbols
nfa: +feat Complement DFAs directly and drop foreign symbols
nfa: +feat Complement DFAs directly and drop foreign symbols
nfa: +feat Complement DFAs directly and drop foreign symbols
nfa: +feat Complement DFAs directly and drop foreign symbols
nfa: +fix Close epsilon on both sides and share one closure routine
nfa: +refactor Dispatch deterministic automata to scalar fast paths
nfa: +fix Close epsilon on both sides and share one closure routine
nfa: +refactor Dispatch deterministic automata to scalar fast paths (#…
nfa: +fix Close epsilon on both sides and share one closure routine
nfa: +fix Close epsilon on both sides and share one closure routine (#…