perf: use flag-based convergence detection in include_statements#8412
Merged
graphite-app[bot] merged 1 commit intomainfrom Feb 22, 2026
Merged
Conversation
Member
Author
How to use the Graphite Merge QueueAdd the label graphite: merge-when-ready to this PR to add it to the merge queue. You must have a Graphite account in order to use the merge queue. Sign up using this link. An organization admin has enabled the Graphite Merge Queue in this repository. Please do not merge from GitHub as this will restart CI on PRs being processed by the merge queue. This stack of pull requests is managed by Graphite. Learn more about stacking. |
✅ Deploy Preview for rolldown-rs canceled.
|
Contributor
There was a problem hiding this comment.
Pull request overview
This PR optimizes the convergence detection in the tree-shaking include_statements algorithm by replacing an O(N) linear scan with a boolean flag. The previous implementation counted included modules on each iteration by scanning the entire is_module_included_vec array (~19K entries in benchmarked project). The new implementation tracks whether any module was newly included during the current iteration via a module_inclusion_changed flag.
Changes:
- Added
module_inclusion_changedboolean flag toIncludeContextstruct to track module inclusion state changes - Modified convergence loop to reset the flag at iteration start and check it for termination instead of counting modules
- Set the flag in
include_module()when a module transitions from not-included to included
Reviewed changes
Copilot reviewed 2 out of 2 changed files in this pull request and generated no comments.
| File | Description |
|---|---|
| crates/rolldown/src/stages/link_stage/tree_shaking/include_statements.rs | Added module_inclusion_changed field to IncludeContext, initialized it in constructor, added flag reset/check in convergence loop, and set flag in include_module() |
| crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs | Initialized new module_inclusion_changed field in IncludeContext struct literal construction |
Contributor
Benchmarks Rust |
IWANABETHATGUY
approved these changes
Feb 22, 2026
Contributor
Merge activity
|
Replace O(N) linear scan of is_module_included_vec per convergence iteration with a boolean flag (module_inclusion_changed) that is set when include_module() transitions a module to included. This avoids scanning ~19K entries on every loop iteration to detect fixpoint. Benchmark (10K module project, 15 runs): - System time: 2.68s -> 2.52s (-5.9%) - Wall clock: 4.42s -> 4.41s (-0.2%) Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com> <!-- CURSOR_SUMMARY --> --- > [!NOTE] > **Low Risk** > Behavior should be unchanged (only alters fixpoint detection), but mistakes could cause premature termination and missed module inclusion in tree-shaking. > > **Overview** > Speeds up tree-shaking convergence in `include_statements` by replacing per-iteration O(N) scans of `is_module_included_vec` with a `module_inclusion_changed` flag that is reset each loop and set when `include_module` newly includes a module. > > Extends `IncludeContext` (and its construction sites, including `chunk_optimizer`) to carry this flag so the dynamic-entry inclusion loop can stop at fixpoint without counting included modules each iteration. > > <sup>Written by [Cursor Bugbot](https://cursor.com/dashboard?tab=bugbot) for commit 50910e2. This will update automatically on new commits. Configure [here](https://cursor.com/dashboard?tab=bugbot).</sup> <!-- /CURSOR_SUMMARY -->
50910e2 to
26d804e
Compare
shulaoda
approved these changes
Feb 22, 2026
This was referenced Feb 25, 2026
Closed
Closed
Merged
shulaoda
added a commit
that referenced
this pull request
Feb 26, 2026
## [1.0.0-rc.6] - 2026-02-26 ### 💥 BREAKING CHANGES - css: remove `css_entry_filenames` , `css_chunk_filenames` and related code (#8402) by @hyf0 - css: drop builtin CSS bundling to explore alternative solutions (#8399) by @hyf0 ### 🚀 Features - rust/data-url: use hash as id for data url modules to prevent long string overhead (#8420) by @hyf0 - validate bundle stays within output dir (#8441) by @sapphi-red - rust: support `PluginOrder::PinPost` (#8417) by @hyf0 - support `ModuleType:Copy` (#8407) by @hyf0 - expose `ESTree` types from `rolldown/utils` (#8400) by @sapphi-red ### 🐛 Bug Fixes - incorrect sourcemap when postBanner/postFooter is used with shebang (#8459) by @Copilot - resolver: disable node_path option to align ESM resolver behavior (#8472) by @sapphi-red - parse `.js` within `"type": "commonjs"` as ESM for now (#8470) by @sapphi-red - case-insensitive filename conflict detection for chunk deduplication (#8458) by @Copilot - prevent inlining CJS exports that are mutated by importers (#8456) by @IWANABETHATGUY - parse `.cjs` / `.cts` / `.js` within `"type": "commonjs"` as CommonJS (#8455) by @sapphi-red - plugin/copy-module: correct hooks' priority (#8423) by @hyf0 - plugin/chunk-import-map: ensure `render_chunk_meta` run after users plugin (#8422) by @hyf0 - rust: correct hooks order of `DataUriPlugin` (#8418) by @hyf0 - `jsx.preserve` should also considering tsconfig json preserve (#8324) by @IWANABETHATGUY - `deferred_scan_data.rs "Should have resolved id: NotFound"` error (#8379) by @sapphi-red - cli: require value for `--dir`/`-d` and `--file`/`-o` (#8378) by @Copilot - dev: avoid mutex deadlock caused by inconsistent lock order (#8370) by @sapphi-red ### 🚜 Refactor - watch: rename TaskStart/TaskEnd to BundleStart/BundleEnd (#8463) by @hyf0 - rust: rename `rolldown_plugin_data_uri` to `rolldown_plugin_data_url` (#8421) by @hyf0 - bindingify-build-hook: extract helper for PluginContextImpl (#8438) by @ShroXd - give source loading a proper name (#8436) by @IWANABETHATGUY - ban holding DashMap refs across awaits (#8362) by @sapphi-red ### 📚 Documentation - add glob pattern usage example to input option (#8469) by @IWANABETHATGUY - remove `https://rolldown.rs` from links in reference docs (#8454) by @sapphi-red - mention execution order issue in `output.codeSplitting` docs (#8452) by @sapphi-red - clarify `output.comments` behavior a bit (#8451) by @sapphi-red - replace npmjs package links with npmx.dev (#8439) by @Boshen - reference: add `Exported from` for values / types exported from subpath exports (#8394) by @sapphi-red - add JSDocs for APIs exposed from subpath exports (#8393) by @sapphi-red - reference: generate reference pages for APIs exposed from subpath exports (#8392) by @sapphi-red - avoid pipe character in codeSplitting example to fix broken rendering (#8391) by @IWANABETHATGUY ### ⚡ Performance - avoid redundant PathBuf allocations in resolve paths (#8435) by @Brooooooklyn - bump to `sugar_path@2` (#8432) by @hyf0 - use flag-based convergence detection in include_statements (#8412) by @Brooooooklyn ### 🧪 Testing - execute `_test.mjs` even if `executeOutput` is false (#8398) by @sapphi-red - add retry to tree-shake/module-side-effects-proxy4 as it is flaky (#8397) by @sapphi-red - avoid `expect.assertions()` as it is not concurrent test friendly (#8383) by @sapphi-red - disable `mockReset` option (#8382) by @sapphi-red - fix flaky failure caused by concurrent resolveId calls (#8381) by @sapphi-red ### ⚙️ Miscellaneous Tasks - deps: update dependency rollup to v4.59.0 [security] (#8471) by @renovate[bot] - ai/design: add design doc about watch mode (#8453) by @hyf0 - deps: update oxc resolver to v11.19.0 (#8461) by @renovate[bot] - ai: introduce progressive spec-driven development pattern (#8446) by @hyf0 - deprecate output.legalComments (#8450) by @sapphi-red - deps: update dependency oxlint-tsgolint to v0.15.0 (#8448) by @renovate[bot] - ai: make CLAUDE.md a symlink of AGENTS.md (#8445) by @hyf0 - deps: update rollup submodule for tests to v4.59.0 (#8433) by @sapphi-red - deps: update test262 submodule for tests (#8434) by @sapphi-red - deps: update oxc to v0.115.0 (#8430) by @renovate[bot] - deps: update oxc apps (#8429) by @renovate[bot] - deps: update npm packages (#8426) by @renovate[bot] - deps: update rust crate owo-colors to v4.3.0 (#8428) by @renovate[bot] - deps: update github-actions (#8424) by @renovate[bot] - deps: update rust crates (#8425) by @renovate[bot] - deps: update oxc resolver to v11.18.0 (#8406) by @renovate[bot] - deps: update dependency oxlint-tsgolint to v0.14.2 (#8405) by @renovate[bot] - ban `expect.assertions` in all fixture tests (#8395) by @sapphi-red - deps: update oxc apps (#8389) by @renovate[bot] - ban `expect.assertions` in fixture tests (#8387) by @sapphi-red - enable lint for `_config.ts` files (#8386) by @sapphi-red - deps: update dependency oxlint-tsgolint to v0.14.1 (#8385) by @renovate[bot] Co-authored-by: shulaoda <165626830+shulaoda@users.noreply.github.com>
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
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.
Replace O(N) linear scan of is_module_included_vec per convergence
iteration with a boolean flag (module_inclusion_changed) that is set
when include_module() transitions a module to included. This avoids
scanning ~19K entries on every loop iteration to detect fixpoint.
Benchmark (10K module project, 15 runs):
Co-Authored-By: Claude Opus 4.6 noreply@anthropic.com
Note
Low Risk
Behavior should be unchanged (only alters fixpoint detection), but mistakes could cause premature termination and missed module inclusion in tree-shaking.
Overview
Speeds up tree-shaking convergence in
include_statementsby replacing per-iteration O(N) scans ofis_module_included_vecwith amodule_inclusion_changedflag that is reset each loop and set wheninclude_modulenewly includes a module.Extends
IncludeContext(and its construction sites, includingchunk_optimizer) to carry this flag so the dynamic-entry inclusion loop can stop at fixpoint without counting included modules each iteration.Written by Cursor Bugbot for commit 50910e2. This will update automatically on new commits. Configure here.