perf: use flag-based convergence detection in include_statements (#8412)

Brooooooklyn · Brooooooklyn · commit 26d804ee11c9 · 2026-02-22T05:16:17.000Z
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>  --- > [!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>
diff --git a/crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs b/crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs
@@ -906,6 +906,7 @@ impl GenerateStage<'_> {
       normal_symbol_exports_chain_map: &self.link_output.normal_symbol_exports_chain_map,
       bailout_cjs_tree_shaking_modules: FxHashSet::default(),
       may_partial_namespace: false,
+      module_inclusion_changed: false,
       module_namespace_included_reason: &mut module_namespace_reason_vec,
       inline_const_smart: self.options.optimization.is_inline_const_smart_mode(),
       json_module_none_self_reference_included_symbol: FxHashMap::default(),
diff --git a/crates/rolldown/src/stages/link_stage/tree_shaking/include_statements.rs b/crates/rolldown/src/stages/link_stage/tree_shaking/include_statements.rs
@@ -49,6 +49,7 @@ bitflags::bitflags! {
     }
 }
 
+#[expect(clippy::struct_excessive_bools)]
 pub struct IncludeContext<'a> {
   pub modules: &'a IndexModules,
   pub symbols: &'a SymbolRefDb,
@@ -66,6 +67,9 @@ pub struct IncludeContext<'a> {
   /// see [rolldown_common::ecmascript::ecma_view::EcmaViewMeta]
   pub bailout_cjs_tree_shaking_modules: FxHashSet<ModuleIdx>,
   pub may_partial_namespace: bool,
+  /// Tracks whether any new module was included during the current convergence iteration.
+  /// Used to detect fixpoint without O(N) scanning of `is_module_included_vec`.
+  pub module_inclusion_changed: bool,
   pub module_namespace_included_reason: &'a mut ModuleNamespaceReasonVec,
   pub json_module_none_self_reference_included_symbol: FxHashMap<ModuleIdx, FxHashSet<SymbolRef>>,
 }
@@ -100,6 +104,7 @@ impl<'a> IncludeContext<'a> {
       normal_symbol_exports_chain_map,
       bailout_cjs_tree_shaking_modules: FxHashSet::default(),
       may_partial_namespace: false,
+      module_inclusion_changed: false,
       module_namespace_included_reason,
       json_module_none_self_reference_included_symbol: FxHashMap::default(),
     }
@@ -209,10 +214,10 @@ impl LinkStage<'_> {
 
     let mut unused_record_idxs = vec![];
     let cycled_idx = self.sort_dynamic_entries_by_topological_order(&mut dynamic_entries);
-    let mut previous_included_module_count =
-      context.is_module_included_vec.iter().filter(|item| **item).count();
     let mut included_dynamic_entry = FxHashSet::default();
     loop {
+      context.module_inclusion_changed = false;
+
       // It could be safely take since it is no more used.
       // We extract bailout_modules first to avoid borrowing conflict:
       // passing `context` requires a mutable borrow, which conflicts with
@@ -236,14 +241,9 @@ impl LinkStage<'_> {
         }
       });
 
-      let current_included_module_count =
-        context.is_module_included_vec.iter().filter(|item| **item).count();
-
-      if current_included_module_count == previous_included_module_count {
+      if !context.module_inclusion_changed {
         break;
       }
-
-      previous_included_module_count = current_included_module_count;
     }
 
     dynamic_entries.retain(|entry| included_dynamic_entry.contains(&entry.idx));
@@ -578,6 +578,7 @@ pub fn include_module(ctx: &mut IncludeContext, module: &NormalModule) {
   }
 
   ctx.is_module_included_vec[module.idx] = true;
+  ctx.module_inclusion_changed = true;
 
   if module.idx == ctx.runtime_idx && !module.side_effects.has_side_effects() {
     // Unmodified runtime: statements included only via references.
