perf(semantic): replace scope interval tree with pre-order index - #12016
Merged
Merged
Conversation
🦋 Changeset detectedLatest commit: 0c993c8 The changes in this PR will be included in the next version bump. This PR includes changesets to release 13 packages
Not sure what this means? Click here to learn what changesets are. Click here if you're a maintainer who wants to add another changeset to this PR |
github-actions
Bot
added
the
L-JavaScript
Contributor
Parser conformance results onjs/262
jsx/babel
markdown/commonmark
symbols/microsoft
ts/babel
ts/microsoft
yaml/yaml-test-suite
|
Contributor
Author
Merging this PR will regress 1 benchmark
|
| Benchmark | BASE |
HEAD |
Efficiency | |
|---|---|---|---|---|
| ❌ | bench_recursive_alias_member_lookup[path_value] |
751.2 µs | 807.7 µs | -6.99% |
| ⚡ | index_d_ts[astro_server.mjs] |
486.7 ms | 233.9 ms | ×2.1 |
| ⚡ | bench_index_d_ts_salsa_end_to_end[astro_server.mjs] |
589.3 ms | 336.3 ms | +75.25% |
| ⚡ | bench_index_d_ts_salsa_incremental_first_run |
1.6 s | 1 s | +58.91% |
| ⚡ | index_d_ts[RedisCommander.d.ts] |
379 ms | 262.5 ms | +44.42% |
| ⚡ | index_d_ts[@next/font/google/index.d.ts] |
755.2 ms | 537.3 ms | +40.57% |
| ⚡ | bench_index_d_ts_salsa_end_to_end[RedisCommander.d.ts] |
429.4 ms | 312 ms | +37.61% |
| ⚡ | bench_index_d_ts_salsa_end_to_end[@next/font/google/index.d.ts] |
930.8 ms | 715.3 ms | +30.13% |
| ⚡ | bench_normalize_local_alias |
115.4 µs | 94 µs | +22.8% |
| ⚡ | index_d_ts[react/index.d.ts] |
57.2 ms | 53.6 ms | +6.81% |
grit_query_anchor_kinds[code_snippet] |
< 1 ns | < 1 ns | N/A | |
grit_query_anchor_kinds[metavariable] |
< 1 ns | < 1 ns | N/A | |
grit_query_anchor_kinds[or_pattern] |
< 1 ns | < 1 ns | N/A |
Tip
Investigate this regression by commenting @codspeedbot fix this regression on this PR, or directly use the CodSpeed MCP with your agent.
Comparing codspeed/optim-scope-range-index (0c993c8) with main (994e40f)
Footnotes
-
6 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. ↩
ematipico
marked this pull request as ready for review
September 29, 2026 09:10
Member
|
I added a changeset because the savings are real, and users will benefit. |
ematipico
approved these changes
Sep 29, 2026
Merged
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
2 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.
Summary
Replace
rust_lapper::Lapperscope lookups inbiome_js_semanticwith a pre-orderScopeRangeIndex.Scope ranges are properly nested, so the new index sorts entries by start ascending/end descending, de-duplicates identical ranges to preserve the existing behavior, and stores each entry's closest enclosing scope. Lookups use binary search followed by an enclosing-scope walk (
O(log n + depth)instead of scanning all intervals). The builder-side range map and therust-lapperdependency are removed.Validation
cargo test -p biome_js_semanticcargo test -p biome_module_graphcargo test -p biome_js_analyzecargo clippy -p biome_js_semantic --all-targets -- -D warningscargo fmt --all -- --checkAll passed with no tracked snapshot changes.
CodSpeed comparison
Measured with the same local CPU-simulation setup on the
biome_module_graphsuite:6abb7053a300d98d548d85276abb6d5268d563499944dd0The comparison reports 10 improvements, 32 unchanged benchmarks, and no regressions. Highlights include:
index_d_ts[astro_server.mjs]: 151.2 ms → 69.6 ms (×2.2)bench_index_d_ts_salsa_end_to_end[astro_server.mjs]: 184.5 ms → 102.5 ms (+80.0%)bench_index_d_ts_salsa_incremental_first_run: 490.5 ms → 304.9 ms (+60.9%)A walltime run was attempted locally but could not complete: dedicated macro runners are unavailable for this repository owner, and the standard-runner LTO build was stopped before benchmark execution. The validated comparison above is CPU simulation, matching the repository's benchmark workflow mode.