Repository navigation
Description
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 aftercomposepassesproject_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 thenremove_epsilon,trim,reduceandtrimagain, and every replace NFT gets the same sequence before it enters the chain (regex.cppL1356). Nft::trim()returnsNft&, soNft x = compose(...).trim();andfinal_trans = compose(...).trim();indecision_procedure.cppcopy 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 (
transducerandnext_transducerat L1375,arg_nftscleared after L666,intersectionat noodlification.cc L498), butcomposetakesconst Nft&and cannot reuse their storage. - The
formula_preprocess.cppchain 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
- 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_epsilonandreducetime, and peak live intermediate size. - Make the composer's trim on demand (the
TODO: Make trim on demand.at L1082) and return construction metadata such asmay_contain_dead_statesand a trimmed flag, through an internalCompositionResultInfoor a structural property from Delta metadata (Delta: O(1)empty()and transition count, epoch-cached structural properties #805). A caller that immediately runsremove_epsilonandtrimcan 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. - 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. - 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
- 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.
- 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
- 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 andproject_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.
- 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.
- For each post-compose cleanup, check whether it is redundant for the options used there. On z3-noodler
develthedecision_procedure.cpptrims followproject_out_sync_levels = falseand are needed. Change a call site only with a regression test and a documented guarantee. - 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). - Build a pure schema-composition function. Test associativity eligibility exhaustively on small schemas, returning "not certified" by default.
- Compare all certified parenthesizations offline on a corpus. Fit a readable estimator and test it on held-out cases.
- Add planner execution behind an opt-in mode. Validate the final relation and the output track and alphabet metadata against the original order.
- 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).
Activity
nft: +feat Compose a trimmed result from the final states when that b…
nft: +fix Race the directions of the fast composition only for an exp…
nft: +feat Compose a trimmed result from the final states when that b…