Repository navigation
perf(core): linearize array reconstruction in truncateHistoryToBudget - #29517
Kaushik2210 wants to merge 1 commit into
Conversation
truncateHistoryToBudget() in chatCompressionService.ts visits messages and their parts newest-to-oldest to prioritize recent tool responses, then restores chronological order via unshift() for every processed part and every reconstructed message. Repeated front-insertion is O(n) per call, so for H messages with P_i parts each this costs O(H^2 + sum(P_i^2)) instead of O(H + sum(P_i)). Append with push() instead and reverse each parts array and the overall history once at the end. The backwards traversal (and all budget/truncation decisions, which are unaffected by how the result array is built) is unchanged. Exported truncateHistoryToBudget for direct testing, matching the existing pattern for this file's other internal helpers (findCompressSplitPoint, collapseOlderFunctionResponses), and added a regression test asserting message and multi-part ordering is preserved when no truncation occurs. Fixes google-gemini#29511
|
📊 PR Size: size/S
|
Summary of ChangesHello, I'm Gemini Code Assist1! I'm currently reviewing this pull request and will post my feedback shortly. In the meantime, here's a summary to help you and other reviewers quickly get up to speed! This pull request improves the performance of the chat history truncation logic by switching from an O(n^2) array reconstruction approach to an O(n) approach. By appending elements and reversing the final arrays, the service avoids the overhead of repeated front-insertions, ensuring more efficient processing of chat history while maintaining identical output behavior. Highlights
Using Gemini Code AssistThe full guide for Gemini Code Assist can be found on our documentation page, here are some quick tips. Invoking Gemini You can request assistance from Gemini at any point by creating a comment using either
Customization To customize the Gemini Code Assist for GitHub experience, repository maintainers can create a configuration file and/or provide a custom code review style guide (such as PEP-8 for Python) by creating and adding files to a Limitations & Feedback Gemini Code Assist may make mistakes. Please leave feedback on any instances where its feedback is incorrect or counterproductive. You can react with 👍 and 👎 on @gemini-code-assist comments. If you're interested in giving your feedback about your experience with Gemini Code Assist for GitHub and other Google products, sign up here. Footnotes
|
![gemini-code-assist[bot]](/web-api/iframe-proxy?url=https://avatars.githubusercontent.com/in/956858?s=60&v=4){kind=small}
There was a problem hiding this comment.
Code Review
This pull request optimizes the truncateHistoryToBudget function in chatCompressionService.ts by replacing inefficient unshift operations with push followed by a single reverse() call, improving performance during array reconstruction. It also exports truncateHistoryToBudget and adds a unit test in chatCompressionService.test.ts to ensure that message and multi-part ordering are correctly preserved. There are no review comments, and I have no additional feedback to provide.
gemini-cli
Bot
added
the
area/agent
|
Hi there! Thank you for your interest in contributing to Gemini CLI. To ensure we maintain high code quality and focus on our prioritized roadmap, we only guarantee review and consideration of pull requests for issues that are explicitly labeled as 'help wanted'. This PR will be closed in 7 days if it remains without that designation. We encourage you to find and contribute to existing 'help wanted' issues in our backlog! Thank you for your understanding. |
This branch has not been deployed
1 participant
Summary
truncateHistoryToBudget()inpackages/core/src/context/chatCompressionService.tsvisits messages and their parts newest-to-oldest (to prioritize recent tool responses against the truncation budget), then restores chronological order by callingunshift()for every processed part and every reconstructed message.Repeated front-insertion into a JS array is
O(n)per call, so forHmessages withP_iparts each, this costsO(H^2 + sum(P_i^2))instead ofO(H + sum(P_i)). This helper runs on the whole curated history before compression splits it, so the overhead applies even to messages that get summarized away afterward.Fix
Append with
push()instead ofunshift(), and reverse each parts array once and the overall history array once at the end. The backwards traversal itself — and every budget/truncation decision, which only depends on processing order, not on how the result array is built — is unchanged.Exported
truncateHistoryToBudgetfor direct unit testing, following this file's existing pattern of exporting internal helpers for tests (findCompressSplitPoint,collapseOlderFunctionResponses).Test plan
describeblock already cover).npm test -w @google/gemini-cli-core -- src/context/chatCompressionService.test.ts— 37/37 pass, including the existing truncation-ordering tests (should truncate older function responses when budget is exceeded, etc.) unchanged.npx eslinton both touched files andnpx tsc --noEmitonpackages/core: clean.Fixes #29511