feat(linter): improve no-accumulating-spread by camc314 · Pull Request #5302 · oxc-project/oxc

camc314 · 2024-08-28T15:22:37Z

VSCode has a couple violations. examples:

  x oxc(no-accumulating-spread): Do not spread accumulators in loops
    ,-[src/vs/workbench/services/textMate/common/TMGrammarFactory.ts:65:5]
 64 |                 let injections: string[] = [];
 65 |                 for (let i = 1; i <= scopeParts.length; i++) {
    :                 ^|^
    :                  `-- For this loop
 66 |                     const subScopeName = scopeParts.slice(0, i).join('.');
 67 |                     injections = [...injections, ...(this._injections[subScopeName] || [])];
    :                                   ^^^^^^|^^^^^^
    :                                         `-- From this spread
 68 |                 }
    `----
  help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead.
        Using spreads within accumulators leads to `O(n^2)` time complexity.

  x oxc(no-accumulating-spread): Do not spread accumulators in loops
     ,-[src/vs/base/common/actions.ts:205:3]
 204 |         let out: IAction[] = [];
 205 |         for (const list of actionLists) {
     :         ^|^
     :          `-- For this loop
 206 |             if (!list.length) {
 207 |                 // skip
 208 |             } else if (out.length) {
 209 |                 out = [...out, new Separator(), ...list];
     :                        ^^^|^^
     :                           `-- From this spread
 210 |             } else {
     `----
  help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead.
        Using spreads within accumulators leads to `O(n^2)` time complexity.

  help: It looks like you're spreading an `Array`. Consider using the `Array.push` or `Array.concat` methods to mutate the accumulator instead.
        Using spreads within accumulators leads to `O(n^2)` time complexity.

  x oxc(no-accumulating-spread): Do not spread accumulators in loops
     ,-[src/vs/workbench/contrib/extensions/browser/extensionsActions.ts:302:3]
 301 |         let actions: IAction[] = [];
 302 |         for (const visibleActions of actionsGroups) {
     :         ^|^
     :          `-- For this loop
 303 |             if (visibleActions.length) {
 304 |                 actions = [...actions, ...visibleActions, new Separator()];
     :                            ^^^^^|^^^^
     :                                 `-- From this spread
 305 |             }
     `----
  help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead.
        Using spreads within accumulators leads to `O(n^2)` time complexity.

  x oxc(no-accumulating-spread): Do not spread accumulators in loops
      ,-[src/vs/workbench/contrib/extensions/browser/extensionsActions.ts:1141:3]
 1140 |         let actions: IAction[] = [];
 1141 |         for (const menuActions of menuActionGroups) {
      :         ^|^
      :          `-- For this loop
 1142 |             actions = [...actions, ...menuActions, new Separator()];
      :                        ^^^^^|^^^^
      :                             `-- From this spread
 1143 |         }
      `----
  help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead.
        Using spreads within accumulators leads to `O(n^2)` time complexity.

  x oxc(no-accumulating-spread): Do not spread accumulators in loops
     ,-[src/vs/workbench/contrib/extensions/browser/extensionsViews.ts:334:4]
 333 |             let actions: IAction[] = [];
 334 |             for (const menuActions of groups) {
     :             ^|^
     :              `-- For this loop
 335 |                 actions = [...actions, ...menuActions, new Separator()];
     :                            ^^^^^|^^^^
     :                                 `-- From this spread
 336 |             }
     `----
  help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead.
        Using spreads within accumulators leads to `O(n^2)` time complexity.

camc314 · 2024-08-28T15:22:52Z

feat(linter): improve no-accumulating-spread #5302 👈
main

This stack of pull requests is managed by Graphite. Learn more about stacking.

Join @camc314 and the rest of your teammates on Graphite

codspeed-hq · 2024-08-28T15:38:23Z

CodSpeed Performance Report

Merging #5302 will not alter performance

_{Comparing c/08-28-feat_linter_improve_no-accumulating-spread (b103737) with main (da8aa18)}

Summary

✅ 28 untouched benchmarks

DonIsaac · 2024-08-28T17:40:15Z

I disagree with this change. These examples are still O(n^2). Even if VSCode is writing code like this, that doesn't make it a non-violation.

camc314 · 2024-08-28T17:57:33Z

I disagree with this change. These examples are still O(n^2). Even if VSCode is writing code like this, that doesn't make it a non-violation.

why would the fixed version of this code be O(n^2)?

it would improve performance in the same way converting a spread in a reduce loop to a push would.

camc314 · 2024-08-28T19:27:41Z

i also think i've dona a bad job explaining this. so let me try again, and attempt to explain why this is a good thing to add to the lint rule. 🙂

lets take the following example, where n is the count of iterations

let foo = [];
for (let i = 0; i < n; i++) {
    foo = [...foo, i];
}

The time complexity of this example

on the first iteration: O(0) (foo is empty)
on the second iteration: O(1) (foo has 1x element)
on the third iteration: O(2) (foo has 2x element)
on the nth iteration: O(n-1) (foo has n-1 elements)

this leads to a total time complexity of O(n^2)

If we rewrite this code as

let foo = [];
for (let i = 0; i < n; i++) {
    foo.push(i)
}

The time complexity of this will be:

on the first iteration: O(1).
on the second iteration: O(1).
on the nth iteration: O(1)

leading to a total time complexity of O(n)

Furthermore, in the first example, it will make n allocations of arrays (every time we do [...foo, i] it creates a new array. whereas the second should only have 1 allocation (this ignores the fact that foo will probably have to resize, but this will still be faster than the prior case)

We can see the difference in performance brenchmarks

import { bench, run } from 'mitata';

const Ns = [1, 10, 100, 1000, 10000, 100000, 1000000];

for (const N of Ns) {
    bench(`slow (spread array) ${N}`, () => {
        let foo = [];
        for (let i = 0; i < N; i++) {
            foo = [...foo, i];
        }
    });

    bench(`fast (push into array) ${N}`, () => {
        let foo = [];
        for (let i = 0; i < N; i++) {
            foo.push(i);
        }
    });
}

await run();

yeilds the following results: (N=10,000,000)

cpu: Apple M2 Max
runtime: node v22.5.1 (arm64-darwin)

benchmark                           time (avg)             (min … max)       p75       p99      p999
---------------------------------------------------------------------- -----------------------------
slow (spread array) 1            21.68 ns/iter     (15.06 ns … 153 ns)  32.27 ns   39.9 ns  57.68 ns
fast (push into array) 1          9.18 ns/iter      (5.57 ns … 228 ns)   6.33 ns  27.26 ns  43.88 ns
slow (spread array) 10             223 ns/iter       (204 ns … 292 ns)    233 ns    261 ns    288 ns
fast (push into array) 10        15.66 ns/iter     (12.78 ns … 236 ns)  13.55 ns  42.22 ns  79.83 ns
slow (spread array) 100          6'099 ns/iter   (5'864 ns … 6'878 ns)  6'207 ns  6'812 ns  6'878 ns
fast (push into array) 100         182 ns/iter       (164 ns … 309 ns)    190 ns    228 ns    298 ns
slow (spread array) 1000           430 µs/iter       (379 µs … 876 µs)    448 µs    502 µs    851 µs
fast (push into array) 1000      2'511 ns/iter   (2'379 ns … 3'169 ns)  2'499 ns  3'167 ns  3'169 ns
slow (spread array) 10000       39'149 µs/iter (38'492 µs … 39'597 µs) 39'316 µs 39'597 µs 39'597 µs
fast (push into array) 10000    21'490 ns/iter    (18'916 ns … 247 µs) 20'292 ns 77'417 ns 99'083 ns
slow (spread array) 100000      11'019 ms/iter (10'920 ms … 11'230 ms) 11'133 ms 11'230 ms 11'230 ms
fast (push into array) 100000      406 µs/iter     (341 µs … 1'201 µs)    391 µs    668 µs    951 µs

represented a bit cleaner:

| Size   | Spread Array                       | Push Into Array          | Percentage Faster |
| ------ | ---------------------------------- | ------------------------ | ----------------- |
| 1      | 21.88 ns/iter                      | 9.79 ns/iter             | 123.46%           |
| 10     | 228.00 ns/iter                     | 16.28 ns/iter            | 1300.49%          |
| 1 00   | 6,731.00 ns/iter                   | 203 ns/iter              | 3,215%            |
| 1000   | 494,000.00 ns/iter                 | 2,822 ns/iter            | 17,405%           |
| 10000  | 41,978,000 ns (41,978 µs/iter)     | 22'417 ns/iter           | 190,707,195%      |
| 100000 | 12,158,000,000 ns (12'158 ms/iter) | 439,000 ns (439 µs/iter) | 2,769,376%        |

as you can see. using Array.prototype.push is significantly faster than spreading

@DonIsaac let me know your thoughts

DonIsaac · 2024-08-28T23:19:35Z

@camc314 i owe you an apology, I though this PR was allowing spreads in for-loops. This is a misunderstanding on my part. I'll re-open this PR.

crates/oxc_linter/src/rules/oxc/no_accumulating_spread.rs

Boshen · 2024-08-29T00:50:32Z

This is nice 👍

camc314 · 2024-08-29T07:58:00Z

@camc314 i owe you an apology, I though this PR was allowing spreads in for-loops. This is a misunderstanding on my part. I'll re-open this PR.

no worries, thanks for bearing with me! the description lacked a clear explanation

graphite-app · 2024-08-29T13:06:25Z

Merge activity

Aug 29, 9:06 AM EDT: The merge label 'merge' was detected. This PR will be added to the Graphite merge queue once it meets the requirements.
Aug 29, 10:16 AM EDT: DonIsaac added this pull request to the Graphite merge queue.
Aug 29, 10:20 AM EDT: DonIsaac merged this pull request with the Graphite merge queue.

VSCode has a couple violations. examples: ``` x oxc(no-accumulating-spread): Do not spread accumulators in loops ,-[src/vs/workbench/services/textMate/common/TMGrammarFactory.ts:65:5] 64 | let injections: string[] = []; 65 | for (let i = 1; i <= scopeParts.length; i++) { : ^|^ : `-- For this loop 66 | const subScopeName = scopeParts.slice(0, i).join('.'); 67 | injections = [...injections, ...(this._injections[subScopeName] || [])]; : ^^^^^^|^^^^^^ : `-- From this spread 68 | } `---- help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead. Using spreads within accumulators leads to `O(n^2)` time complexity. x oxc(no-accumulating-spread): Do not spread accumulators in loops ,-[src/vs/base/common/actions.ts:205:3] 204 | let out: IAction[] = []; 205 | for (const list of actionLists) { : ^|^ : `-- For this loop 206 | if (!list.length) { 207 | // skip 208 | } else if (out.length) { 209 | out = [...out, new Separator(), ...list]; : ^^^|^^ : `-- From this spread 210 | } else { `---- help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead. Using spreads within accumulators leads to `O(n^2)` time complexity. help: It looks like you're spreading an `Array`. Consider using the `Array.push` or `Array.concat` methods to mutate the accumulator instead. Using spreads within accumulators leads to `O(n^2)` time complexity. x oxc(no-accumulating-spread): Do not spread accumulators in loops ,-[src/vs/workbench/contrib/extensions/browser/extensionsActions.ts:302:3] 301 | let actions: IAction[] = []; 302 | for (const visibleActions of actionsGroups) { : ^|^ : `-- For this loop 303 | if (visibleActions.length) { 304 | actions = [...actions, ...visibleActions, new Separator()]; : ^^^^^|^^^^ : `-- From this spread 305 | } `---- help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead. Using spreads within accumulators leads to `O(n^2)` time complexity. x oxc(no-accumulating-spread): Do not spread accumulators in loops ,-[src/vs/workbench/contrib/extensions/browser/extensionsActions.ts:1141:3] 1140 | let actions: IAction[] = []; 1141 | for (const menuActions of menuActionGroups) { : ^|^ : `-- For this loop 1142 | actions = [...actions, ...menuActions, new Separator()]; : ^^^^^|^^^^ : `-- From this spread 1143 | } `---- help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead. Using spreads within accumulators leads to `O(n^2)` time complexity. x oxc(no-accumulating-spread): Do not spread accumulators in loops ,-[src/vs/workbench/contrib/extensions/browser/extensionsViews.ts:334:4] 333 | let actions: IAction[] = []; 334 | for (const menuActions of groups) { : ^|^ : `-- For this loop 335 | actions = [...actions, ...menuActions, new Separator()]; : ^^^^^|^^^^ : `-- From this spread 336 | } `---- help: Consider using `Object.assign()` or `Array.prototype.push()` to mutate the accumulator instead. Using spreads within accumulators leads to `O(n^2)` time complexity. ```

…d` (#5373) mentioned here: #5302 (comment) it's not exactly clear why we check that it's a `let` declaration kind.

## [0.9.2] - 2024-09-02 ### Features - f81e8a1 linter: Add `oxc/no-async-endpoint-handlers` (#5364) (DonIsaac) - b103737 linter: Improve no-accumulating-spread (#5302) (camc314) - 9c22ce9 linter: Add hyperlinks to diagnostic messages (#5318) (DonIsaac) - 1967c67 linter/eslint: Implement no-new-func (#5360) (dalaoshu) - b867e5f linter/eslint-plugin-promise: Implement catch-or-return (#5121) (Jelle van der Waa) - 8d781e7 linter/oxc: Differentiate between array/object in `no-accumulating-spread` loop diagnostic (#5375) (camc314) - db55444 linter/oxc: Add fixer for `double-comparisons` (#5378) (camc314) - e5c755a linter/promise: Add `spec-only` rule (#5124) (Jelle van der Waa) - 4c0861f linter/unicorn: Add fixer for `prefer-type-error` (#5311) (camc314) - 084c2d1 linter/vitest: Implement prefer-to-be-object (#5321) (dalaoshu) ### Bug Fixes - 11b93af linter/unicorn: Consistent-function-scoping false positive on assignment expression (#5312) (Arian94) ### Performance - f052a6d linter: `react/jsx_no_undef` faster check for unbound references (#5349) (overlookmotel) - 05636b7 linter: Avoid unnecessary work in `jsx_a11y/anchor_is_valid` rule (#5341) (overlookmotel) ### Refactor - afb038e linter: `react/jsx_no_undef` use loop instead of recursion (#5347) (overlookmotel) - fe62687 linter: Simplify skipping JSX elements in `unicorn/consistent_function_scoping` (#5351) (overlookmotel) - 381d9fe linter: Shorten code in `react/jsx_no_useless_fragment` (#5350) (overlookmotel) - 83b9a82 linter: Fix indentation in `nextjs/no_script_component_in_head` rule (#5338) (overlookmotel) - 89f0188 linter: Improve docs for `react/jsx_no_target_blank` rule (#5342) (overlookmotel) - 57050ab linter: Shorten code in `jsx_a11y/aria_activedescendant_has_tabindex` rule (#5340) (overlookmotel) - ed31d67 linter/jest: Fix indentation in code comment (#5372) (camc314) - 2499cb9 linter/oxc: Update rule docs for `erasing-op` (#5376) (camc314) - 69493d2 linter/oxc: Improve diagnostic for `no-accumulating-spread` in loops (#5374) (camc314) - 024b585 linter/oxc: Improve code comment for `no-accumulating-spread` (#5373) (camc314) Co-authored-by: Boshen <[email protected]>

camc314 marked this pull request as ready for review August 28, 2024 15:22

github-actions bot added the A-linter Area - Linter label Aug 28, 2024

camc314 force-pushed the c/08-28-feat_linter_improve_no-accumulating-spread branch from cc648de to b1ba16f Compare August 28, 2024 15:26

camc314 requested a review from DonIsaac August 28, 2024 15:26

DonIsaac added the X-wontfix Close Reason - wontfix label Aug 28, 2024

DonIsaac closed this Aug 28, 2024

camc314 mentioned this pull request Aug 28, 2024

enhancement(linter) expand no-accumulating-spread #5288

Closed

DonIsaac reopened this Aug 28, 2024

DonIsaac reviewed Aug 28, 2024

View reviewed changes

crates/oxc_linter/src/rules/oxc/no_accumulating_spread.rs Show resolved Hide resolved

camc314 closed this Aug 29, 2024

camc314 reopened this Aug 29, 2024

camc314 force-pushed the c/08-28-feat_linter_improve_no-accumulating-spread branch from b1ba16f to 85c4122 Compare August 29, 2024 08:05

DonIsaac approved these changes Aug 29, 2024

View reviewed changes

DonIsaac added the 0-merge Merge with Graphite Merge Queue label Aug 29, 2024

DonIsaac force-pushed the c/08-28-feat_linter_improve_no-accumulating-spread branch from 85c4122 to b103737 Compare August 29, 2024 14:17

graphite-app bot merged commit b103737 into main Aug 29, 2024

graphite-app bot deleted the c/08-28-feat_linter_improve_no-accumulating-spread branch August 29, 2024 14:20

camc314 linked an issue Aug 31, 2024 that may be closed by this pull request

enhancement(linter) expand no-accumulating-spread #5288

Closed

camc314 mentioned this pull request Aug 31, 2024

refactor(linter/oxc): improve code comment for no-accumulating-spread #5373

Merged

DonIsaac pushed a commit that referenced this pull request Aug 31, 2024

refactor(linter/oxc): improve code comment for `no-accumulating-sprea…

024b585

…d` (#5373) mentioned here: #5302 (comment) it's not exactly clear why we check that it's a `let` declaration kind.

oxc-bot mentioned this pull request Sep 2, 2024

Release oxlint v0.9.2 #5401

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Comments

feat(linter): improve no-accumulating-spread#5302

feat(linter): improve no-accumulating-spread#5302
graphite-app[bot] merged 1 commit intomainfrom
c/08-28-feat_linter_improve_no-accumulating-spread

camc314 commented Aug 28, 2024 •

edited

Loading

Uh oh!

camc314 commented Aug 28, 2024

Uh oh!

codspeed-hq bot commented Aug 28, 2024 •

edited

Loading

Uh oh!

DonIsaac commented Aug 28, 2024

Uh oh!

camc314 commented Aug 28, 2024

Uh oh!

camc314 commented Aug 28, 2024 •

edited

Loading

Uh oh!

DonIsaac commented Aug 28, 2024

Uh oh!

Uh oh!

Boshen commented Aug 29, 2024

Uh oh!

camc314 commented Aug 29, 2024

Uh oh!

graphite-app bot commented Aug 29, 2024 •

edited

Loading

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Comments

Conversation

camc314 commented Aug 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

camc314 commented Aug 28, 2024

Uh oh!

codspeed-hq bot commented Aug 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

CodSpeed Performance Report

Merging #5302 will not alter performance

Summary

Uh oh!

DonIsaac commented Aug 28, 2024

Uh oh!

camc314 commented Aug 28, 2024

Uh oh!

camc314 commented Aug 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DonIsaac commented Aug 28, 2024

Uh oh!

Uh oh!

Boshen commented Aug 29, 2024

Uh oh!

camc314 commented Aug 29, 2024

Uh oh!

graphite-app bot commented Aug 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Merge activity

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

camc314 commented Aug 28, 2024 •

edited

Loading

codspeed-hq bot commented Aug 28, 2024 •

edited

Loading

camc314 commented Aug 28, 2024 •

edited

Loading

graphite-app bot commented Aug 29, 2024 •

edited

Loading