8000 NFT composition chains: on-demand trim, result metadata and certified reordering · Issue #819 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

NFT composition chains: on-demand trim, result metadata and certified reordering #819

Open

Description

@koniksedy

Severity: Medium · Effort: Medium first phase, Large for planning and fusion · Expected effect: 1.1–2× estimate from removing repeated cleanup and copies in chains; 2–100× only where a certified reordering avoids a large intermediate

Scope: the public compose() API, the composer's trim after projection (and the trim at the end of project_out that compose_general reaches), and the chains that call it: Mata's noodlify_for_transducer and, in z3-noodler devel (ccf9f8e3), regex.cpp#L1375-L1376, regex.cpp#L666, formula_preprocess.cpp#L1869-L1873 and decision_procedure.cpp#L648-L676.

Problem

Real callers compose more than two NFTs, one binary compose() per step, usually followed by generic cleanup:

Call site Sync levels Projection Mode After each step
z3-noodler regex.cpp L1375-L1376 (replace chains) 1, 0 yes NoJump, fast path reduce(remove_epsilon(t).trim()).trim()
z3-noodler regex.cpp L666 (rational compose) defaults 1, 0 yes defaults (RepeatSymbol), General operands cleared
z3-noodler formula_preprocess.cpp L1869-L1873 0, 0 only in the last step NoJump nothing
z3-noodler decision_procedure.cpp L662, L667 (recursive) 1, 0 and 0, 0 no NoJump .trim() on the returned temporary
Mata noodlification.cc L472-L499 0, 0 and 0, 1 no NoJump trim(), emptiness check; later reduce(remove_epsilon(x).trim()).trim()

What this shows on current code:

  • The composer trims only when it projects (composition.cc L1083; General reaches the trim in project_out). Every sampled caller that trims right after compose passes project_out_sync_levels = false, so its trim is the only one and is needed. No sampled call site trims twice in a row. The repeated whole-graph passes are elsewhere: in the replace chain, each step runs the composer's trim and then remove_epsilon, trim, reduce and trim again, and every replace NFT gets the same sequence before it enters the chain (regex.cpp L1356).
  • Nft::trim() returns Nft&, so Nft x = compose(...).trim(); and final_trans = compose(...).trim(); in decision_procedure.cpp copy the whole result. This is the pattern of Avoid deep copies from chained trim() on temporaries, Nft move-assignment and renumber_targets()/append() #745, here in z3-noodler.
  • Operands are often dead after the call (transducer and next_transducer at L1375, arg_nfts cleared after L666, intersection at noodlification.cc L498), but compose takes const Nft& and cannot reuse their storage.
  • The formula_preprocess.cpp chain composes untrimmed intermediates: without projection the composer does not trim, and nothing trims between the steps, so dead pairs from step i are input to step i+1.
  • A binary chain fixes the evaluation order, which can create a huge intermediate even when another order stays small.

Relational composition is associative, but a Mata compose() call also fixes the selected level mappings, projection, alphabet objects, wildcard and EPSILON semantics, and the jump mode. Reassociating because (A∘B)∘C = A∘(B∘C) holds on paper is therefore wrong in general. It is legal only after proving that the complete request describes the same tuple-track relation and the same output level order.

Proposed change

