Skip to content

fix: non-deterministic chunk generation#8882

Merged
graphite-app[bot] merged 1 commit intomainfrom
03-24-fix_non-deterministic_chunk_generation
Mar 24, 2026
Merged

fix: non-deterministic chunk generation#8882
graphite-app[bot] merged 1 commit intomainfrom
03-24-fix_non-deterministic_chunk_generation

Conversation

@sapphi-red
Copy link
Copy Markdown
Member

@sapphi-red sapphi-red commented Mar 24, 2026

I told claude to investigate the reason of #8834 (comment) and it suggested this change.

Details
Root Cause Analysis: Non-deterministic /* empty css */ placement

The Observed Problem

The /* empty css */ comment (which replaces imports to pure CSS chunks) appears in the entry chunk on local (Windows) but in the non-entry chunk on CI (Linux). This means the cross-chunk import for the CSS chunk is assigned to different chunks across platforms.    

Primary Root Cause: FxHashMap iteration order in Rolldown's chunk optimizer

There are three interacting sources of non-determinism in Rolldown, all involving FxHashMap / FxHashSet iteration where order matters:

1. chunk_optimizer.rs:98 — Non-deterministic bits_to_chunk_idx ordering

// crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs:98
bits_to_chunk_idx: bits_to_chunk_idx.iter().map(|(k, v)| (k.clone(), *v)).collect(),

An FxHashMap<BitSet, ChunkIdx> is iterated and collected into an FxIndexMap. Since FxHashMap iteration order is unspecified, the resulting FxIndexMap preserves a platform-dependent insertion order.

2. chunk_optimizer.rs:344-400 — Stateful sequential assignment with non-deterministic input

// Line 344-366: First pass collects assignments in non-deterministic order
let assignments: Vec<_> = temp_chunk_graph.bits_to_chunk_idx.iter()
    .filter_map(|(bits, temp_chunk_idx)| { ... })
    .collect();

// Line 368-400: Second pass applies assignments SEQUENTIALLY
for (bits, temp_chunk_idx, chunk_idxs, merge_target) in assignments {
    // Circular dependency check depends on PREVIOUS merges
    let merge_target = match merge_target {
        Some(target) if temp_chunk_graph.would_create_circular_dependency(...) => None,
        other => other,
    };
    // merge_chunk_dependencies MODIFIES state for subsequent iterations
    temp_chunk_graph.merge_chunk_dependencies(target_chunk_idx, temp_chunk_idx);
}

The first pass iterates the non-deterministically-ordered FxIndexMap. The second pass applies assignments sequentially, where each merge modifies the dependency graph (merge_chunk_dependencies), affecting circular dependency checks for later iterations. Different  
iteration orders → different merge decisions → different chunk structures.

3. compute_cross_chunk_links.rs:262-264 — Non-deterministic symbol ordering

// crates/rolldown/src/stages/generate_stage/compute_cross_chunk_links.rs:262
for export_ref in entry_meta.resolved_exports.values()  // FxHashMap iteration!
    .filter(|resolved_export| !resolved_export.came_from_cjs)
{
    depended_symbols.insert(symbols.canonical_ref_resolving_namespace(export_ref.symbol_ref));
}

resolved_exports is an FxHashMap. Its iteration order feeds into depended_symbols (FxIndexSet), which maintains insertion order. This non-deterministic ordering affects which symbols are processed first when computing cross-chunk imports (line 429).

Why It Differs Between Local and CI

FxHasher is deterministic for the same key bytes, but the HashMap's bucket layout depends on the hash values and the capacity/resize patterns. On Windows vs Linux:
- Module indices (ModuleIdx) may be assigned in slightly different order due to platform-specific path normalization or parallel module resolution
- This causes BitSet keys to have different bit patterns → different hash values → different bucket assignments → different iteration order
- This cascades through the chunk optimizer, causing different merge decisions

Recommended Fix (in Rolldown)

Fix 1 — Sort bits_to_chunk_idx deterministically before processing (chunk_optimizer.rs:344):
let mut assignments: Vec<_> = temp_chunk_graph.bits_to_chunk_idx.iter()
    .filter_map(...)
    .collect();
assignments.sort_by_key(|(bits, _, _, _)| bits.clone()); // deterministic sort

Fix 2 — Sort resolved_exports before iterating (compute_cross_chunk_links.rs:262):
for export_ref in entry_meta.resolved_exports.iter()
    .sorted_by_key(|(name, _)| name.clone())  // sort by export name
    .map(|(_, v)| v)
    .filter(...)

