8000 Simulation reduction: initial partition instead of marker labels, no dense relation copy · Issue #803 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

Simulation reduction: initial partition instead of marker labels, no dense relation copy #803

Open

Description

@koniksedy

Severity: High · Effort: Large · Expected effect: 1.4–1.7× less simulation time on NFT-like inputs from dropping the marker labels (quick check on devel); half the peak relation memory; 2–10× target overall, to be demonstrated, since on NFAs the simulation engine itself dominates

Scope: NFA compute_fw_direct_simulation() and algorithms::reduce_simulation() with the renaming copy in reduce(); the NFT mirror compute_fw_direct_simulation() and reduce_size_by_simulation(); and in simlib ExplicitLTS, compute_simulation(), build_result() and BinaryRelation (restrict_to_symmetric, get_quotient_projection).

Problem

Artificial marker labels. Forward simulation must not let a non-final state simulate a final one, and for NFTs must not relate states on different levels. Both implementations encode this with extra self-loops in the LTS. The NFA version searches for an unused symbol, adds f -u-> f for every final f, and throws "all symbols are used" if it finds none. The NFT version adds f -(max+1)-> f for every final and q -(max+2+level(q))-> q for every state, in 32-bit Symbol arithmetic that wraps onto real symbols when EPSILON or DONT_CARE is present (#727). For an NFT this adds n + |F| transitions and num_of_levels + 1 labels, and the engine starts from the single block {Q} and must split levels apart itself. Simlib already accepts an initial partition and a block relation: ExplicitLTS::compute_simulation(partition, relation, output_size). Mata never uses that overload.

The dense relation is expanded, copied and scanned. build_result() expands the engine's partition and block relation into an n × n BinaryRelation (a std::vector<bool> with row stride rowSize_). reduce_simulation() then copies it in full (auto sim_relation_symmetric = sim_relation;), runs restrict_to_symmetric() over n²/2 pairs, and scans n²/2 pairs again in get_quotient_projection(). The copy doubles peak relation memory: at 50,000 states each copy is 2.5·10⁹ bits, about 312 MB.

The quotient is built through hash maps and sorted inserts. Every state is inserted into a std::unordered_map<State, State> renaming, and each target is mapped with .at(). Target representatives are collected by sorted insert, dominated targets are found with k² calls to sim_relation.get(s, p), and reduce() finally copies the whole renaming into the caller's map instead of moving it (*state_renaming = reduced_state_map;, in both the NFA and the NFT reduce()).

Where the time goes. A local Release probe (GCC 15.2, -O3 -DNDEBUG, commit bb63f4e) with four symbols and fanout four scaled from 36 ms at 1,000 states to 102 ms at 2,000 and 444 ms at 4,000, with peak RSS 75 MB. The 2,000 → 4,000 step is 4.35× while transitions only doubled. A quick split on a Release build of devel (f874bae, GCC 15.2, -O3 -DNDEBUG; random NFAs with 1,000–4,000 states and four symbols, one dense and one sparse family) shows that compute_relation() alone takes about as long as the whole reduce(). Building the ExplicitLTS took under 2% of it (dense family), and the relation copy, symmetric restriction and projection together took 1–7%. For NFAs, the data-path changes below therefore mostly save memory. The marker change is where time moves: on a synthetic two-level NFT-like automaton (two symbols, level markers on every state), passing the partition {(level, final)} instead of markers gave the same relation (0 differing pairs) with 1.4–1.7× less time for building the LTS and running the engine, at every size and over three repetitions. For NFAs, where only the final marker disappears, the times were within noise.

Proposed change

  1. Initial partition instead of markers. Call compute_simulation(partition, relation, n) with the blocks {non-final, final} for NFAs and {(level, final)} for NFTs, dropping empty blocks. Set the block relation to R(B, B') = level(B) == level(B') && (final(B) → final(B')), where R(x, y) means "y simulates x", the orientation reduce_simulation() uses (sim_relation.get(s, p): p simulates s). This removes the unused-symbol search, its throw, and the NFT marker arithmetic that NFT reduce: simulation marker symbols wrap around when EPSILON or DONT_CARE is present, so reduce changes the language #727 fixes. algorithms::compute_relation() returns the same relation as before, so its callers (tests, Python) are unaffected.
  2. No full copy for the quotient. Add a read-only get_symmetric_quotient_projection() that tests R(p, q) && R(q, p) on the original relation. Next, have simlib return its partition and block relation to Mata, so reduction can take classes and dominance per block and skip the n × n expansion. Check first whether the final blocks are exactly the simulation-equivalence classes. If mutually related blocks can remain, merge them.
  3. Quotient with vectors. Keep class IDs in a std::vector<State> indexed by state. Fill the caller's StateRenaming only when it is requested, and move it in reduce(). Optimization of adding/removing transitions #179 (comment) proposes emplace_back for the output posts and Delta: checked builder for ordered construction and a batched import for unsorted transitions #782 the builder; this issue does not repeat that.
  4. Dominance pruning. Keep the scalar k² test for small target sets. For large ones, store BinaryRelation rows as 64-bit words with a stride rounded to 64 and intersect a candidate mask with the row of each target. Building a full-width mask costs O(n / 64), so switch only above a measured k. Keep the public BinaryRelation interface, which the Python binding wraps. Prune only among representatives: mutually similar targets were merged first, so two targets never remove each other.
  5. Adapter, last. Build the ExplicitLTS in one pass with per-label vectors reserved from the delta, or feed it spans. It took under 2% of the time in the split above, so do this only for memory.
  6. Budget. Before starting, estimate the relation (n² bits) and the engine's per-label, per-block, per-state structures with overflow-safe arithmetic. When the estimate exceeds a limit given in the ParameterMap, return the input unchanged with a "skipped" status. Return the reduction ratio in either case.
Explanation and worked example

What simulation reduction needs. Simulation computes a preorder: p simulates q if p can match every move of q forever. States that simulate each other can be merged, and a target that is simulated by another target of the same post can be dropped. The mathematics is sound. The overhead comes from how Mata feeds the engine and how it post-processes the result.

The marker example. Take an NFT with states 0, 2 on level 0 and 1, 3 on level 1, and final state 2. Today every state gets a level-marker self-loop and state 2 a final-marker self-loop, so 5 new transitions and 3 new labels are added. The engine starts from {0, 1, 2, 3} and discovers through those labels that 0 and 1 cannot be related. With a partition, it starts from {0}, {2}, {1, 3} with {0} ≤ {2} and nothing across levels, and skips those refinement rounds.

Pruning by bits. For the target set {2, 5, 9, 12}, the scalar test makes up to 12 relation lookups. With word rows, build the mask of the four bits and intersect it with row 2 to see which targets simulate 2, one machine word at a time. For two or three targets, the scalar test is cheaper.

Current data movement Proposed data movement
Finals and levels as marker labels and self-loops Initial partition and block relation
n × n expansion, full copy, symmetric restriction Read-only projection, or per-block result
unordered_map renaming and .at() per target Vector of class IDs
k² bit lookups per post Scalar for small k, word rows for large k

Why the budget stays. A dense relation over 100,000 states is quadratic whatever the adapter does. Estimate the size first and skip when it is not affordable. Be explicit about orientation: reversing "p simulates q" removes the wrong target, and symmetric test automata will not catch it.

Step-by-step execution plan

Read first: both compute_fw_direct_simulation() functions, reduce_simulation(), reduce_size_by_simulation(), ExplicitLTS, the SimulationEngine (init, run, build_result), BinaryRelation, the simulation tests in tests/nfa/nfa.cc and tests/nft/nft.cc, and #727. Write down the relation orientation before changing anything.

  1. Add timers and counters around LTS construction, the engine, build_result, the copy, the symmetric projection, the quotient build and pruning, plus relation bytes, class count and reduction ratio. Reproduce the 1k/2k/4k scaling and record the split for NFAs and NFTs.
  2. Switch both implementations to the initial partition. Differentially compare the full relation with the marker encoding on random NFAs and multi-level NFTs. The NFT reference must use NFT reduce: simulation marker symbols wrap around when EPSILON or DONT_CARE is present, so reduce changes the language #727's fixed markers (computed in size_t); otherwise it is itself wrong on inputs with EPSILON or DONT_CARE.
  3. Add get_symmetric_quotient_projection(), remove the copy, and compare quot_proj with the old one.
  4. Build the quotient with a class-ID vector, fill StateRenaming only on request, and move it in reduce(). Compare the reduced automata and renamings with the old code exactly.
  5. Prototype the per-block result from simlib. Check whether its blocks are the equivalence classes on random inputs, and use it only if it is exact or after merging mutually related blocks.
  6. Change BinaryRelation rows to 64-bit words behind the same interface, add the masked pruning above a measured k, and test it on asymmetric relations.
  7. Add the budget and the "skipped" result. Test the overflow-safe estimate at the boundary.
  8. Run the unit tests, the Python tests, randomized mutual-inclusion checks of reduce(aut) against aut, and the regex-construction and noodlification paths that call reduce() (Mintermization, alphabet lookups and regex conversion do quadratic or redundant work #754, optimize noodlification?  #207).

Dependencies and hand-off: #727 first, so the differential reference is correct. #207 asks for a quotient function over a given relation and state subset (quotient_by_simulation); the vector-based quotient of step 4 should be that function. The reusable graph index (#811) can later supply the CSR for the adapter (proposed change 5). Land the partition change separately from the quotient and pruning changes.

Definition of done: no marker labels or self-loops remain in either implementation, relation orientation is tested on asymmetric inputs, the quotient needs no copy of the relation, the budget fails safely, randomized results match the old code (with #727's markers), and the time split and peak RSS are recorded before and after.

Expected result and validation

The partition change removes the marker code and gave 1.4–1.7× less simulation time on the NFT-like check above. Removing the copy halves peak relation memory. Time gains on NFAs from the data-path changes alone are expected to be small, because the engine dominates there. The 2–10× target, and larger gains on highly nondeterministic target sets, must be shown by the step 1 split. Benchmark by states, labels, fanout, final density, number of levels and actual reduction ratio, including cases where reduction removes nothing. Validate by mutual inclusion and by comparing relation and quotient with the old code.

Related: #727 (NFT marker wrap-around; this change removes that code, and the oracle must use the fixed markers), #207 (per-final simulation reuse in noodlification needs a reusable quotient function), #754 (regex construction runs reduce() by default), #755 (Python compute_relation reads the relation bit by bit).

Metadata

Metadata

Assignees

No one assigned

    Labels

    For:libraryThe issue is related to library (c++ implementation)Module:nfaThe issue is related to Nondeterministic Finite AutomataModule:nftThe issue is related to Nondeterministic Finite Transducerstype: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