Phase 1: measure and remove repeated passes

  1. Keep the call-site inventory above current, and add per-stage timing and size telemetry in a representative z3-noodler benchmark build: wall time, raw and final sizes, trim, remove_epsilon and reduce time, and peak live intermediate size.
  2. Make the composer's trim on demand (the TODO: Make trim on demand. at L1082) and return construction metadata such as may_contain_dead_states and a trimmed flag, through an internal CompositionResultInfo or a structural property from Delta metadata (Delta: O(1) empty() and transition count, epoch-cached structural properties #805). A caller that immediately runs remove_epsilon and trim can then skip the composer's trim, and a caller without projection can skip its own trim when the composer proves the result dead-free (for example after label lookahead (NFT composition: prune state pairs whose future synchronization labels cannot match #816)). Remove a caller's pass only with a regression test and a documented guarantee.
  3. Consuming paths for dead operands and the copies from .trim() on temporaries belong to move-aware pipelines (Union, concatenation and plumbing: Nfa&& overloads that reuse a dead operand's storage #810), including its review of the z3-noodler call sites. Here, only measure copies and allocations per chain step.
  4. Measure the generic cleanup after each step. If composition-generated EPSILON artifacts dominate it, the fix is construction-time epsilon normalization (NFT composition: collapse generated epsilon rounds and duplicate paths during construction #815).

Phase 2: cost-aware planning, only after phase 1 data

  1. Represent a requested chain and its track mappings explicitly as a track schema, with a verifier for legal reassociation that returns "not certified" by default. Test it exhaustively on small schemas.
  2. Estimate intermediate size from state and transition counts, synchronization selectivity, label frontiers (NFT composition: prune state pairs whose future synchronization labels cannot match #816), EPSILON ambiguity and projected levels. Choose among certified parenthesizations with a small dynamic program for short chains, behind an opt-in mode, and keep the original order as a forced option and as the differential oracle.

Phase 3: fused multiway traversal, only if binary intermediates still dominate

  1. Traverse a tuple of operand configurations once, apply the synchronization filters at each shared boundary, project internal tracks without materializing binary intermediates, and intern the full configuration before emitting output (reusing the keys of configuration interning (NFT composition: intern waiting configurations and expand each one once #813)). Prototype on one fixed three-stage pattern, and drop it if the epsilon filter (NFT composition: add an epsilon-filter state so each epsilon interleaving is built once #812) and direct general composition (compose_general: direct traversal instead of padded copies, product and project_out #814) already remove the bottleneck.
Explanation and worked example

Reordering. Suppose A∘B admits nearly every pair and creates one million intermediate states, while composing B with a restrictive C first leaves ten. If the level mapping permits it, A∘(B∘C) is dramatically faster, much as a database query planner applies selective joins early. If the first composition keeps a synchronization track that the second step inspects or maps differently, changing the parentheses changes the represented tuples. The planner therefore needs an explicit track schema; three NFT pointers do not say which tracks each step keeps.

Repeated cleanup. In the replace chain, one step is compose (which trims because it projects), then remove_epsilon, trim, reduce, trim. The composer's trim may still pay for itself by shrinking the input of remove_epsilon, and the generic remove_epsilon is expensive on composition output. Only per-stage measurements show which pass to drop. When a pass is dropped, the guarantee that makes it redundant must be a checked property of the result.

Why not start with a three-way algorithm? Much of the benefit may come from smaller binary outputs (the epsilon filter, label lookahead) and from not repeating cleanup. Measure chain profiles before accepting the complexity of multiway traversal.

Step-by-step execution plan

Read first: all compose( and apply( call sites in Mata and z3-noodler, the operations applied to their results, the alphabet and level APIs, and the move-aware pipeline issue (#810). For each chain, draw the input and output tracks and mark which synchronized tracks are projected.

  1. Add scoped benchmark counters without changing the call order. Capture per-stage wall time, raw and final sizes, trim time, and peak live intermediate size.
  2. For each post-compose cleanup, check whether it is redundant for the options used there. On z3-noodler devel the decision_procedure.cpp trims follow project_out_sync_levels = false and are needed. Change a call site only with a regression test and a documented guarantee.
  3. Measure allocations and copies per step on repeated chains, and hand the call sites to move-aware pipelines (Union, concatenation and plumbing: Nfa&& overloads that reuse a dead operand's storage #810).
  4. Build a pure schema-composition function. Test associativity eligibility exhaustively on small schemas, returning "not certified" by default.
  5. Compare all certified parenthesizations offline on a corpus. Fit a readable estimator and test it on held-out cases.
  6. Add planner execution behind an opt-in mode. Validate the final relation and the output track and alphabet metadata against the original order.
  7. If binary intermediates remain dominant, prototype fused traversal on one fixed three-stage pattern.

Dependencies and hand-off: Last in the composition sequence. Re-measure z3-noodler after the epsilon filter (#812), label lookahead (#816) and epsilon normalization (#815) land, and only then start phases 2 and 3. Consuming overloads come from move-aware pipelines (#810).

Definition of done: every removed cleanup pass is proven redundant for its call and covered by a structural or property test; move-aware steps reduce measured copies without changing lvalue operands; no reassociation happens without a certified identical track schema; end-to-end z3-noodler time, timeout count and peak RSS are measured before and after.

Expected result and validation

Estimate 1.1–2× on chains from removing repeated cleanup and copies, and potentially 2–100× where a chain now creates a disastrous intermediate. The second range requires legal reassociation and a corpus with selective later stages.

  • Every removed cleanup pass is proven redundant for that call and covered by a structural or property test.
  • Move-aware paths reduce measured copies without changing operands passed as lvalues.
  • Reassociation never happens without a certified identical track schema and relation semantics.
  • End-to-end z3-noodler time, timeout count and peak RSS are the 8000 primary metrics; microbenchmarks are secondary.
  • The original binary order stays available as a fallback and as the differential oracle.

Related: #745 (copies from chained trim() on temporaries in Mata), #753 (b) (Auto picks General for default-argument calls such as regex.cpp L666), #750 item 3 (trim before project_out in compose_general), #207 (noodlification cost).

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