8000 `compose_general`: direct traversal instead of padded copies, product and `project_out` · Issue #814 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content
< 8BD0 div class="height-full" hidden="">

compose_general: direct traversal instead of padded copies, product and project_out #814

Open

Description

@koniksedy

Severity: Critical · Effort: Research/Large · Expected effect: 2–20× target on multi-sync or padding-heavy inputs; lower peak memory

Scope: compose_general(), with insert_levels(), the NFT product() and project_out(); dispatch in compose().

Problem

compose_general() runs for every call with more than one synchronization level, for every jump mode other than NoJump, and for compose() and Nft::apply() with their default arguments. It does not traverse the composition. It:

  1. computes a common level layout (L1118-L1185);
  2. copies both NFTs with the other side's levels inserted (L1188-L1189); insert_levels() pads every transition with DONT_CARE on those levels;
  3. adds a whole-round self-loop at every zero-level state of both copies (L1106-L1116, L1195-L1197): ε on the NFT's own levels, DONT_CARE on the inserted ones;
  4. builds the generic product (L1199);
  5. if asked, projects the synchronization levels out of the untrimmed product (L1200; Small independent speedups: naive inclusion product map, universality cex paths, compose_general trim, RE2 copy, is_flat, random NFA generator #750 item 3).

The product rejects only pairs of two self-loop states (intersection.cc#L63-L64). A self-loop state paired with an original state is created whenever the other copy's inserted DONT_CARE meets the self-loop's ε, because product() lets DONT_CARE match ε (#561). Such a pair gets past the synchronization level only when the other side has ε there (or DONT_CARE, which product() also matches with ε); otherwise it dies. Pairs that can never synchronize are not pruned either, since the synchronization-type lookahead of the fast composer has no counterpart here.

Local Release probe on f874bae (GCC 15.2, -O3 -DNDEBUG, single runs). Random jump-free NFTs: each zero-level state has three rounds to random zero-level states, and every fourth zero-level state is final. The intermediate counts come from a copy of the compose_general() pipeline.

Operands (both) Product states …pairing a self-loop state (useful) Product after trim() Result compose_general() fast path
2 levels, 800 states, no ε, sync 1/0, projected 133,603 56,228 (0) 38,338 23,332 85 ms 18 ms
2 levels, 800 states, 10% ε, sync 1/0, projected 200,596 93,712 (21,666) 79,768 46,972 143 ms 36 ms
4 levels, 4,000 states, 10% ε, sync {1,3}/{0,2}, projected 1,527,360 386,298 (21,400) 465,392 295,404 2.5 s n/a

70% of the 4-level product is dead, and project_out() then processes all of it; projection takes about half of the 2.5 s. On the 2-level rows the general path is 4–5× slower than the fast path for the same relation, which matches the measurement in #753.

Proposed change

  1. Describe the level alignment as a compact immutable schedule of blocks: lhs-only levels, rhs-only levels, synchronization level, next block. Extract it from the current mask computation first.

  2. Traverse virtual aligned configurations: the original operand states plus a cursor per operand into the schedule. A padding step advances one cursor. No copied NFT, no inserted level and no self-loop exist.

    struct GeneralCompositionKey {
        State lhs;
        State rhs;
        SyncBlock block;
        LevelCursor lhs_cursor;
        LevelCursor rhs_cursor;
        EpsilonFilterState filter;
        WaitingPhase waiting;
    };
  3. Reuse the epsilon filter (NFT composition: add an epsilon-filter state so each epsilon interleaving is built once #812) in every synchronization block, with the block and phase in the interned key, and the fast composer's synchronization-type lookahead per block. Label lookahead (NFT composition: prune state pairs whose future synchronization labels cannot match #816) refines that lookahead.

  4. Handle projection during move generation. A projected match becomes an internal expansion whose visible successors are attached directly to the predecessor, so no synchronization transition is built only to be removed.

  5. Add jump modes one at a time: NoJump, AppendDontCares, then RepeatSymbol. Unsupported combinations call the current pipeline, which stays as the reference strategy and fallback.

  6. Intern configurations before allocating states, as in configuration interning (NFT composition: intern waiting configurations and expand each one once #813), and build outgoing posts in bulk with the composition output builder (NFT composition: build each state's outgoing post in bulk and emit wildcard matches once #817).

  7. Let Auto choose the new engine only after both are benchmarked, through the strategy override and cost features of composition dispatch and contracts (NFT composition: validate the whole compose() request and expose which strategy ran #818).

Because padding is a cursor move, no inserted DONT_CARE has to match the other side's ε, so the direct engine does not depend on the permissive DONT_CARE/ε match discussed in #561.

Explanation and worked example

The current route. Let lhs have tracks [A, X], rhs have [X, B], and X be synchronized; the result is [A, B]. The general route first rewrites both machines to the common shape [A, X, B]. Every lhs round (a, x) becomes (a, x, *) and every rhs round (x, b) becomes (*, x, b). Every zero-level state gets a self-loop, (ε, ε, *) in lhs and (*, ε, ε) in rhs, so that one side can stand still while the other reads ε on X. The product of the two larger machines is then built and X is projected out.

The direct route. Keep the originals. At (L0, R0) lhs supplies A while rhs waits virtually; then both supply a matching X; then rhs supplies B while lhs waits virtually. Virtual waiting is a field of the configuration, nothing is copied into the zero-level states, and with projection the X transition is never emitted.

Why this matters. Eager alignment pays for all padding locations, including unreachable ones: in the ε-free row above, 56,228 product states pair an original state with a self-loop state and none of them is useful. Direct traversal pays only for configurations reachable from the initial pairs. Projection after the product also pays for synchronization transitions whose only purpose is to be removed.

Why not only speed up product(). A faster product helps, but it cannot recover the memory spent on copying both inputs and inserting padding paths, and it does not know that projected synchronization transitions need never be emitted.

Step-by-step execution plan

Read first: compose_general(), insert_levels(), the self-loop helper, the NFT product(), project_out(), the level and jump semantics, and every composition test with several synchronization levels. Before coding, write down the exact output level order for a worked pair of masks.

  1. Extract the mask computation into a tested CompositionSchedule without changing graph construction.
  2. Build a trace-only interpreter of the cursors. On hand examples, compare its emitted (side, old level, new level, block) trace with the physically aligned NFTs.
  3. Implement direct NoJump composition behind a new internal mode. Keep the synchronization levels at first, so direct traversal and projection are not combined in the first change.
  4. Differential-test against the current general composition on random acyclic NFTs with multiple initial and final states, empty posts, wildcards and ε.
  5. Fuse projected synchronization levels by computing the small local closure inside successor generation. Guard against cycles and cache by projected configuration.
  6. Add the jump modes separately, with focused tests for skipped levels and wraparound. Do not infer jump behavior from numeric level comparison alone.
  7. Instrument copied input states (zero on the direct path), padding states avoided, unique configurations, projected internal expansions and raw output counts.
  8. Benchmark both strategies over levels, synchronization blocks, padding imbalance, reachability, ε density and jumps, and add z3-noodler cases that use general composition.
  9. Let Auto select the new engine only inside its tested domain and keep a user/internal override so regressions can be isolated.

Dependencies and hand-off: The epsilon filter (#812) is a hard prerequisite. The engine also uses the keys from configuration interning (#813), the composition output builder (#817) and the strategy override from composition dispatch and contracts (#818); label lookahead (#816) prunes further. The trim() before project_out() from #750 item 3 is a stopgap for the current pipeline and stays useful on the fallback path. Deliver the schedule definition, the trace comparisons, and benchmark data for both strategies.

Definition of done: the direct and reference strategies accept the same tuple relation on exhaustive tiny and randomized cases; the direct path builds no aligned copy and no physical self-loop; on the ε-free row above the direct engine creates no waiting configuration, since neither side has ε to wait on; unsupported jump or semantic cases visibly fall back to the current pipeline.

Expected result and validation

2–20× target on multi-synchronization or heavily padded inputs, with lower peak memory. The largest gains are expected where eager padding makes the intermediate product much larger than the final relation, as in the 4-level row (1.5M product states for a 295k-state result).

Record setup, composition, projection, peak RSS and raw output separately for both strategies. Compare accepted relations; state numbering and ε placement may change.

Related: #750 (item 3: trim() before project_out() in the current pipeline), #561 (the DONT_CARE/ε match the current pipeline relies on), #753 (Auto sends default calls to this path).

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

Activity

  1. added
    For:libraryThe issue is related to library (c++ implementation)
    Module:nftThe issue is related to Nondeterministic Finite Transducers
    type:optimizationThis issue is related to a possible optimization of an algorithm, improving the performance of Mata.
    on Sep 30, 2026
  2. added 20 commits that reference this issue on Nov 5, 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: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