8000 NFA: deterministic fast paths for `determinize()`, membership and DFA products · Issue #801 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

NFA: deterministic fast paths for determinize(), membership and DFA products #801

Open

Description

@koniksedy

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

  1. DFA dispatch in determinize(). At entry, if aut.is_deterministic(), run a scalar DFS with a std::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, and emplace_back the single-target post. This reproduces the generic output exactly: same state numbering, unreachable states dropped, same finals. Checked on devel against determinize() on 3,000 random partial DFAs (1–40 states, 1–5 symbols, with unreachable states): identical delta, initial and final sets every time. When subset_map is requested, insert {q} → id for each reached q in the same pass. When macrostate_discover is 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).
  2. 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 in replace.cc. The measured 1.35 ms copy is this path.
  3. Scalar successor. Add std::optional<State> successor(State, Symbol) implemented with a lower_bound over the state post, so it does not go through StatePost::find. Use it in read_word_det(). Let is_in_lang() dispatch to it when the automaton is certified deterministic and either use_epsilon is false or the automaton has no ε-transitions.
  4. 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.
  5. 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 uncached DfaView that runs is_deterministic() once at operation entry. That is enough for determinize(), where the scan is cheap compared with the work saved.
  6. Turn the MATA_ASSERTs in union_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.

  1. Add benchmarks for DFA, almost-DFA and NFA inputs: determinize, is_in_lang on short and long words, DFA×DFA intersection and lang_difference. Record time and allocation counts.
  2. Implement the scalar DFS in determinize(). Add golden tests for numbering, unreachable states, an empty delta, subset_map, macrostate_discover stopping early, and ε used as a letter. Add a randomized test comparing it with the generic path on DFAs, as in the check above.
  3. Add as_dfa() for language-only callers and switch replace.cc to it.
  4. Add the lower_bound-based successor(), use it in read_word_det(), and add the is_in_lang() dispatch behind a DfaView check first.
  5. Implement DFA×DFA intersection and difference. Compare them with the generic operations by are_equivalent and, where numbering is contractual, by exact structure.
  6. 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 of add/remove/mutable_state_post/append/move leaves a stale certificate accepted, in Release as well.
  7. 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.
  8. 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

  1. added
    For:libraryThe issue is related to library (c++ implementation)
    Module:nfaThe issue is related to Nondeterministic Finite Automata
    type:optimizationThis issue is related to a possible optimization of an algorithm, improving the performance of Mata.
    on Sep 30, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    For:libraryThe issue is related to library (c++ implementation)Module:nfaThe issue is related to Nondeterministic Finite Automatatype:optimizationThis issue is related to a possible optimization of an algorithm, improving the performance of Mata.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      0