[PR] fix(stream): replace O(n) finalization scan with O(1) counter in afterStageHasRun [pekko]

["He-Pin (via GitHub)" <gi...@apache.org>]

He-Pin opened a new pull request, #3373:
URL: https://github.com/apache/pekko/pull/3373

   ### Motivation
   
   PR #3030 (commit 3fbb1848f3) introduced `releaseStage()` which nulls out connection references during stage finalization. The `afterStageHasRun` method was changed to scan all `initializedStages` on every event dispatch to find completed stages. With 1M+ stages (`InterpreterStressSpec`), this causes O(n²) behavior — the test thread hangs indefinitely at `GraphInterpreter.afterStageHasRun` (issue #3372).
   
   ### Modification
   
   Replace the `pendingFinalization` Boolean with a `pendingFinalizations` Int counter:
   
   - **O(1) fast path**: finalizes the active stage directly and decrements the counter by 1
   - **O(n) scan loop**: only runs when the counter is still > 0 after the fast path (cascading completion where multiple stages completed during one event dispatch)
   
   A Boolean cannot distinguish "one stage pending" from "multiple stages pending" — the fast path would erase signals for other stages, breaking cascading finalization (verified by `GraphInterpreterSpec` "release references after cascading stage completion").
   
   ### Result
   
   `afterStageHasRun` is O(1) in the common case (long chains where each event completes exactly one stage). The O(n) scan only runs for cascading completions (rare in practice). `InterpreterStressSpec` with 1M stages completes in bounded time instead of hanging.
   
   ### Tests
   
   - `sbt "stream-tests / Test / testOnly org.apache.pekko.stream.impl.fusing.GraphInterpreterSpec"` — 14/14 passed
   - `sbt "stream-tests / Test / testOnly org.apache.pekko.stream.impl.fusing.GraphInterpreterPortsSpec org.apache.pekko.stream.impl.fusing.LifecycleInterpreterSpec"` — 75/75 passed
   - `sbt "stream / scalafmt"` — no formatting changes needed
   - `InterpreterStressSpec` LongRunningTest-tagged tests not run locally (1M chain × 100 repetitions takes too long on dev machine); CI will verify
   
   ### References
   
   Fixes #3372


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org

Re: [PR] fix(stream): replace O(n) finalization scan with O(1) counter in afterStageHasRun [pekko]

["He-Pin (via GitHub)" <gi...@apache.org>]

He-Pin merged PR #3373:
URL: https://github.com/apache/pekko/pull/3373


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org