Repository navigation
Description
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_storagemaps a running-side state to its waiting state and is cleared at the start of everymodel_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 incopy_transition(), L876-L886 inmodel_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
- Make the waiting context an explicit
WaitingKeywith 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. - Add
intern_waiting(key)returning{state, inserted}and push to the waiting worklist only wheninserted. Assert in Debug builds that no configuration is expanded twice. This alone removes the exponential case. - 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. - Turn the entries of both worklists into complete keys or stable configuration ids instead of bare state pairs.
- 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. - 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.
- Instrument waiting-cache hits and misses, worklist pushes and expansions, auxiliary states created per reason, and duplicate edge attempts.
- 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.
- Introduce the typed keys and hashes with equality tests. Use small enums and fixed-width fields, and measure the key size.
- Replace worklist insertion with discover-once semantics and assert that an expanded configuration is never expanded again.
- 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.
- Add suffix sharing behind an internal switch. Test the crossover counterexample before enabling it.
- 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).
Activity
nft: +fix Expand each waiting state of fast composition once
nft: +fix Expand each waiting state of fast composition once
nft: +fix Expand each waiting state of fast composition once
nft: +fix Expand each waiting state of fast composition once (#930)