perf(rolldown): use unstable sort for itertools sorted_by at unique-key sites#9827
Merged
Merged
Conversation
✅ Deploy Preview for rolldown-rs canceled.
|
Merging this PR will not alter performance
Comparing 
Footnotes
|
IWANABETHATGUY
approved these changes
Jun 17, 2026
Member
Author
Merge activity
|
shulaoda
approved these changes
Jun 17, 2026
f22dae7 to
d7a2e7f
Compare
…ey sites (#9827) Use the **unstable** itertools sort (`sorted_unstable_by`/`sorted_unstable_by_key`) instead of the stable one at sites where the sort key is **unique**, so stability buys nothing. Stable sort only differs from unstable in the relative order of *equal* elements — and at these sites no two elements compare equal, so the output is identical. Unstable sort is also marginally faster (no scratch allocation, smaller routine). This mirrors how the std slice sorts are already used. ## Flipped (key is unique ⇒ output unchanged) - `generate_stage/manual_code_splitting.rs` — by `stable_id` (unique) - `generate_stage/compute_cross_chunk_links.rs` (×3) — by chunk `exec_order` (the unique `chunk.exec_order = i` index), external-module map entries by `exec_order`, and by export `name` (unique map key) - `generate_stage/code_splitting.rs` — the `(group, chunk-index / chunk exec_order)` tuple key (unique across all chunks) ## Left stable (on purpose) - `compute_cross_chunk_links` cjs-namespace sort by `owner.exec_order()` — multiple ns bindings can share an owner (→ equal keys), and the surrounding logic relies on the relative order ("first reference"). - `code_splitting.rs` chunk comparator (`:194`) — its same-kind branches return `Equal` when two chunks' representative **module** `exec_order`s tie. Assigned `exec_order`s are unique (`sort_modules.rs` monotonic counter), but unvisited modules keep the `u32::MAX` sentinel; the cross-kind `if a == b { a_should_be_first }` tiebreaks and the trailing comment *"other chunks has stable order at per entry chunk level"* show the code relies on stable ordering to break those ties deterministically. (Reverted from an earlier revision of this PR after review.) ## Verification The full bundler-output integration/snapshot suite passes with **no snapshot changes** (the only failures in an isolated worktree are pre-existing environment issues — a missing `node_modules` package and the `test262` submodule — which fail identically on `main`). `cargo clippy` (with `--features experimental`) and `cargo fmt` are clean.
d7a2e7f to
ea204dc
Compare
shulaoda
added a commit
that referenced
this pull request
Jun 18, 2026
## [1.1.2] - 2026-06-18 ### 📝 Notable tsconfig behavior changes These ship via the `oxc_resolver` 11.21.3 bump (#9841) and affect `resolve.tsconfigPaths` (Vite 8 resolves through oxc-resolver): - **Honor explicit non-TS extensions in `include`** (oxc-project/oxc-resolver#1213). `compilerOptions.paths` now resolve for importers whose extension is explicitly listed in a tsconfig's `include` (e.g. `src/**/*.vue`, `src/**/*.svelte`). Previously oxc-resolver filtered importers by extension before evaluating the `include` globs, so a `.vue`/`.svelte` file listed in `include` never matched its project and its `paths` were skipped. This unblocks the default create-vite Vue + TS layout (a solution-style root plus a referenced `tsconfig.app.json` that declares `paths` and `include: ["src/**/*.ts", "src/**/*.vue"]`). Matches vue-tsc and svelte-check, which register these extensions via TypeScript's `extraFileExtensions`. - **No fallback to the outermost tsconfig in auto-discovery** (oxc-project/oxc-resolver#1220). Auto-discovery no longer attaches the topmost ancestor `tsconfig.json` to a file that no project actually owns (via `files` / `include` / project references). Previously such a file inherited the outermost ancestor's `paths` / `baseUrl`, leaking aliases into files that project does not own. oxc-resolver now returns no config in that case, matching tsserver / typescript-go, which route such files to an inferred project with no aliases. ### 🚀 Features - add option named for invalid return type errors for more places (#9846) by @shulaoda - add option names for invalid return type errors (#9821) by @sapphi-red - transform: infer decorator strictNullChecks from tsconfig (#9590) by @kylecannon - expose React Compiler options for rolldown and Vite users (#9801) by @Boshen - tracing: gate chrome-json trace layer behind `chrome-tracing` feature (#9773) by @hyf0 - dev: align test-dev-server with Vite dev server (#9668) by @h-a-n-a ### 🐛 Bug Fixes - plugin_timings: point doc link to existing checks reference page (#9837) by @hyf0 - generator: correct contradictory panic message in cjs cross-chunk symbol lookup (#9836) by @hyf0 - esm: preserve with clause on export * from external (#9796) by @hyf0 - Make external_import_binding_merger deterministic (#9755) by @naruaway - surface invalid `manualCodeSplitting` group `test` regex as an error (#9792) by @shulaoda - avoid panic on `output.file` without a file name (#9789) by @shulaoda - avoid O(N^2) rendering of high-volume diagnostics (#9748) (#9749) by @IWANABETHATGUY - avoid panic on JSON numbers outside f64 range (#9788) by @shulaoda - deps: bump mimalloc-safe to 0.1.63 to fix worker_threads segfault (#9785) by @shulaoda - cache ESM evaluation errors (#9784) by @sapphi-red - wrap node require helper in pure IIFE (#9783) by @kb019 - lazy-barrel: load locally-used imports on a re-exported record (#9757) by @shulaoda - avoid dangling wrapped-ESM init call across chunks (#9502) (#9717) by @IWANABETHATGUY - dev: detect same-second rewrites in CI poll watcher (#9736) by @h-a-n-a - dev: force rebuild after HMR errors (#9686) by @h-a-n-a - dev: print build errors on browser refresh after a failed build (#9652) by @h-a-n-a ### 🚜 Refactor - single-source the chunk $N symbol-naming algorithm (#9831) by @Dunqing - simplify common_dir helper (#9857) by @IWANABETHATGUY - drop commondir crate in favor of in-house helper (#9849) by @Boshen - binding: extract helpers from normalize_binding_options (#9842) by @Boshen - move rolldown_filter_analyzer to tasks and scope oxc cfg feature (#9839) by @Boshen - options: merge manualCodeSplitting into codeSplitting object form (#9805) by @IWANABETHATGUY - options: support codeSplitting object form in CodeSplittingMode (#9804) by @IWANABETHATGUY - diagnostic: reuse ByteLocator for per-source line lookup (#9762) by @IWANABETHATGUY - remove redundant Arc around tracing spans (#9778) by @camc314 - remove unnecessary `Arc` around sourcemap sender (#9777) by @camc314 - rolldown_plugin_vite_wasm_fallback: remove the plugin (#9775) by @sapphi-red - binding: remove infer-able `napi(ts_type)` (#9737) by @sapphi-red - remove preprocessor span dedup (#9734) by @hyf0 - identify AST nodes by NodeId instead of Span/Address (#9609) by @IWANABETHATGUY ### 📚 Documentation - tsconfig: align auto-discovery docs with oxc-resolver behavior (#9845) by @shulaoda - relocate meta/design to internal-docs, split design from implementation (#9826) by @h-a-n-a - meta: add options normalization design doc (#9818) by @IWANABETHATGUY - document why the napi tracing feature is enabled (#9766) by @Boshen - dev: move test-dev-server test guidance into the testing docs (#9809) by @h-a-n-a ### ⚡ Performance - drop unused regex unicode property tables from the binding (#9848) by @Boshen - drop urlencoding crate in favor of percent-encoding (#9851) by @Boshen - drop owo-colors supports-colors feature in vite reporter (#9824) by @Boshen - skip enum member value extraction for non-TypeScript modules (#9840) by @shulaoda - rolldown: use unstable sort for itertools sorted_by at unique-key sites (#9827) by @Boshen - cheaper deterministic ordering in external import binding merger (#9810) by @IWANABETHATGUY - disable idna's ICU backend by pinning idna_adapter to 1.0.0 (-129 KB) (#9811) by @Boshen - size: use unstable sort where stability is unneeded (#9803) by @Boshen - remove num-format dependency from vite reporter (#9795) by @Boshen - reduce js callback error size (#9776) by @Boshen - rolldown_error: remove Debug supertrait from BuildEvent (#9798) by @Boshen - reduce plugin hook order code size (#9761) by @Boshen - deps: disable `infer` default features to reduce binary size (#9765) by @Boshen - reduce pluginable monomorphization size (#9771) by @Boshen - avoid rebuilding replace plugin values (#9764) by @Boshen - defer link-stage-output drop to rayon workers after output is produced (#9733) by @Brooooooklyn - tree-shaking: hoist already-included guard to call sites in inclusion DFS (#9738) by @Brooooooklyn - renamer: dedup before allocating the owned name in add_symbol_in_root_scope (#9740) by @Brooooooklyn ### 🧪 Testing - allocs: track allocation counts for rolldown_sourcemap (#9835) by @hyf0 - bench: add CodSpeed micro-benchmarks for rolldown_sourcemap (#9834) by @hyf0 - add cjs named export mutation test (#9823) by @sapphi-red - dev: restore shared-page reliability conventions in AGENTS.md (#9786) by @h-a-n-a - dev: add `AGENTS.md` test guidance for agents (#9763) by @h-a-n-a - dev: split out initial-build-error into its own playground (#9772) by @h-a-n-a - dev: align e2e suite with Vite and parallelize playgrounds (#9759) by @h-a-n-a - remove unnecessary module namespace object JSON serializations in tests (#9725) by @sapphi-red - use `assert.deepStrictEqual` instead of `assert.deepEqual` by using `assert/strict` instead of `assert` (#9724) by @sapphi-red - hmr: add test case for #5301 (#5302) by @sapphi-red - dev: add tests for dev-engine principles (#9720) by @h-a-n-a - dev: align dev-engine test harness with Vite (#9684) by @h-a-n-a ### ⚙️ Miscellaneous Tasks - deps: update napi to 3.9.3 (#9862) by @shulaoda - deps: update oxc to 0.137.0 (#9856) by @Boshen - re-enable default lld linker on x86_64-unknown-linux-gnu (#9855) by @Boshen - deps: bump vite-plus to 0.2.1 (#9850) by @Boshen - skills: translate _config.json when encoding rolldown REPL links (#9847) by @IWANABETHATGUY - deps: update oxc_resolver and oxc_resolver_napi to 11.21.3 (#9841) by @Boshen - pin vite-plus (vp) CLI to 0.1.24 in setup-vp (#9830) by @Boshen - add crate/package-level CODEOWNERS (#9819) by @IWANABETHATGUY - drop unused derive_more display feature from rolldown_plugin (#9820) by @Boshen - remove auto-assign PR workflow (#9807) by @IWANABETHATGUY - deps: update rollup submodule for tests to v4.62.0 (#9780) by @rolldown-guard[bot] - deps: update esbuild for tests to 0.28.1 (#9779) by @rolldown-guard[bot] - deps: update test262 submodule for tests (#9781) by @rolldown-guard[bot] - deps: update oxc to 0.136.0 (#9770) by @Boshen - add pull request template (#9756) by @sapphi-red - clarify `rolldown_plugin_vite_*` is compatible for the same minor (#9774) by @sapphi-red - deps: update github actions (#9745) by @renovate[bot] - deps: update rust crates (#9747) by @renovate[bot] - deps: update napi to v3.9.2 (#9744) by @renovate[bot] - deps: update npm packages (#9746) by @renovate[bot] - deps: update @napi-rs/cli and emnapi deps (#9741) by @Brooooooklyn - generator: fix `vp fmt` on Windows (#9727) by @sapphi-red - ban importing from `assert` and recommend `assert/strict` (#9726) by @sapphi-red ### ❤️ New Contributors * @naruaway made their first contribution in [#9755](#9755) * @kb019 made their first contribution in [#9783](#9783) Co-authored-by: shulaoda <165626830+shulaoda@users.noreply.github.com>
leegeunhyeok
added a commit
to rollipop-dev/rolldown
that referenced
this pull request
Jun 18, 2026
## [1.0.16] - 2026-06-18 ### 🚀 Features - add option named for invalid return type errors for more places (rolldown#9846) by `@shulaoda` - add option names for invalid return type errors (rolldown#9821) by `@sapphi-red` - transform: infer decorator strictNullChecks from tsconfig (rolldown#9590) by `@kylecannon` - expose React Compiler options for rolldown and Vite users (rolldown#9801) by `@Boshen` - tracing: gate chrome-json trace layer behind `chrome-tracing` feature (rolldown#9773) by `@hyf0` - dev: align test-dev-server with Vite dev server (rolldown#9668) by `@h-a-n-a` ### 🐛 Bug Fixes - plugin_timings: point doc link to existing checks reference page (rolldown#9837) by `@hyf0` - generator: correct contradictory panic message in cjs cross-chunk symbol lookup (rolldown#9836) by `@hyf0` - esm: preserve with clause on export * from external (rolldown#9796) by `@hyf0` - Make external_import_binding_merger deterministic (rolldown#9755) by `@naruaway` - surface invalid `manualCodeSplitting` group `test` regex as an error (rolldown#9792) by `@shulaoda` - avoid panic on `output.file` without a file name (rolldown#9789) by `@shulaoda` - avoid O(N^2) rendering of high-volume diagnostics (rolldown#9748) (rolldown#9749) by `@IWANABETHATGUY` - avoid panic on JSON numbers outside f64 range (rolldown#9788) by `@shulaoda` - deps: bump mimalloc-safe to 0.1.63 to fix worker_threads segfault (rolldown#9785) by `@shulaoda` - cache ESM evaluation errors (rolldown#9784) by `@sapphi-red` - wrap node require helper in pure IIFE (rolldown#9783) by `@kb019` - lazy-barrel: load locally-used imports on a re-exported record (rolldown#9757) by `@shulaoda` - avoid dangling wrapped-ESM init call across chunks (rolldown#9502) (rolldown#9717) by `@IWANABETHATGUY` - dev: detect same-second rewrites in CI poll watcher (rolldown#9736) by `@h-a-n-a` - dev: force rebuild after HMR errors (rolldown#9686) by `@h-a-n-a` - dev: print build errors on browser refresh after a failed build (rolldown#9652) by `@h-a-n-a` ### 🚜 Refactor - single-source the chunk $N symbol-naming algorithm (rolldown#9831) by `@Dunqing` - simplify common_dir helper (rolldown#9857) by `@IWANABETHATGUY` - drop commondir crate in favor of in-house helper (rolldown#9849) by `@Boshen` - binding: extract helpers from normalize_binding_options (rolldown#9842) by `@Boshen` - move rolldown_filter_analyzer to tasks and scope oxc cfg feature (rolldown#9839) by `@Boshen` - options: merge manualCodeSplitting into codeSplitting object form (rolldown#9805) by `@IWANABETHATGUY` - options: support codeSplitting object form in CodeSplittingMode (rolldown#9804) by `@IWANABETHATGUY` - diagnostic: reuse ByteLocator for per-source line lookup (rolldown#9762) by `@IWANABETHATGUY` - remove redundant Arc around tracing spans (rolldown#9778) by `@camc314` - remove unnecessary `Arc` around sourcemap sender (rolldown#9777) by `@camc314` - rolldown_plugin_vite_wasm_fallback: remove the plugin (rolldown#9775) by `@sapphi-red` - binding: remove infer-able `napi(ts_type)` (rolldown#9737) by `@sapphi-red` - remove preprocessor span dedup (rolldown#9734) by `@hyf0` - identify AST nodes by NodeId instead of Span/Address (rolldown#9609) by `@IWANABETHATGUY` ### 📚 Documentation - tsconfig: align auto-discovery docs with oxc-resolver behavior (rolldown#9845) by `@shulaoda` - relocate meta/design to internal-docs, split design from implementation (rolldown#9826) by `@h-a-n-a` - meta: add options normalization design doc (rolldown#9818) by `@IWANABETHATGUY` - document why the napi tracing feature is enabled (rolldown#9766) by `@Boshen` - dev: move test-dev-server test guidance into the testing docs (rolldown#9809) by `@h-a-n-a` ### ⚡ Performance - drop unused regex unicode property tables from the binding (rolldown#9848) by `@Boshen` - drop urlencoding crate in favor of percent-encoding (rolldown#9851) by `@Boshen` - drop owo-colors supports-colors feature in vite reporter (rolldown#9824) by `@Boshen` - skip enum member value extraction for non-TypeScript modules (rolldown#9840) by `@shulaoda` - rolldown: use unstable sort for itertools sorted_by at unique-key sites (rolldown#9827) by `@Boshen` - cheaper deterministic ordering in external import binding merger (rolldown#9810) by `@IWANABETHATGUY` - disable idna's ICU backend by pinning idna_adapter to 1.0.0 (-129 KB) (rolldown#9811) by `@Boshen` - size: use unstable sort where stability is unneeded (rolldown#9803) by `@Boshen` - remove num-format dependency from vite reporter (rolldown#9795) by `@Boshen` - reduce js callback error size (rolldown#9776) by `@Boshen` - rolldown_error: remove Debug supertrait from BuildEvent (rolldown#9798) by `@Boshen` - reduce plugin hook order code size (rolldown#9761) by `@Boshen` - deps: disable `infer` default features to reduce binary size (rolldown#9765) by `@Boshen` - reduce pluginable monomorphization size (rolldown#9771) by `@Boshen` - avoid rebuilding replace plugin values (rolldown#9764) by `@Boshen` - defer link-stage-output drop to rayon workers after output is produced (rolldown#9733) by `@Brooooooklyn` - tree-shaking: hoist already-included guard to call sites in inclusion DFS (rolldown#9738) by `@Brooooooklyn` - renamer: dedup before allocating the owned name in add_symbol_in_root_scope (rolldown#9740) by `@Brooooooklyn` ### 🧪 Testing - allocs: track allocation counts for rolldown_sourcemap (rolldown#9835) by `@hyf0` - bench: add CodSpeed micro-benchmarks for rolldown_sourcemap (rolldown#9834) by `@hyf0` - add cjs named export mutation test (rolldown#9823) by `@sapphi-red` - dev: restore shared-page reliability conventions in AGENTS.md (rolldown#9786) by `@h-a-n-a` - dev: add `AGENTS.md` test guidance for agents (rolldown#9763) by `@h-a-n-a` - dev: split out initial-build-error into its own playground (rolldown#9772) by `@h-a-n-a` - dev: align e2e suite with Vite and parallelize playgrounds (rolldown#9759) by `@h-a-n-a` - remove unnecessary module namespace object JSON serializations in tests (rolldown#9725) by `@sapphi-red` - use `assert.deepStrictEqual` instead of `assert.deepEqual` by using `assert/strict` instead of `assert` (rolldown#9724) by `@sapphi-red` - hmr: add test case for rolldown#5301 (rolldown#5302) by `@sapphi-red` - dev: add tests for dev-engine principles (rolldown#9720) by `@h-a-n-a` - dev: align dev-engine test harness with Vite (rolldown#9684) by `@h-a-n-a` ### ⚙️ Miscellaneous Tasks - add rollipop-integration skill by `@leegeunhyeok` - update esbuild snap diff metrics by `@leegeunhyeok` - sync upstream rolldown v1.1.2 by `@leegeunhyeok` - deps: update napi to 3.9.3 (rolldown#9862) by `@shulaoda` - deps: update oxc to 0.137.0 (rolldown#9856) by `@Boshen` - re-enable default lld linker on x86_64-unknown-linux-gnu (rolldown#9855) by `@Boshen` - deps: bump vite-plus to 0.2.1 (rolldown#9850) by `@Boshen` - skills: translate _config.json when encoding rolldown REPL links (rolldown#9847) by `@IWANABETHATGUY` - deps: update oxc_resolver and oxc_resolver_napi to 11.21.3 (rolldown#9841) by `@Boshen` - pin vite-plus (vp) CLI to 0.1.24 in setup-vp (rolldown#9830) by `@Boshen` - add crate/package-level CODEOWNERS (rolldown#9819) by `@IWANABETHATGUY` - drop unused derive_more display feature from rolldown_plugin (rolldown#9820) by `@Boshen` - remove auto-assign PR workflow (rolldown#9807) by `@IWANABETHATGUY` - deps: update rollup submodule for tests to v4.62.0 (rolldown#9780) by `@rolldown-guard[bot]` - deps: update esbuild for tests to 0.28.1 (rolldown#9779) by `@rolldown-guard[bot]` - deps: update test262 submodule for tests (rolldown#9781) by `@rolldown-guard[bot]` - deps: update oxc to 0.136.0 (rolldown#9770) by `@Boshen` - add pull request template (rolldown#9756) by `@sapphi-red` - clarify `rolldown_plugin_vite_*` is compatible for the same minor (rolldown#9774) by `@sapphi-red` - deps: update github actions (rolldown#9745) by `@renovate[bot]` - deps: update rust crates (rolldown#9747) by `@renovate[bot]` - deps: update napi to v3.9.2 (rolldown#9744) by `@renovate[bot]` - deps: update npm packages (rolldown#9746) by `@renovate[bot]` - deps: update @napi-rs/cli and emnapi deps (rolldown#9741) by `@Brooooooklyn` - generator: fix `vp fmt` on Windows (rolldown#9727) by `@sapphi-red` - ban importing from `assert` and recommend `assert/strict` (rolldown#9726) by `@sapphi-red` Co-authored-by: leegeunhyeok <26512984+leegeunhyeok@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
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.
Use the unstable itertools sort (
sorted_unstable_by/sorted_unstable_by_key) instead of the stable one at sites where the sort key is unique, so stability buys nothing. Stable sort only differs from unstable in the relative order of equal elements — and at these sites no two elements compare equal, so the output is identical. Unstable sort is also marginally faster (no scratch allocation, smaller routine). This mirrors how the std slice sorts are already used.Flipped (key is unique ⇒ output unchanged)
generate_stage/manual_code_splitting.rs— bystable_id(unique)generate_stage/compute_cross_chunk_links.rs(×3) — by chunkexec_order(the uniquechunk.exec_order = iindex), external-module map entries byexec_order, and by exportname(unique map key)generate_stage/code_splitting.rs— the(group, chunk-index / chunk exec_order)tuple key (unique across all chunks)Left stable (on purpose)
compute_cross_chunk_linkscjs-namespace sort byowner.exec_order()— multiple ns bindings can share an owner (→ equal keys), and the surrounding logic relies on the relative order ("first reference").code_splitting.rschunk comparator (:194) — its same-kind branches returnEqualwhen two chunks' representative moduleexec_orders tie. Assignedexec_orders are unique (sort_modules.rsmonotonic counter), but unvisited modules keep theu32::MAXsentinel; the cross-kindif a == b { a_should_be_first }tiebreaks and the trailing comment "other chunks has stable order at per entry chunk level" show the code relies on stable ordering to break those ties deterministically. (Reverted from an earlier revision of this PR after review.)Verification
The full bundler-output integration/snapshot suite passes with no snapshot changes (the only failures in an isolated worktree are pre-existing environment issues — a missing
node_modulespackage and thetest262submodule — which fail identically onmain).cargo clippy(with--features experimental) andcargo fmtare clean.