Fix 3 — Add secondary sort key in Modules::from() (output_chunk.rs:42):
kvs.sort_by(|a, b| {
    a.1.exec_order.cmp(&b.1.exec_order)
        .then_with(|| a.0.cmp(&b.0))  // secondary sort by module ID
});

The most impactful fix is Fix 1, as it directly controls how common chunks are merged or created, which determines the overall chunk structure.

While this didn't fix the output for #8834 (comment), I think the fix itself makes sense.

Copy link
Copy Markdown
Member Author


How to use the Graphite Merge Queue

Add 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.

@netlify
Copy link
Copy Markdown

netlify bot commented Mar 24, 2026

Deploy Preview for rolldown-rs canceled.

Name Link
🔨 Latest commit efad975
🔍 Latest deploy log https://app.netlify.com/projects/rolldown-rs/deploys/69c2093cc9b08600088552d6

@sapphi-red sapphi-red marked this pull request as ready for review March 24, 2026 03:28
@codspeed-hq
Copy link
Copy Markdown

codspeed-hq bot commented Mar 24, 2026

Merging this PR will not alter performance

✅ 4 untouched benchmarks
⏩ 10 skipped benchmarks1


Comparing 03-24-fix_non-deterministic_chunk_generation (b32f646) with main (53e0b0a)2

Open in CodSpeed

Footnotes

  1. 10 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports.

  2. No successful run was found on main (c92c356) during the generation of this report, so 53e0b0a was used instead as the comparison base. There might be some changes unrelated to this pull request in this report.

Copy link
Copy Markdown
Member Author

sapphi-red commented Mar 24, 2026

Merge activity

  • Mar 24, 3:46 AM UTC: The merge label 'graphite: merge-when-ready' was detected. This PR will be added to the Graphite merge queue once it meets the requirements.
  • Mar 24, 3:46 AM UTC: sapphi-red added this pull request to the Graphite merge queue.
  • Mar 24, 3:51 AM UTC: Merged by the Graphite merge queue.

I told claude to investigate the reason of #8834 (comment) and it suggested this change.

<details>

```
Root Cause Analysis: Non-deterministic /* empty css */ placement

The Observed Problem

The /* empty css */ comment (which replaces imports to pure CSS chunks) appears in the entry chunk on local (Windows) but in the non-entry chunk on CI (Linux). This means the cross-chunk import for the CSS chunk is assigned to different chunks across platforms.

Primary Root Cause: FxHashMap iteration order in Rolldown's chunk optimizer

There are three interacting sources of non-determinism in Rolldown, all involving FxHashMap / FxHashSet iteration where order matters:

1. chunk_optimizer.rs:98 — Non-deterministic bits_to_chunk_idx ordering

// crates/rolldown/src/stages/generate_stage/chunk_optimizer.rs:98
bits_to_chunk_idx: bits_to_chunk_idx.iter().map(|(k, v)| (k.clone(), *v)).collect(),

An FxHashMap<BitSet, ChunkIdx> is iterated and collected into an FxIndexMap. Since FxHashMap iteration order is unspecified, the resulting FxIndexMap preserves a platform-dependent insertion order.

2. chunk_optimizer.rs:344-400 — Stateful sequential assignment with non-deterministic input

// Line 344-366: First pass collects assignments in non-deterministic order
let assignments: Vec<_> = temp_chunk_graph.bits_to_chunk_idx.iter()
    .filter_map(|(bits, temp_chunk_idx)| { ... })
    .collect();

// Line 368-400: Second pass applies assignments SEQUENTIALLY
for (bits, temp_chunk_idx, chunk_idxs, merge_target) in assignments {
    // Circular dependency check depends on PREVIOUS merges
    let merge_target = match merge_target {
        Some(target) if temp_chunk_graph.would_create_circular_dependency(...) => None,
        other => other,
    };
    // merge_chunk_dependencies MODIFIES state for subsequent iterations
    temp_chunk_graph.merge_chunk_dependencies(target_chunk_idx, temp_chunk_idx);
}

The first pass iterates the non-deterministically-ordered FxIndexMap. The second pass applies assignments sequentially, where each merge modifies the dependency graph (merge_chunk_dependencies), affecting circular dependency checks for later iterations. Different
iteration orders → different merge decisions → different chunk structures.

3. compute_cross_chunk_links.rs:262-264 — Non-deterministic symbol ordering

// crates/rolldown/src/stages/generate_stage/compute_cross_chunk_links.rs:262
for export_ref in entry_meta.resolved_exports.values()  // FxHashMap iteration!
    .filter(|resolved_export| !resolved_export.came_from_cjs)
{
    depended_symbols.insert(symbols.canonical_ref_resolving_namespace(export_ref.symbol_ref));
}

resolved_exports is an FxHashMap. Its iteration order feeds into depended_symbols (FxIndexSet), which maintains insertion order. This non-deterministic ordering affects which symbols are processed first when computing cross-chunk imports (line 429).

Why It Differs Between Local and CI

FxHasher is deterministic for the same key bytes, but the HashMap's bucket layout depends on the hash values and the capacity/resize patterns. On Windows vs Linux:
- Module indices (ModuleIdx) may be assigned in slightly different order due to platform-specific path normalization or parallel module resolution
- This causes BitSet keys to have different bit patterns → different hash values → different bucket assignments → different iteration order
- This cascades through the chunk optimizer, causing different merge decisions

Recommended Fix (in Rolldown)

Fix 1 — Sort bits_to_chunk_idx deterministically before processing (chunk_optimizer.rs:344):
let mut assignments: Vec<_> = temp_chunk_graph.bits_to_chunk_idx.iter()
    .filter_map(...)
    .collect();
assignments.sort_by_key(|(bits, _, _, _)| bits.clone()); // deterministic sort

Fix 2 — Sort resolved_exports before iterating (compute_cross_chunk_links.rs:262):
for export_ref in entry_meta.resolved_exports.iter()
    .sorted_by_key(|(name, _)| name.clone())  // sort by export name
    .map(|(_, v)| v)
    .filter(...)

Fix 3 — Add secondary sort key in Modules::from() (output_chunk.rs:42):
kvs.sort_by(|a, b| {
    a.1.exec_order.cmp(&b.1.exec_order)
        .then_with(|| a.0.cmp(&b.0))  // secondary sort by module ID
});

The most impactful fix is Fix 1, as it directly controls how common chunks are merged or created, which determines the overall chunk structure.
```

