Repository navigation
Description
Severity: Medium · Effort: Medium · Expected effect: no deep copy of operands the caller no longer needs; 1.2–3× target on construction pipelines that pass temporaries
Scope: union_nondet, Nfa::unite_nondet_with, Nfa::concatenate, concatenate and algorithms::concatenate_eps, the plumbing wrappers, the free-operation declarations in nfa.hh, and the Nfa move operations (nfa.hh#L151-L157, nfa.cc#L399-L406).
Already filed
- Avoid deep copies from chained trim() on temporaries, Nft move-assignment and renumber_targets()/append() #745: rewrites the chained
.trim()/complement_deterministic()call sites andunion_nondetso they stop copy-constructing from a returnedNfa&; adds the twostd::moves inrenumber_targetsandappend(std::vector<StatePost>&&); fixesNftmove-assignment (already fixed on devel); optionally adds a ref-qualifiedtrim() &&.
This issue is only about letting a caller hand over an operand it no longer needs. The in-repo ε-concatenation folds in noodlification are left to #207 (comment, item c).
Problem
Every free NFA operation takes its operands as const Nfa&. union_nondet(std::move(a), b) compiles, binds to const Nfa&, and copies a anyway. The plumbing wrappers call *res = op(lhs, rhs), so plumbing::union_nondet(&a, a, b) copies a into a new union and then move-assigns the result back into a.
After #745, union_nondet still copies lhs once. With a const operand that copy is unavoidable, even when the caller drops lhs right afterwards. Similarly:
concatenate_epsstarts withresult.delta = lhs.delta(L98), a full copy of the left delta. Bulk Delta primitives: offset append for union/concatenation and a predecessor index for revert #751 turns the right-hand side into oneappend_shifted, which still copies every post ofrhs.unite_nondet_with(const Nfa&)copies the whole operand whenthishas no initial or final states (L463-L466).
A local Release probe (GCC 15.2, -O3 -DNDEBUG, commit bb63f4eb) measured a deep copy of a 5,000-state, 40,000-transition DFA at about 1.35 ms and 45,005 allocations. After the core algorithms get faster, a few such copies per step can dominate a z3-noodler rewrite pipeline.
Consuming complement and determinize overloads belong with the deterministic fast paths (#801) and the complement pipeline (#802), where the in-place case is a certified DFA. trim() && is #745's optional item.
Proposed change
- Fix one overload policy and document it in the header: add
Nfa&&overloads next to the existingconst Nfa&ones. This is ABI-additive. Replacingconst Nfa&by a by-value parameter would change the mangled name of an exported function, and keeping both forms would make lvalue calls ambiguous. State which operand may be consumed and that a moved-fromNfais valid but unspecified. - Add
Delta::append_shifted(Delta&& other, State offset)on top of Bulk Delta primitives: offset append for union/concatenation and a predecessor index for revert #751. It shiftsother's targets in place (a monotone shift keeps every target set sorted) and moves itsStatePosts, so appending allocates nothing per post. Checkoffset + other.num_of_states()for overflow first. - Union: add
Nfa::unite_nondet_with(Nfa&&)andunion_nondet(Nfa&& lhs, const Nfa& rhs), andunion_nondet(Nfa&&, Nfa&&)for when both operands are dead. The left operand provides the base storage, and a dead right operand goes through step 2. State numbering stays exactly as in theconstversions (lhs states first). - Concatenation: add
Nfa::concatenate(Nfa&&),concatenate(Nfa&& lhs, const Nfa& rhs, ...)andalgorithms::concatenate_eps(Nfa&& lhs, ...).result.delta = lhs.deltabecomes a move, and a deadrhsgoes through step 2. The consuming overload must return the same automaton as theconstone:concatenate_epscurrently returns an NFA withoutlhs's alphabet, so either reset it or change both overloads together. - Detect aliasing before consuming anything.
union_nondet(std::move(a), a)would otherwise read a moved-fromrhs, anda.concatenate(std::move(a))would do the same. Fall back to one controlled snapshot, as theconstpaths do today. - Plumbing: when
res == &lhs, consume*resinstead of copying it (res->unite_nondet_with(rhs)for union,*res = concatenate(std::move(*res), rhs, ...)for concatenation, sinceNfa::concatenatebuilds a different automaton than the ε-based free function), and addNfa&&operand overloads that forward to steps 3 and 4. - Keep every
const Nfa&overload with unchanged behavior; each makes exactly one intentional copy and then delegates to the consuming path. - Review z3-noodler call sites for operands that are dead after the call and migrate only those, with
std::move. Mirror the overloads forNft(nft::union_nondet,Nft::concatenate) once the NFA versions settle.
Explanation and worked example
Copying can dominate a finished algorithm. A 5,000-state, 40,000-transition DFA deep copy made 45,005 allocations and took about 1.35 ms. If a pipeline does tmp = intersection(a, b); tmp.trim(); u = union_nondet(tmp, c); and never uses tmp again, the union should reuse tmp's delta and state sets instead of copying them.
Value-category example. union_nondet(const Nfa& lhs, const Nfa& rhs) must preserve lhs, so copying it is correct. union_nondet(Nfa&& lhs, const Nfa& rhs) has permission to consume lhs: it appends the shifted posts of rhs onto lhs's delta and returns lhs by move.
| Call | Safe behavior |
|---|---|
union_nondet(a, b) |
Preserve both; copy the base once |
union_nondet(std::move(a), b) |
Reuse a's storage; a is left valid but unspecified |
union_nondet(std::move(a), a) |
Detect the alias and take a controlled snapshot |
plumbing::union_nondet(&a, a, b) |
Unite in place, no temporary |
Why adding std::move at call sites is not enough. If the callee only accepts const Nfa&, std::move changes nothing. If the caller uses the object later, moving is a bug. The consuming API has to exist, and each call site needs a liveness check. Move the delta, initial and final sets, alphabet and attributes together, and later the cached properties from delta metadata/epoch (#805).
Offset appends are the easy case. Union and concatenation shift the right operand's states by a constant. The shift is monotone, so a dead operand's target sets can be renumbered in place and its state posts moved whole. Check overflow and aliasing first, and benchmark allocations to prove that the rvalue path really removed the deep copy instead of moving into another copying helper.
Step-by-step execution plan
Read first: the free-operation declarations in include/mata/nfa/nfa.hh and algorithms.hh, plumbing.hh, the Nfa/Automaton copy and move members, unite_nondet_with, Nfa::concatenate, concatenate_eps, #745 and #751, and the z3-noodler call chains. Decide operand liveness from the call sites themselves, never from temporary syntax alone.
- Add counted-allocation benchmarks for lvalue and rvalue copy, union and concatenation, and for a multi-stage chain. Add tests for moved-from validity and for exception behavior.
- Write the overload policy into the header documentation (step 1 above) and check that no existing call becomes ambiguous.
- Implement
append_shifted(Delta&&, State)with its overflow check on top of Bulk Delta primitives: offset append for union/concatenation and a predecessor index for revert #751'sappend_shifted. Test self-append, empty operands, and states that exist only ininitial/final. - Implement the consuming union overloads, then the concatenation overloads. Move delta, initial and final sets, alphabet and attributes as one object, and keep the result identical to the
constoverload's, including the alphabet. - Add the alias checks (
&lhs == &rhs) before any storage is consumed, and test self-union and self-concatenation for exact language and state mapping. - Teach plumbing the in-place case (
res == &lhs) and theNfa&&forwarding overloads, and test that each produces exactly what theconstwrapper produces. Keep theconstwrappers. - Review z3-noodler, migrate only operands that are demonstrably dead, review every use-after-move path, and run its tests and benchmarks.
- Record copies, moves, allocations, bytes and wall time. Check whether small moved inputs keep excessive capacity, and shrink only if profiling supports it.
Dependencies and hand-off: Builds on #745 and on #751's append_shifted. When the #782 builder lands, it should hand out its delta through finish() && so the result moves into the automaton. The consuming complement/determinize overloads come with the deterministic fast paths (#801) and the complement pipeline (#802); the certificates from delta metadata/epoch (#805) must move with the delta. New public overloads need a source-compatibility review.
Definition of done: rvalue union and concatenation perform no avoidable deep copy, lvalue behavior and results are unchanged, self-aliasing is safe, all automaton members move together, z3-noodler use-after-move checks pass, and allocation probes show the copies are gone.
Expected result and validation
Near-elimination of deep-copy allocations when operands are consumable, and a 1.2–3× target on construction and transformation pipelines. Read-only algorithms do not benefit.
Benchmark lvalue against rvalue union, concatenation and plumbing chains, and record bytes and allocations. Test self-aliasing, exception safety, alphabet and attribute ownership, moved-from validity and exact output identity with the const overloads.
Related: #751 (alias-safe Delta::append_shifted(const Delta&, State) for union and concatenation, which the consuming overloads build on), #207 (comment, item c: n-ary in-place ε-concatenation for the noodlification folds)
Activity
nfa: +feat Nfa&& overloads for union and concatenation
nfa: +feat Nfa&& overloads for union and concatenation
nfa: +feat Nfa&& overloads for union and concatenation
nfa: +feat Nfa&& overloads for union and concatenation
nfa: +feat Nfa&& overloads for union and concatenation
nfa: +feat Nfa&& overloads for union and concatenation (#919)
nfa, nft: +feat Consume dead operands of union and concatenation (#954)
nfa, nft: +feat Consume dead operands of union and concatenation