perf: binary-search lookup_token by dst_col only#385
Merged
Conversation
The `lookup_table` group only measured `generate_lookup_table` (table construction). Add a `lookup_token` group that, with the table already built, probes every token's generated position — the per-token remapping pattern bundlers use when collapsing a sourcemap chain.
Every token in `lookup_table[line]` has `dst_line == line` (see `generate_lookup_table`), so binary-searching the `(dst_line, dst_col)` tuple compares a constant first component on every probe. Searching `dst_col` alone is equivalent and measurably faster on this remapping hot path, which dominates sourcemap-chain collapse in bundlers. Also marks `lookup_token` `#[inline]` so it inlines into cross-crate callers. Microbench (criterion, in-crate, before -> after): lookup_token/real_small 21.67ns -> 14.00ns (-35%) lookup_token/real_medium 70.25ns -> 36.47ns (-48%) lookup_token/real_large 1.555us -> 0.723us (-54%) lookup_token/real_xlarge 54.06us -> 25.68us (-52%)
Merging this PR will not alter performance
Warning Please fix the performance issues or acknowledge them on CodSpeed. Performance Changes
Tip Investigate this regression by commenting Comparing 
Footnotes
|
Merged
Boshen
added a commit
to hyfdev/oxc-sourcemap
that referenced
this pull request
Jul 2, 2026
…sition test Model the full rolldown/rolldown#10070 pipeline in one integration test: codegen indents a line so its first anchor sits at column 1, the bundler samples the moved line at column 0, and collapsing the chain resolves the bundle token through the codegen map. The strict lookup drops the mapping (asserted); the approximating lookup keeps it. The composed map then round-trips through JSON and resolves the bundle position back to the original source via OwnedSourceMap, covering the delegation as well. Also align the new method's binary search with lookup_token (dst_col-only key, oxc-project#385).
Boshen
added a commit
that referenced
this pull request
Jul 3, 2026
* feat: add lookup_token_approx for lossless sourcemap composition lookup_token returns None when the queried column is before the first token on a line. That's correct for a plain position lookup but drops mappings when composing sourcemaps: an indented line's first token sits after the indent, so a column-0 query misses and the line loses its mapping. Add lookup_token_approx / lookup_source_view_token_approx, which clamp to the line's first token in that case, matching Rollup's collapseSourcemaps traceSegment. lookup_token is unchanged. * test: replace lookup_token_approx unit tests with an end-to-end composition test Model the full rolldown/rolldown#10070 pipeline in one integration test: codegen indents a line so its first anchor sits at column 1, the bundler samples the moved line at column 0, and collapsing the chain resolves the bundle token through the codegen map. The strict lookup drops the mapping (asserted); the approximating lookup keeps it. The composed map then round-trips through JSON and resolves the bundle position back to the original source via OwnedSourceMap, covering the delegation as well. Also align the new method's binary search with lookup_token (dst_col-only key, #385). --------- Co-authored-by: Boshen <[email protected]>
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.
What
SourceMap::lookup_tokenbinary-searches a line's token slice for thegreatest token
<= (line, col). Every token inlookup_table[line]is builtto have
dst_line == line(seegenerate_lookup_table), so searching the full(dst_line, dst_col)tuple compares a component that is constant across theslice on every probe. Searching
dst_colalone is equivalent and avoidsbuilding/comparing a tuple per step.
This is the per-token remapping hot path: bundlers call it once per token, per
chain link, when collapsing a sourcemap chain.
This PR:
dst_colonly inlookup_token;lookup_token#[inline]so it inlines into cross-crate callers;lookup_tokenbenchmark group — the existinglookup_tablegroup onlymeasured
generate_lookup_table(table construction), not the lookups.Results
Microbench (
benches/simple.rs, criterion, before → after):lookup_token/real_smalllookup_token/real_mediumlookup_token/real_largelookup_token/real_xlargeEnd-to-end in rolldown (via a local
[patch.crates-io]),cargo bench -p bench:sourcemap/collapse_codegen_chainsourcemap/join_with_sourcemap(control)sourcemap/join_no_sourcemap(control)The two controls are untouched by this change, confirming the delta is isolated
to the lookup path.
Correctness
dst_lineis invariant withinlookup_table[line], so the tuple anddst_col-only searches are equivalent (including the equal-key run handled bygreatest_lower_bound). All existing tests pass (cargo test), includinglookup_token,lookup_with_duplicate_columns, andlookup_before_first_token;cargo clippy --all-targets --all-featuresis clean.Disclosure: this change was developed with AI assistance (Claude), and reviewed,
benchmarked, and verified by the author before submission.