Repository navigation
perf(apps): avoid quadratic scans of compacted session history - #7568
Closed
LingYi-Liang wants to merge 1 commit into
Closed
LingYi-Liang wants to merge 1 commit into
LingYi-Liang wants to merge 1 commit into
Conversation
Use a sorted range sweep and binary search for compacted history, preserving summary and event ordering.
Contributor
There was a problem hiding this comment.
Code Review
This pull request optimizes the compaction range calculation and subsumption checks to avoid O(N^2) all-pairs interval comparisons. It introduces _get_compaction_ranges in compaction.py using sorting, and leverages binary search (bisect_right) in _compaction.py to check if timestamps are compacted. Additionally, new benchmarks and unit tests are added to verify performance scaling and correctness of the interval-query behavior. There are no review comments to address.
copybara-service Bot
pushed a commit
that referenced
this pull request
Oct 16, 2026
Merge #7568 PiperOrigin-RevId: 1000977841
Collaborator
|
Thank you @LingYi-Liang for your contribution! 🎉 Your changes have been successfully imported and merged via Copybara in commit 2a28c3e. Closing this PR as the changes are now in the main branch. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Link to Issue or Description of Change
Problem: Compacted histories still do all-pairs range checks and scan every retained range for each raw event. The cost grows quadratically with session history.
Solution: Sweep sorted ranges to keep non-subsumed summaries, then use binary search for raw-event coverage. Keep the existing overlap, tie and event-order semantics.
In a local CPU fixture with 1,024 summaries and 8,193 raw events, request-content assembly drops from 122 ms to 26 ms with identical output. This measures preprocessing, not model inference.
Testing Plan
Tests and reproduction
Windows, Python 3.12.14; base
f78149a.pytest -q tests/unittests/apps tests/unittests/flows/llm_flows/context # 294 passed, 1 xfailed (existing app-name validation case) python tests/benchmarks/benchmark_compaction.py --output result.jsonTwo comparison-count regressions fail on the base and pass here, without wall-clock assertions. Also checked 300 deterministic randomized histories against the direct containment/coverage rules.
Same fixture and environment, one warmup then five samples per case; median
_get_contentstime in milliseconds:The benchmark emits all samples and output hashes. Copy the same script to a base checkout for comparison; all three output hashes match. These are synthetic CPU timings, not production latency or throughput claims.
The existing Runner/SQLite/rewind E2E cases are included in the pytest command. A separate Runner probe loaded 128 summaries through InMemorySessionService and used the existing MockModel; both versions retained every summary, removed covered raw events, produced
done, and sent identical request contents. No network model call was made. Scoped formatting, spelling, compliance and documentation-link checks pass. Full-repository and Linux tests were not run.Checklist