</details>

While this didn't fix the output for #8834 (comment), I think the fix itself makes sense.
@graphite-app graphite-app bot force-pushed the 03-24-fix_non-deterministic_chunk_generation branch from b32f646 to efad975 Compare March 24, 2026 03:47
@graphite-app graphite-app bot merged commit efad975 into main Mar 24, 2026
30 of 31 checks passed
@graphite-app graphite-app bot deleted the 03-24-fix_non-deterministic_chunk_generation branch March 24, 2026 03:51
This was referenced Mar 25, 2026
shulaoda added a commit that referenced this pull request Mar 25, 2026
## [1.0.0-rc.12] - 2026-03-25

### 🚀 Features

- chunk-optimizer: skip circular dependency check when strict execution order is enabled (#8886) by @hyf0

### 🐛 Bug Fixes

- emit build warnings during watch mode rebuilds (#8897) by @IWANABETHATGUY
- lazy-barrel: load import-then-export specifiers when barrel has local exports (#8895) by @shulaoda
- correct execution order of transferred CJS init calls (#8877) by @IWANABETHATGUY
- mcs: `entriesAware` should calculate sizes without duplication (#8887) by @hyf0
- non-deterministic chunk generation (#8882) by @sapphi-red
- `is_top_level` incorrectly treats strict-mode scopes as top-level (#8878) by @Dunqing

### 🚜 Refactor

- treeshake: migrate SideEffectDetector to Oxc's MayHaveSideEffects trait (#8624) by @Dunqing

### 🧪 Testing

- make dev server tests deterministic by replacing fixed sleeps with event-driven polling (#8561) by @Boshen

### ⚙️ Miscellaneous Tasks

- deps: update dependency vite-plus to v0.1.14 (#8902) by @camc314
- deps: update dependency oxfmt to ^0.42.0 (#8891) by @renovate[bot]
- deps: update rust crate oxc_sourcemap to v6.1.1 (#8890) by @renovate[bot]
- remove Rolldown MF plan (#8883) by @shulaoda
- deps: update rollup submodule for tests to v4.60.0 (#8881) by @sapphi-red
- deps: update test262 submodule for tests (#8880) by @sapphi-red
- deps: upgrade oxc crates to 0.122.0 (#8879) by @shulaoda

Co-authored-by: shulaoda <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants