8000 `GraphIndex`: one epoch-bound forward/reverse/symbol CSR shared across analyses · Issue #811 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

GraphIndex: one epoch-bound forward/reverse/symbol CSR shared across analyses #811

Open

Description

@koniksedy

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() and distances_to_final() build a complete reversed automaton with one sorted Delta::add per transition, only to run a reachability or BFS pass on it.
  • revert() builds the same kind of reversed delta.
  • minimize_hopcroft groups transitions by symbol through an unordered_map in RefinablePartition(const Delta&), and builds incoming transition IDs as a std::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

  1. Add an immutable internal GraphIndex built from a Delta with 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;
    • UsedSymbols and NonemptySources.
  2. 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.
  3. Make the distances_to_final builds 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 the Incoming builder of this type, so there is one implementation.
  4. 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.
  5. 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.
  6. Add a pipeline-owned AnalysisContext that builds features lazily, adds a missing feature without rebuilding the base arrays, and exposes build time, reuse count and retained bytes.
  7. 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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. Add the pipeline-owned AnalysisContext that upgrades features lazily and reuses compatible arrays. Record retained bytes and reuse counts.
  7. Establish dispatch thresholds from setup cost, graph size, requested features and expected reuse. Direct scans remain for tiny or one-shot work.
  8. 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)

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