Skip to content

perf(linter/plugins): use >> not >>> in binary search loops#21129

Merged
graphite-app[bot] merged 1 commit intomainfrom
om/04-03-perf_linter_plugins_use_not_in_binary_search_loops
Apr 7, 2026
Merged

perf(linter/plugins): use >> not >>> in binary search loops#21129
graphite-app[bot] merged 1 commit intomainfrom
om/04-03-perf_linter_plugins_use_not_in_binary_search_loops

Conversation

@overlookmotel
Copy link
Copy Markdown
Member

@overlookmotel overlookmotel commented Apr 7, 2026

>> is cheaper than >>> because >> produces a 32-bit signed integer which is V8's native number type (SMI). >>> produces a 32-bit unsigned integer, which needs to be boxed and stored on the heap.

Source text in raw transfer is limited to 1 GiB, and therefore source offsets, number of lines, number of tokens, and number of comments after all less than 1 << 30. Therefore even the sum of 2 of them cannot reach 1 << 31 (the maximum positive integer which can be stored as a positive signed 31-bit int. Therefore it's safe to use >> in these binary loops.

Copy link
Copy Markdown
Member Author

overlookmotel commented Apr 7, 2026


How to use the Graphite Merge Queue

Add either label to this PR to merge it via the merge queue:

  • 0-merge - adds this PR to the back of the merge queue
  • hotfix - for urgent changes, fast-track this PR to the front of 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.

@github-actions github-actions Bot added A-linter Area - Linter A-parser Area - Parser A-cli Area - CLI A-linter-plugins Area - Linter JS plugins C-performance Category - Solution not expected to change functional behavior, only performance labels Apr 7, 2026
@overlookmotel overlookmotel marked this pull request as ready for review April 7, 2026 15:47
@overlookmotel overlookmotel requested a review from camc314 as a code owner April 7, 2026 15:47
Copilot AI review requested due to automatic review settings April 7, 2026 15:47
Copy link
Copy Markdown
Contributor

Copilot AI left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull request overview

This PR updates several binary-search loops in the oxlint JS plugins to use >> 1 instead of >>> 1, based on the assumption that relevant indices/offsets stay within the signed 32-bit (SMI-friendly) range.

Changes:

  • Replace >>> 1 with >> 1 in a few binary-search midpoint calculations.
  • Add explanatory comments documenting why signed right shift is considered safe here.
  • Adjust raw-transfer documentation around SMI/bitwise constraints.

Reviewed changes

Copilot reviewed 4 out of 4 changed files in this pull request and generated 2 comments.

File Description
napi/parser/src/raw_transfer.rs Updates comments describing why the raw-transfer buffer sizing favors SMI/bitwise-friendly offsets.
apps/oxlint/src-js/plugins/tokens_methods.ts Switches midpoint calculation in token binary searches from >>> 1 to >> 1 and adds rationale comments.
apps/oxlint/src-js/plugins/source_code.ts Adds comments asserting source-length invariants intended to justify use of >> elsewhere.
apps/oxlint/src-js/plugins/location.ts Switches midpoint calculation in line/loc binary searches from >>> 1 to >> 1 and adds rationale comments.

Comment thread napi/parser/src/raw_transfer.rs
Comment thread apps/oxlint/src-js/plugins/source_code.ts
@overlookmotel overlookmotel force-pushed the om/04-03-perf_linter_plugins_use_not_in_binary_search_loops branch from 0df9003 to 3ec6fdb Compare April 7, 2026 16:11
@overlookmotel overlookmotel self-assigned this Apr 7, 2026
@graphite-app graphite-app Bot added the 0-merge Merge with Graphite Merge Queue label Apr 7, 2026
@graphite-app
Copy link
Copy Markdown
Contributor

graphite-app Bot commented Apr 7, 2026

Merge activity

`>>` is cheaper than `>>>` because `>>` produces a 32-bit _signed_ integer which is V8's native number type (SMI). `>>>` produces a 32-bit _unsigned_ integer, which needs to be boxed and stored on the heap.

Source text in raw transfer is limited to 1 GiB, and therefore source offsets, number of lines, number of tokens, and number of comments after all less than `1 << 30`. Therefore even the sum of 2 of them cannot reach `1 << 31` (the maximum positive integer which can be stored as a positive signed 31-bit int. Therefore it's safe to use `>>` in these binary loops.
@graphite-app graphite-app Bot force-pushed the om/04-07-test_napi_parser_fix_benchmarks branch from b341688 to 990b73a Compare April 7, 2026 17:10
@graphite-app graphite-app Bot force-pushed the om/04-03-perf_linter_plugins_use_not_in_binary_search_loops branch from 3ec6fdb to 43482c7 Compare April 7, 2026 17:11
Base automatically changed from om/04-07-test_napi_parser_fix_benchmarks to main April 7, 2026 17:14
@graphite-app graphite-app Bot removed the 0-merge Merge with Graphite Merge Queue label Apr 7, 2026
@graphite-app graphite-app Bot merged commit 43482c7 into main Apr 7, 2026
24 of 25 checks passed
@graphite-app graphite-app Bot deleted the om/04-03-perf_linter_plugins_use_not_in_binary_search_loops branch April 7, 2026 17:15
graphite-app Bot pushed a commit that referenced this pull request Apr 7, 2026
…eserializer (#21132)

Use `int32` (`Int32Array`) instead of `uint32`(`Uint32Array`) for getting data from buffer in raw transfer deserializer. The buffer is 2 GiB in size, so all offsets within the buffer can be represented as a `u31` which can be stored in an `i32` without any loss, and with no risk of being interpreted as negative numbers.

Same as in #21129, the advantage of fetching offsets from an `Int32Array` is that V8 statically knows the value can be stored in an SMI, its native integer type, without any range checks.
camc314 pushed a commit that referenced this pull request Apr 13, 2026
### 💥 BREAKING CHANGES

- 36cdc31 str: [**BREAKING**] Remove identity `FromIn` impl for `Ident`
(#21251) (overlookmotel)
- 382958a span: [**BREAKING**] Remove re-exports of string types from
`oxc_span` crate (#21246) (overlookmotel)
- c4aedfa str: [**BREAKING**] Add `static_ident!` macro (#21245)
(overlookmotel)

### 🚀 Features

- e7e1aea transformer/typescript: Add `optimize_enums` option for
regular enum inlining (#20539) (Dunqing)
- 679f57f transformer/typescript: Implement const enum inlining and
declaration removal (#20508) (Dunqing)
- 6dd061c semantic: Extend `MemberWriteTarget` to cover all property
modification patterns (#21205) (Dunqing)
- f134e24 minifier: Support `property_write_side_effects` option to drop
unused property assignments (#20773) (Dunqing)
- 75663c0 semantic: Add enum member value evaluation for const enum
support (#20602) (Dunqing)
- 3cfe8ed semantic: Add `MemberWriteTarget` flag to `ReferenceFlags`
(#20772) (Dunqing)

### 🐛 Bug Fixes

- af1a586 transformer/class-properties: Use correct property name when
converting parameter properties (#21268) (Amal Jossy)
- b43250a allocator: Move allocation tracking into `Bump` (#21342)
(overlookmotel)
- 36f505f allocator: `StringBuilder` use `Allocator::alloc_layout`
(#21340) (overlookmotel)
- 7a08a6f allocator: Fix allocation counting in
`Allocator::alloc_concat_strs_array` (#21336) (overlookmotel)
- 2338e28 ecmascript: Treat `this` as potentially having side effects
(#21297) (sapphi-red)
- bd8bd39 allocator: Remove unsafe hacks from `from_raw_parts` methods
(#21283) (overlookmotel)
- 8f4c340 allocator: Remove dangerous pointer const to mut cast (#21279)
(overlookmotel)
- aa9259f parser: Add missing error code for optional param diagnostic
(#21258) (camc314)
- 04b3c2f str: Fix unsound casting const pointers to mut pointers
(#21242) (overlookmotel)
- ceadf6c str: Make `Ident::from_raw` an unsafe function (#21241)
(overlookmotel)
- eab13b3 transformer/decorators: Avoid accessor storage name collisions
(#21106) (Dunqing)
- 07e8a30 transformer/react-refresh: Handle parenthesized variable
initializers (#21047) (camc314)

### ⚡ Performance

- c3ca6f6 allocator: `StringBuilder::from_strs_array_in` check for 0
length earlier (#21338) (overlookmotel)
- c2422bb allocator: `Allocator::alloc_concat_strs_array` check for 0
length earlier (#21337) (overlookmotel)
- 04b0fdc allocator: Mark `Allocator::alloc_layout` as
`#[inline(always)]` (#21335) (overlookmotel)
- 17aee9e allocator: Use `offset_from_unsigned` in
`ChunkFooter::as_raw_parts` (#21280) (overlookmotel)
- 61adedd minifier: Fix O(n²) perf on very many var decls (#21062)
(Gunnlaugur Thor Briem)
- addcd02 napi/parser, linter/plugins: Raw transfer deserializer for
`Vec`s use shift instead of multiply where possible (#21142)
(overlookmotel)
- 3068ded napi/parser, linter/plugins: Shift before add when calculating
positions in raw transfer deserializer (#21141) (overlookmotel)
- eb400b8 napi/parser, linter/plugins: Remove `uint32` buffer view
(#21140) (overlookmotel)
- 2675085 napi/parser: Lazy deserialization use only `Int32Array`
(#21139) (overlookmotel)
- 5b35a53 napi/parser: Deserializing tokens use only `int32` array
(#21138) (overlookmotel)
- f163d10 parser: Tokens raw deserialization use `Int32Array` (#21137)
(overlookmotel)
- 7a86613 linter/plugins: Use `Int32Array`s for tokens and comments
buffers (#21136) (overlookmotel)
- 8c51121 napi/parser, linter/plugins: Raw transfer deserialize `Span`
fields as `i32`s (#21135) (overlookmotel)
- bc1bcdd napi/parser, linter/plugins: Inline trivial raw transfer field
deserializers into node object definitions (#21134) (overlookmotel)
- c0278ab napi/parser, linter/plugins: Use `Int32Array` in raw transfer
deserializer (#21132) (overlookmotel)
- 43482c7 linter/plugins: Use `>>` not `>>>` in binary search loops
(#21129) (overlookmotel)

### 📚 Documentation

- f5e1845 allocator: Upgrade headers in doc comments for `Bump` (#21263)
(overlookmotel)
- 2870174 allocator: Upper case `SAFETY` in comments (#21253)
(overlookmotel)
- 01bc269 str: Reformat `Ident` doc comments (#21240) (overlookmotel)
- dd47359 allocator: Add doc comments for panics and errors (#21230)
(overlookmotel)
camc314 pushed a commit that referenced this pull request Apr 13, 2026
# Oxlint
### 💥 BREAKING CHANGES

- 382958a span: [**BREAKING**] Remove re-exports of string types from
`oxc_span` crate (#21246) (overlookmotel)
- c4aedfa str: [**BREAKING**] Add `static_ident!` macro (#21245)
(overlookmotel)
- 7354f3c linter: [**BREAKING**] Error on no matched files (#21144)
(camc314)

### 🚀 Features

- 91f2c79 linter/eslint-jest-plugin: Implemented
`prefer-importing-jest-globals` rule (#21303) (Said Atrahouch)
- a02f32c linter: Add release version for existing rules (#21363)
(camchenry)
- b9e93da linter: Allow tagging rules with release version (#21362)
(camchenry)
- f99ecda oxlint: Gate `vite.config.ts` recognition behind `VP_VERSION`
env var (#21298) (leaysgur)
- cf459d3 linter: Implement suggestion for `no-empty-function` rule
(#21347) (Mikhail Baev)
- 7213d61 linter: Adding pending suggestions fix to `valid_expect`
rules. (#21249) (Said Atrahouch)
- ae45312 linter: Introduce `--type-check-only` flag (#21184) (camc314)
- 1ce8b90 linter: Implemented `valid-expect-in-promise` vitest and jest
rule (#21170) (Said Atrahouch)
- 39f7fda linter: Add auto-fix to `unicorn/prefer-default-parameters`
(#21166) (yefan)
- 15574bc linter/unicorn: Implement consistent-template-literal-escape
(#21126) (AliceLanniste)
- c5c8c03 linter/prefer-readonly-parameter-types: Move rule from nursery
to pedantic (#21114) (camc314)
- 1893be1 linter/no-useless-default-assignment: Move rule from nursery
to correctness (#21113) (camc314)
- 5462ff9 linter/strict-void-return: Move rule from nursery to pedantic
(#21115) (camc314)
- c2989bd linter/no-unnecessary-type-parameters: Move rule from nursery
to suspicious (#21112) (camc314)
- 79d339a linter/no-unnecessary-qualifier: Move rule from nursery to
style (#21111) (camc314)

### 🐛 Bug Fixes

- b577efc linter/unicorn: Handle optional chaining in
`prefer-array-flat` and `no-invalid-remove-event-listener` (#21299)
(Mikhail Baev)
- 5e55735 oxlint/lsp: Skip .git directories in LSP walkers (#21316)
(camc314)
- ec7f6ed oxlint, oxfmt: Apply `check_for_writer_error` to `.flush()`
(#21343) (Craig Morrison)
- a17a08a linter/no-useless-assignment: Handle continue edges in loop
analysis (#21358) (camc314)
- a0eac12 linter/array-type: Move match to first stmt (#21357) (camc314)
- 1b3abc3 linter: Exclude boundary tokens from JSXText whitespace check
in isSpaceBetweenTokens (#21313) (bab)
- ecbcf5e linter: More info to summary output for GitHub formatter
(#21330) (Théo LUDWIG)
- a0a8c62 linter/no-fallthrough: Check from start of switch case for
empty lines (#21324) (Josh Cartmell)
- 36f0bc4 linter/no-cycle: Report all cyclic dependencies inside a file
(#21259) (camc314)
- 3f80536 linter: Ignore regex flags other than `g`/`u`/`v` in
`prefer-string-replace-all` (#21203) (bab)
- f21d3aa linter/unicorn: Report on optional in
`require-number-to-fixed-digits-argument` rule (#21207) (Mikhail Baev)
- af8e122 linter: Render each config error as a separate diagnostic
(#21120) (bab)
- a950f55 linter/unicorn: Do not report on optionals in
`no-single-promise-in-promise-methods` (#21157) (Mikhail Baev)
- 472f8ee linter: Mark complete comment for unused disable directives +
lsp fix (#21092) (copilot-swe-agent)
- edd0865 linter/no-array-index-key: False positive when index is inside
an expression within a template literal (#21123) (bab)
- 7e8d520 linter/unicorn: Report on optional `foo?.postMessage` in
`require-post-message-target-origin` rule (#21104) (Mikhail Baev)

### ⚡ Performance

- addcd02 napi/parser, linter/plugins: Raw transfer deserializer for
`Vec`s use shift instead of multiply where possible (#21142)
(overlookmotel)
- 3068ded napi/parser, linter/plugins: Shift before add when calculating
positions in raw transfer deserializer (#21141) (overlookmotel)
- eb400b8 napi/parser, linter/plugins: Remove `uint32` buffer view
(#21140) (overlookmotel)
- 7a86613 linter/plugins: Use `Int32Array`s for tokens and comments
buffers (#21136) (overlookmotel)
- 8c51121 napi/parser, linter/plugins: Raw transfer deserialize `Span`
fields as `i32`s (#21135) (overlookmotel)
- bc1bcdd napi/parser, linter/plugins: Inline trivial raw transfer field
deserializers into node object definitions (#21134) (overlookmotel)
- c0278ab napi/parser, linter/plugins: Use `Int32Array` in raw transfer
deserializer (#21132) (overlookmotel)
- 43482c7 linter/plugins: Use `>>` not `>>>` in binary search loops
(#21129) (overlookmotel)

### 📚 Documentation

- 7888280 linter: Move config docs for `no-restricted-exports` (#21360)
(camchenry)
- 162d26c linter: Improve docs for `typescript/array-type` (#21356)
(camchenry)
- a2dbaec linter: Add missing docs for options for
`typescript/class-literal-property-style` (#21355) (camchenry)
- 79593eb linter: Improve docs for
`typescript/consistent-type-assertions` (#21353) (camchenry)
- f9d20d2 linter: Move config option docs for
`typescript/no-empty-object-type` (#21352) (camchenry)
- a8f650d linter: Add missing config option docs for
`prefer-string-start-ends-with` (#21332) (camchenry)
- cfd8a4f linter: Don't rely on old eslint doc for available globals
(#21334) (Nicolas Le Cam)
- 03865fa linter: Jest/prefer-snapshot-hint: add doc comment for
snapshot hint mode (#21290) (camchenry)
- a6fe09b linter: Add missing docs for config options in `react` plugin
(#21289) (camchenry)
- 60eaf47 linter: Add missing docs for config options in unicorn plugin
(#21288) (camchenry)
- c3c2055 linter: `jsx-a11y/label-has-associated-control`: document the
`assert` options (#21287) (camchenry)
- a928ed9 linter: Add missing config docs for vitest plugin rules
(#21285) (camchenry)
- 7e07c7c linter: `id-length`: move enum docs to doc comments (#21281)
(camchenry)
- 9746bdf linter: Add missing docs for `class-methods-use-this` config
(#21278) (camchenry)
- 6ffe7a5 linter: Move docs for `Target` variant onto enum (#21277)
(camchenry)
- 305350d linter/plugins: Correct comments (#21130) (overlookmotel)
# Oxfmt
### 💥 BREAKING CHANGES

- 382958a span: [**BREAKING**] Remove re-exports of string types from
`oxc_span` crate (#21246) (overlookmotel)

### 🚀 Features

- e3081e1 oxfmt: Gate `vite.config.ts` recognition behind `VP_VERSION`
env var (#21295) (leaysgur)
- 5b0b573 oxfmt: Update prettier to 3.8.2 (#21294) (leaysgur)
- 0d67834 oxfmt: Show hint for all files are ignored case (#21154)
(leaysgur)

### 🐛 Bug Fixes

- 2871fc2 oxfmt: Non idempotent formatting on comments in TS (#20449)
(Cat Chen)
- ec7f6ed oxlint, oxfmt: Apply `check_for_writer_error` to `.flush()`
(#21343) (Craig Morrison)
- 1a8c225 formatter: Preserve newline between self-closing JSX element
and single-char text (#21149) (Justin Mecham)
- 407b725 oxfmt: Indent dangling comments in empty enum with block
indent (#21163) (Leonabcd123)
- d13fd37 formatter: Remove extra outer parentheses on return with JSDoc
type cast (#21109) (bab)
- 22babde oxfmt: Fix unicode char escaping (#21162) (leaysgur)
- 4da53e5 formatter: Preserve trailing comma in TSX arrow functions with
default type params (#21151) (Justin Mecham)
- 94fe774 oxfmt: Handle paths with consecutive leading slashes (#21155)
(leaysgur)
- 50c389b oxfmt: Support `.editorconfig` `quote_type` (#20989)
(leaysgur)

### ⚡ Performance

- 0ce619f formatter: Use `Allocator::alloc_concat_strs_array` instead of
`StringBuilder::from_strs_array_in` (#21339) (overlookmotel)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

A-cli Area - CLI A-linter Area - Linter A-linter-plugins Area - Linter JS plugins A-parser Area - Parser C-performance Category - Solution not expected to change functional behavior, only performance

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants