8000 NFT composition: intern waiting configurations and expand each one once · Issue #813 · VeriFIT/mata · GitHub
[go: up one dir, main page]

Skip to content

NFT composition: intern waiting configurations and expand each one once #813

Open

Description

@koniksedy

Severity: High · Effort: Medium/Large · Expected effect: exponential to linear work on branching waiting paths (measured below); 1.3–8× target on waiting-heavy inputs; lower peak memory

Scope: in compose_fast_no_jump(): waiting_state_storage, the waiting branch of copy_transition(), model_waiting(), create_epsilon_transition_with_common_path() and create_composition_state().

Problem

Ordinary result states are interned by (lhs, rhs) in composition_storage and enter the main worklist once. The states created while one side waits go through a local cache with weaker rules:

  • waiting_state_storage maps a running-side state to its waiting state and is cleared at the start of every model_waiting() call (L737). Two calls never share a waiting state, and the key is only the running state because the stationary state is fixed within one call.
  • A cache hit still pushes (waiting state, running state) onto the local worklist (L689-L698 in copy_transition(), L876-L886 in model_waiting(); the comment at L696-L697 mentions the re-push). There is no discovered or expanded flag, so a waiting state is expanded once for every path that reaches it within the round.
  • Every expansion of a sync-level running state that has more than one ε to emit calls create_epsilon_transition_with_common_path() (L827-L835), which always allocates a new chain.

The work is therefore proportional to the number of paths through the running side within one round, and with the synchronization level kept, so is the output. Local Release probe on f874bae (GCC 15.2, -O3 -DNDEBUG, median of 3; pop counts from an instrumented copy of composition.cc). lhs is a 3-level path x y z with synchronization level 1. rhs has 2k+1 levels: k diamonds (s -a-> p -a-> s', s -b-> q -b-> s'), then ε on its last level, which is its synchronization level, so lhs waits.

k rhs states / transitions waiting worklist pops result, sync level kept time result, projected time
4 14 / 17 61 32 / 50 0.01 ms 15 / 18 0.01 ms
8 26 / 33 1,021 284 / 546 0.18 ms 27 / 34 0.05 ms
12 38 / 49 16,381 4,136 / 8,242 8.6 ms 39 / 50 0.57 ms
16 50 / 65 262,141 65,588 / 131,138 1.5 s 51 / 66 9.3 ms

The pops are 2^(k+2) − 3. Every re-expansion of the last merge state adds a new padding chain, so with the synchronization level kept the output doubles per diamond; trim() removes one state. The exponential form needs branching and merging inside one round, so three or more levels on the running side. Two-level operands hit a linear form: with m parallel symbols from the running root into one state, that state is expanded m times and, with the synchronization level kept, gets m padding chains (m = 32: 37 states instead of 6).

The same lambdas copy every SymbolPost through insert_symbol_post_to_delta(const SymbolPost&) followed by std::move. That fix is #753 item (a) and is not part of this issue.

Proposed change

  1. Make the waiting context an explicit WaitingKey with every field that decides the future: stationary state, running state, waiting side, synchronization block and result level. The epsilon filter (NFT composition: add an epsilon-filter state so each epsilon interleaving is built once #812) adds its mode. Document why each field is needed.
  2. Add intern_waiting(key) returning {state, inserted} and push to the waiting worklist only when inserted. Assert in Debug builds that no configuration is expanded twice. This alone removes the exponential case.
  3. Keep the waiting storage for the whole composition (or the whole synchronization block) instead of one model_waiting() call. With the stationary state in the key, calls from different roots that reach the same waiting configuration share its states.
  4. Turn the entries of both worklists into complete keys or stable configuration ids instead of bare state pairs.
  5. Split create_epsilon_transition_with_common_path() into computing a path descriptor and interning/emitting it. Share a padding suffix only when its complete continuation key is equal. Start with suffixes, which are safer to share than prefixes.
  6. Emit the outgoing posts of a source through the composition output builder (NFT composition: build each state's outgoing post in bulk and emit wildcard matches once #817), sorted and deduplicated once.
struct WaitingKey {
    State stationary;
    State running;
    Side waiting_side;
    SyncBlock block;
    EpsilonFilterState filter; // added by the epsilon filter
    Level result_level;
};

struct PaddingSuffixKey {
    State semantic_target;
    Level next_level;
    SmallSymbolSequence remaining;
};
Explanation and worked example

Two questions. Suppose three branches all reach the situation "lhs is fixed at L7, rhs has reached R12; emit two ε, then continue at the same composition state". Today each branch draws its own two-state chain, so the graph holds three copies of the same future. A semantic cache answers the first question: is this really the same waiting situation? A suffix cache answers the second: if the futures are identical, may the last two padding states be shared? Keep the two apart. Two transitions with the same endpoint and different output symbols reach the same semantic endpoint through different emitted paths.

The diamond. In the measured family, the running rhs goes s -a-> p -a-> s' and s -b-> q -b-> s'. The cache gives p and q their own waiting states; both reach the cached waiting state of s' and each pushes it, so s' is expanded twice. With k diamonds in a row, the last state is expanded 2^k times. Discover-once interning expands every waiting configuration once, so the work becomes linear in the size of the running round.

What the key must contain. Keying only by the running state is correct today because the cache lives for one call. Once it lives longer, R12 waiting for L7 and R12 waiting for L9 are different configurations, so the stationary state and the waiting side join the key. Keying only by (lhs, rhs) is not enough either: with the epsilon filter (#812), the same pair in mode 0 and in mode 1 allows different next actions.

What must not be merged. Path multiplicity does not matter for the relation, but merging arbitrary look-alike paths can create crossovers: a prefix of branch A could gain a suffix that belonged only to branch B. Share a suffix only when the complete continuation key is equal.

Step-by-step execution plan

Read first: all local lambdas in compose_fast_no_jump(), especially state creation, create_epsilon_transition_with_common_path(), copy_transition() and both waiting directions. List every variable a waiting lambda captures. Each variable that changes future behavior belongs in the key or must be shown to follow from the key.

  1. Instrument waiting-cache hits and misses, worklist pushes and expansions, auxiliary states created per reason, and duplicate edge attempts.
  2. Add regressions: the diamond family with a bound on expansions, the parallel-symbol family, two routes that reach the same waiting configuration, and a control where the stationary states differ and must not merge.
  3. Introduce the typed keys and hashes with equality tests. Use small enums and fixed-width fields, and measure the key size.
  4. Replace worklist insertion with discover-once semantics and assert that an expanded configuration is never expanded again.
  5. Widen the cache lifetime one scope at a time and run the differential tests after each widening. A higher hit rate without relation equivalence is not success.
  6. Add suffix sharing behind an internal switch. Test the crossover counterexample before enabling it.
  7. Benchmark wait-heavy branching DAGs, repeated reconnections and ordinary sparse compositions. Record the cache hit rate and auxiliary states separately from the total state count.

Dependencies and hand-off: Can land right after composition dispatch and contracts (#818), which provides the instrumentation. The epsilon filter (#812) adds its mode to these keys, the composition output builder (#817) batches the outgoing posts, and #753 (a) removes the SymbolPost copy in the same lambdas. Deliver the key definitions with the list of captured variables and the reason each one is or is not in the key.

Definition of done: no configuration is expanded twice; on the diamond family, expansions and output grow linearly in k; keys with different futures never merge (randomized relation equivalence); simple cases stay within 3% median.

Expected result and validation

Linear instead of exponential work on branching waiting paths, fewer auxiliary states on repeated-wait and shared-suffix families, and a 1.3–8× target on waiting-heavy inputs with lower peak memory. This complements the epsilon filter (#812): the filter removes equivalent schedules, and interning removes identical remaining configurations and paths.

  • Randomized relation equivalence against the current composer and compose_general() is mandatory.
  • ε-free and simple cases stay within 3% median unless output building itself improves them.
  • Record expansions per configuration (at most one), the cache hit rate and the auxiliary states.

Related: #753 (const SymbolPost& + std::move copy and try_emplace in the same lambdas), #743 (TwoDimensionalMap also stores waiting-state ids during composition).

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