Repository navigation
Description
Severity: High · Effort: Large · Expected effect: 1.2–3× target on multi-analysis pipelines; one-shot operations unchanged
Scope: the views that analyses build from the source-major delta today: Automaton::reverted() behind get_terminating_states() and distances_to_final(); simple_revert; the splitter partition RefinablePartition(const Delta&) and incoming transition lists (L898-L905) in minimize_hopcroft; the Simlib::ExplicitLTS in compute_fw_direct_simulation; Delta::get_transitions_to as used by residual reduction; and the used-symbol scan in Nfa::resolve_alphabet.
Problem
Mata's delta is source-major: outgoing transitions of a state are one lookup away, predecessors are not. Each analysis that needs another view builds its own, from scratch, on every call:
get_terminating_states()anddistances_to_final()build a complete reversed automaton with one sortedDelta::addper transition, only to run a reachability or BFS pass on it.revert()builds the same kind of reversed delta.minimize_hopcroftgroups transitions by symbol through anunordered_mapinRefinablePartition(const Delta&), and builds incoming transition IDs as astd::vector<std::vector<size_t>>.- Simulation copies every transition into a
Simlib::ExplicitLTS. - Residual reduction scans the whole delta once per covered state through
get_transitions_to. - An NFA without an alphabet recomputes and sorts its used symbols on every
resolve_alphabet()call.
Filed issues replace several of these with local one-shot helpers: #740 adds a label-free predecessor CSR for distances_to_final and get_terminating_states, #751 reuses it for revert, nft::remove_epsilon, residual reduction and ShortestWordsMap, and trim & reverse index (#786) proposes reverse reachability for trim. Each helper still rebuilds its index per call. A caller that runs several analyses on an unchanged automaton, for example repeated inclusion or equivalence checks against the same automaton, or Hopcroft or simulation reduction after a trim that removed nothing, pays O(|Q| + |Δ|) setup and allocation again in every stage. Without one shared type, each optimized operation also risks building yet another incompatible CSR.
Proposed change
- Add an immutable internal
GraphIndexbuilt from aDeltawith feature flags, so a one-shot caller pays only for what it reads:Outgoing: offsets plus flat(symbol, target)arrays;Incoming: predecessor offsets plus sources, optionally with symbols;BySymbol: transitions grouped by symbol, with per-symbol offsets;TransitionIds: a stable ID per transition in outgoing order;UsedSymbolsandNonemptySources.
- Build each array in count, prefix-sum and fill passes with exact allocation and checked sums. Use the narrow state and symbol widths once state width (Core types: configurable 32-bit
State, overflow checks, compact initial/final sets #789) makes them configurable. - Make the
distances_to_finalbuilds a reversed NFA and dominates quickly decided antichain inclusion checks #740/Bulk Delta primitives: offset append for union/concatenation and a predecessor index for revert #751 predecessor-CSR helper theIncomingbuilder of this type, so there is one implementation. - Let internal routines accept an optional
const GraphIndex*: distances and terminating states, reverse reachability for trim,rev 8000 ert, Hopcroft, the simulation adapter and residual predecessor queries. A null pointer keeps today's direct path. - Bind validity to the delta's identity and the mutation epoch from delta metadata/epoch (
Delta: O(1)empty()and transition count, epoch-cached structural properties #805). Any mutation invalidates the index. Remap an index instead of rebuilding it only for operations with a proven stable state mapping, such as trim's compaction, and test that remap. Never update a CSR incrementally during arbitrary ordered insertion; the mutable delta stays the edit representation. - Add a pipeline-owned
AnalysisContextthat builds features lazily, adds a missing feature without rebuilding the base arrays, and exposes build time, reuse count and retained bytes. - Set dispatch thresholds from measured setup cost, graph size, requested features and expected reuse. Tiny and one-shot work keeps the direct scan.
Explanation and worked example
One graph, many temporary copies. Terminating states and distance-to-final build a reversed automaton; Hopcroft builds incoming transition lists and a symbol grouping; simulation builds its own transition table; residual reduction scans for predecessors; completion collects used symbols. In a pipeline over an unchanged delta these are copies of nearly the same facts.
Feature-based index example. For transitions 0 -a→ 2 and 1 -b→ 2, the outgoing CSR stores one slice per source. The incoming CSR stores (0,a), (1,b) in the slice of target 2. Reverse reachability for trim requests incoming sources only. Hopcroft requests incoming transition IDs and the symbol grouping. Simulation requests outgoing and incoming grouped by symbol. Feature flags keep a one-shot trim from allocating labels and IDs it never reads.
| Strategy | Ten-state one-shot | Million-edge multi-analysis pipeline |
|---|---|---|
| Direct delta scan with a local queue | Likely best | Repeats setup and scattered traversal |
| Build every possible index | Overkill | Wastes optional arrays |
| Lazy feature index with reuse | Dispatches to the direct scan | Built once; missing views added on demand |
Validity rule. CSR offsets depend on the exact transition count and order. After any delta mutation an old index must never be used, so it is bound to the delta's identity and mutation epoch. Copying or moving an automaton needs explicit semantics too: an equal epoch on different storage proves nothing.
Why not update the CSR incrementally. An arbitrary insertion shifts the offsets of every later slice and can move most of the arrays. Keep the mutable source-major delta for edits and build immutable snapshots after them. Migrate consumers one at a time, compare each indexed traversal with its direct or reference result, and measure index build time separately, so that a claimed speedup does not hide a more expensive setup paid elsewhere.
Step-by-step execution plan
Read first: every local reverse, CSR or LTS construction (reverted(), the revert variants, RefinablePartition and the incoming lists in minimize_hopcroft, compute_fw_direct_simulation, get_transitions_to), the helpers proposed in #740 and #751, the epoch design in delta metadata/epoch (#805), and the order guarantees of transition iteration. Inventory the fields each consumer needs, to avoid an oversized universal index.
- Define the feature flags and layouts: outgoing CSR, incoming
{source, symbol}CSR, nonempty sources, used symbols, symbol grouping and optional transition IDs. State which arrays each flag combination omits. - Implement
GraphIndex::build(delta, features, epoch)in count/prefix/fill passes with exact allocation and checked sums. Keep a deterministic order, or sort slices where a consumer requires it. - Add a direct-scan oracle and fuzz every indexed view on random deltas with empty posts, sparse state and symbol IDs, ε-transitions, duplicate insertion attempts and self-loops. Validate offsets, cursors and transition multiplicity.
- Bind validity to the epoch and the delta's identity. Access after a mutation must rebuild or fail, and copies or moves must not validate an index for different storage.
- Migrate one consumer at a time: distances and terminating states, trim's reverse reachability,
revert, Hopcroft, the simulation adapter, residual predecessor queries. Each takes an optional index and keeps its direct one-shot path. - Add the pipeline-owned
AnalysisContextthat upgrades features lazily and reuses compatible arrays. Record retained bytes and reuse counts. - Establish dispatch thresholds from setup cost, graph size, requested features and expected reuse. Direct scans remain for tiny or one-shot work.
- Benchmark isolated operations and pipelines such as trim → minimize, distances → inclusion and simulation → quotient. Measure build, traversal, reuse, memory and allocations separately.
Dependencies and hand-off: Requires the mutation epoch from delta metadata/epoch (#805); uses the widths from state width (#789) and the used-symbol collection from #324. It consolidates the one-shot helpers of #740 and #751, the reusable workspace proposed in trim & reverse index (#786) and the symbol-grouped forward/backward index proposed in simulation reduction (#803), so land it before those multiply.
Definition of done: consumers share one validated representation where profitable, feature flags avoid unused arrays, a stale index cannot be used, direct and indexed fuzz results match, setup time is visible separately, and multi-analysis pipelines show amortized time and RSS gains.
Expected result and validation
Target 1.2–3× on multi-analysis pipelines, with less duplicated allocation and RSS. One-shot operations may be unchanged or slightly slower, which is why construction is adaptive.
Benchmark individual operations and sequences such as trim → minimize, distances → inclusion and simulation → quotient. Compare every indexed traversal with direct delta traversal under random mutations, sparse states and symbols, ε-transitions and state renaming.
Related: #740 (label-free predecessor CSR for distances_to_final/get_terminating_states), #751 (the same helper for revert, nft::remove_epsilon, residual reduction and ShortestWordsMap), #224 (templated Tarjan walks the delta directly and needs no index)
Activity
Delta: O(1)empty()and transition count, epoch-cached structural properties #805nfa: +refactor Compute useful states with two reachability passes
nfa: +refactor Compute useful states with two reachability passes
nfa: +refactor Compute useful states with two reachability passes
nfa: +refactor Compute useful states with two reachability passes
nfa: +refactor Compute useful states with two reachability passes (#886)