Repository navigation
Description
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:
- computes a common level layout (L1118-L1185);
- copies both NFTs with the other side's levels inserted (L1188-L1189);
insert_levels()pads every transition with DONT_CARE on those levels; - 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;
- builds the generic product (L1199);
- 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
-
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.
-
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; };
-
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.
-
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.
-
Add jump modes one at a time:
NoJump,AppendDontCares, thenRepeatSymbol. Unsupported combinations call the current pipeline, which stays as the reference strategy and fallback. -
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).
-
Let
Autochoose the new engine only after both are benchmarked, through the strategy override and cost features of composition dispatch and contracts (NFT composition: validate the wholecompose()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.
- Extract the mask computation into a tested
CompositionSchedulewithout changing graph construction. - 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. - Implement direct
NoJumpcomposition behind a new internal mode. Keep the synchronization levels at first, so direct traversal and projection are not combined in the first change. - Differential-test against the current general composition on random acyclic NFTs with multiple initial and final states, empty posts, wildcards and ε.
- Fuse projected synchronization levels by computing the small local closure inside successor generation. Guard against cycles and cache by projected configuration.
- Add the jump modes separately, with focused tests for skipped levels and wraparound. Do not infer jump behavior from numeric level comparison alone.
- Instrument copied input states (zero on the direct path), padding states avoided, unique configurations, projected internal expansions and raw output counts.
- Benchmark both strategies over levels, synchronization blocks, padding imbalance, reachability, ε density and jumps, and add z3-noodler cases that use general composition.
- Let
Autoselect 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
nft/project_out: +refactor Compute the closures by a search from the …
nft: +feat Compose operands with DONT_CARE by the direct general comp…
nft: +feat Read jump transitions under AppendDontCares in the direct …
nft: +feat Read jump transitions under RepeatSymbol and NoJump in the…
nft: +fix Read each projected level once per configuration in the dir…
nft: +refactor Extract the level layout of the general composition in…
nft: +feat Compose jump-free NFTs without DONT_CARE by a direct trave…
nft: +feat Fuse the projection of the synchronization levels into the…
nft: +feat Let compose_general() take the direct composition inside i…
nft: +feat Compose operands with DONT_CARE by the direct general comp…
nft: +feat Read jump transitions under AppendDontCares in the direct …
nft: +feat Read jump transitions under RepeatSymbol and NoJump in the…
nft: +fix Read each projected level once per configuration in the dir…
nft: +refactor Extract the level layout of the general composition in…
nft: +feat Compose jump-free NFTs without DONT_CARE by a direct trave…
nft: +feat Fuse the projection of the synchronization levels into the…
nft: +feat Let compose_general() take the direct composition inside i…
nft: +feat Compose operands with DONT_CARE by the direct general comp…
nft: +feat Read jump transitions under AppendDontCares in the direct …
nft: +feat Read jump transitions under RepeatSymbol and NoJump in the…
nft: +fix Read each projected level once per configuration in the dir…
nft: +feat Compose by a direct traversal of the aligned configuration…