8000 NFT composition: collapse generated epsilon rounds and duplicate paths during construction · Issue #815 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

NFT composition: collapse generated epsilon rounds and duplicate paths during construction #815

Open

Description

@koniksedy

Severity: High · Effort: Large · Expected effect: much smaller output on generated-ε-heavy compositions without seconds-long generic cleanup; 1.2–10× target on the operations that follow

Scope: the ε chains built by create_epsilon_transition_with_common_path() and create_epsilon_transition_with_target() in compose_fast_no_jump(), used by process_fast_epsilon_transitions() and model_waiting(); the final trim(); the generic nft::remove_epsilon().

Problem

The fast composer writes padding as explicit ε chains: create_epsilon_transition_with_common_path() adds one fresh state per padded level, and the ε moves of either side are routed through such chains. After the epsilon filter (#812) and configuration interning (#813), one route per ε schedule remains, but the output still contains whole-round ε runs (ε on every level, from a zero-level state to a zero-level state) between generated states, and generated chains with identical futures. trim() runs only when the synchronization levels are projected (L1082-L1083) and removes dead states only; redundant live states stay.

Not every ε can go. An ε on a nonzero level is the ε of that track: in a 3-level result, q0 -ε-> p1 -ε-> p2 -a-> q3 encodes (ε, ε, a), and bypassing p1 and p2 would need a jump, which under JumpMode::RepeatSymbol would put a on all three tracks. Only whole-round ε runs can be closed away, and only states whose origin is known can be merged without analysis.

The generic nft::remove_epsilon() closes such runs when their inner states have one incoming and one outgoing transition, but it does not work as a composition post-pass. It reverts an NFA copy (L396), enumerates safe runs (L410-L462), closes StateSets in a Floyd–Warshall-style pass (L464-L486), copies the whole NFT (L491), removes the run transitions one at a time through a std::set (L494-L504) and adds the closure posts with Delta::add (L506-L517). Its safety test is also wrong (#728).

Local Release probe on f874bae (GCC 15.2, -O3 -DNDEBUG, median of 3). Family: a 2-level NFT with n fast ε-transitions and then x x, composed with a 1-level NFT with n ε-transitions and then x (sync 1/0, projected; the relation is one tuple):

n Raw result After remove_epsilon() + trim() Cleanup time
16 290 / 545 2 / 1 2.6 ms
32 1,090 / 2,113 2 / 1 76 ms
64 4,226 / 8,321 2 / 1 4.8 s

The composition itself takes 0.8 ms at n = 64. On typical output there is little to remove: for random 2-level operands (200 zero-level states, 20% ε, synchronization level kept, single run) the trimmed result has 150,622 states. remove_epsilon() + trim() takes 146 ms (the composition 39 ms) and removes 3% of them; merging all bisimilar states would remove 16%. Calling remove_epsilon() after every compose() is therefore slow on both kinds of input, and a composition-specific pass must be nearly free on output that is already compact.

Proposed change

Normalize while building, where the builder knows which states it generated and why. The target is a composition-normalized result with stated invariants; general minimization of nondeterministic transducers is out of scope.

  1. Tag generated states with their origin (Padding, ProjectedBridge, Waiting; product states are Semantic) and record which rules may touch each kind. No rule removes a Semantic state.

  2. Emit generated nodes through a delayed emitter. Before a completed pending node gets a permanent number:

    A node is complete once its configuration is fully expanded; before that, its filter phase decides which transitions it will still receive, so incomplete nodes are never merged.

  3. Keep a predecessor count or list inside the builder, so no rule scans the whole delta.

  4. Detect ε SCCs among generated states and leave nontrivial ones unchanged at first. Quotient them later only under a proven relation-preserving equivalence.

  5. Expose the modes None, GeneratedOnly and an explicit, expensive Full. Auto uses GeneratedOnly only if it wins end to end. The option belongs with the strategy settings of composition dispatch and contracts (NFT composition: validate the whole compose() request and expose which strategy ran #818).

  6. When construction can show that no dead configuration exists, skip the unconditional trim() at L1082-L1083, whose TODO asks for trimming on demand.

enum class GeneratedKind { Semantic, Padding, ProjectedBridge, Waiting };

struct PendingNode {
    Level level;
    GeneratedKind kind;
    bool initial;
    bool final;
    EdgeBuffer outgoing;
};

Sharing padding suffixes by their semantic continuation at creation time is part of configuration interning (#813). This issue covers merging completed generated nodes by structural signature and closing whole-round ε runs. Faster generic ε removal stays separate (#240; correctness in #728).

Explanation and worked example

A safe case. In a 2-level result, suppose the composer generated q0 -ε-> p -ε-> r (levels 0, 1, 0) and r -a-> s -b-> t. q0 → p → r is a whole round of ε. If p and r exist only as padding, are neither initial nor final, and have no other predecessors, q0 takes over r's posts (q0 -a-> s) and both p and r disappear.

Unsafe variants. If p also has p -b-> u, the tuple (ε, b) goes through p, so the run is not all ε and p stays. If p has a second incoming transition, from q1, deleting p -ε-> r strands q1; this is the #728 bug, where the check counts distinct incoming symbols instead of incoming transitions. If r has a second predecessor, r stays for it while q0 still takes over its posts and p goes away. If r is final, q0 becomes final.

Levels and phases. Two generated states with identical outgoing posts on different levels are not mergeable, because the reading head differs. Two states on the same level can still differ while one of them is inside an rhs ε run of the filter; they become comparable only when both are complete.

Why local rules first. The composer knows which states it generated, why they exist, and whether they are observable from outside. A generic post-pass has lost that information and has to rediscover safety through graph analysis, which is what the measurements above show.

Step-by-step execution plan

Read first: every helper in composition.cc that creates a result state or path, trim(), NFT remove_epsilon(), project_out(), and the state-renaming utilities. Classify each generated state: why it exists, whether its level is observable, and which branches may enter it.

  1. Add raw and normalized counts without changing defaults. Create golden examples for a safe run, an unsafe branch, a final forwarder, an initial forwarder, a cycle, and differing levels.
  2. Add the origin tags in the composition builder only, and assert that no rule eliminates a Semantic state.
  3. Implement one safe rewrite at a time: first merging of identical completed padding nodes, then single-predecessor whole-round ε runs.
  4. Check each rewrite with a small checker that compares all bounded tuple traces before and after, then with full relation-equivalence tests.
  5. Add detection of generated ε SCCs with a conservative "do not normalize" fallback. A recursive finalizer must never loop on a cycle.
  6. Benchmark the normalization cost and the saved downstream cost separately, for compose alone and for compose followed by the next operation.
  7. Make GeneratedOnly the default only if it wins end to end and causes no meaningful regression on output that is already compact.

Dependencies and hand-off: Lands after the epsilon filter (#812), which removes the redundant schedules, and configuration interning (#813), which shares suffixes at creation time. Label lookahead (#816) lands in the same step and reduces dead configurations; together they decide when the final trim() can be skipped. Deliver the rule list with the invariant of each rule, the negative tests, and raw and normalized counts for the benchmark families.

Definition of done: every rewrite has a named invariant and a negative test in which it must not fire; raw and normalized counts are both recorded; normalization is near-linear in generated states and transitions; on the ε-prefix family, compose plus normalize stays far below the 4.8 s of the generic cleanup and the output approaches 2 states and 1 transition; ε-free and compact outputs stay within 3%.

Expected result and validation

The gain is mainly downstream: an estimated 2–50× smaller output on generated-ε-heavy families and 1.2–10× on the operations that follow. Typical random output changes little (see above), so the pass itself must be cheap enough to keep ε-free and compact compositions within a 3% budget.

State numbering is not contractual unless an existing API or test requires it; the relation and the level of every state are. The current composition tests compare after normalizing both the actual and the expected NFT and bound raw sizes only on small hand-written cases. Add count assertions before normalization on generated-ε families, and assertions on the origin tags; otherwise a change can keep the relation while silently reintroducing thousands of generated ε states.

Related: #728 (nft::remove_epsilon counts incoming symbols instead of incoming transitions), #240 (ε-removal performance).

Part of the composition work tracked in (#790).

Metadata

Metadata

Assignees

No one assigned

    Labels

    For:libraryThe issue is related to library (c++ implementation)Module: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