8000 Union, concatenation and plumbing: `Nfa&&` overloads that reuse a dead operand's storage · Issue #810 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

Union, concatenation and plumbing: Nfa&& overloads that reuse a dead operand's storage #810

Open

Description

@koniksedy

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

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:

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

  1. Fix one overload policy and document it in the header: add Nfa&& overloads next to the existing const Nfa& ones. This is ABI-additive. Replacing const 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-from Nfa is valid but unspecified.
  2. 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 shifts other's targets in place (a monotone shift keeps every target set sorted) and moves its StatePosts, so appending allocates nothing per post. Check offset + other.num_of_states() for overflow first.
  3. Union: add Nfa::unite_nondet_with(Nfa&&) and union_nondet(Nfa&& lhs, const Nfa& rhs), and union_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 the const versions (lhs states first).
  4. Concatenation: add Nfa::concatenate(Nfa&&), concatenate(Nfa&& lhs, const Nfa& rhs, ...) and algorithms::concatenate_eps(Nfa&& lhs, ...). result.delta = lhs.delta becomes a move, and a dead rhs goes through step 2. The consuming overload must return the same automaton as the const one: concatenate_eps currently returns an NFA without lhs's alphabet, so either reset it or change both overloads together.
  5. Detect aliasing before consuming anything. union_nondet(std::move(a), a) would otherwise read a moved-from rhs, and a.concatenate(std::move(a)) would do the same. Fall back to one controlled snapshot, as the const paths do today.
  6. Plumbing: when res == &lhs, consume *res instead of copying it (res->unite_nondet_with(rhs) for union, *res = concatenate(std::move(*res), rhs, ...) for concatenation, since Nfa::concatenate builds a different automaton than the ε-based free function), and add Nfa&& operand overloads that forward to steps 3 and 4.
  7. Keep every const Nfa& overload with unchanged behavior; each makes exactly one intentional copy and then delegates to the consuming path.
  8. Review z3-noodler call sites for operands that are dead after the call and migrate only those, with std::move. Mirror the overloads for Nft (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.

  1. 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.
  2. Write the overload policy into the header documentation (step 1 above) and check that no existing call becomes ambiguous.
  3. 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's append_shifted. Test self-append, empty operands, and states that exist only in initial/final.
  4. 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 const overload's, including the alphabet.
  5. Add the alias checks (&lhs == &rhs) before any storage is consumed, and test self-union and self-concatenation for exact language and state mapping.
  6. Teach plumbing the in-place case (res == &lhs) and the Nfa&& forwarding overloads, and test that each produces exactly what the const wrapper produces. Keep the const wrappers.
  7. Review z3-noodler, migrate only operands that are demonstrably dead, review every use-after-move path, and run its tests and benchmarks.
  8. 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)

Metadata

Metadata

Assignees

No one assigned

    Labels

    For:libraryThe issue is related to library (c++ implementation)Module:nfaThe issue is related to Nondeterministic Finite Automatatype: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