Migrate functional-red-black-tree to Js-sdsl OrderedMap

[ZLY201]

ESLint version

v8.4.1

What problem do you want to solve?

Hey! I'm the developer of Js-sdsl. Official website: https://js-sdsl.github.io/

Now, we published the version 4.1.3.

I see you are using functional-red-black-tree.

In benchmark, we have confirmed that Js-sdsl is several times faster than functional-red-black-tree.

What do you think is the correct solution?

We would like to invite you to migrate red-black tree related functions to Js-sdsl v4.1.3.

Looking forward to your reply! :D

Participation

• I am willing to submit a pull request for this change.

Additional comments

No response

[aladdin-add]

👍 sgtm! I can see it will be a big perf win to make the migration - rb-tree was used in the indent rule, and it has been the most time-consuming:

Rule                             | Time (ms) | Relative
:--------------------------------|----------:|--------:
indent                           |  5686.558 |    20.0%
jsdoc/check-line-alignment       |   981.454 |     3.4%
jsdoc/valid-types                |   850.830 |     3.0%
jsdoc/check-types                |   668.047 |     2.3%
eslint-plugin/no-identical-tests |   650.312 |     2.3%
n/no-missing-require             |   627.973 |     2.2%
jsdoc/check-tag-names            |   581.224 |     2.0%
jsdoc/check-values               |   571.479 |     2.0%
jsdoc/check-syntax               |   519.362 |     1.8%
jsdoc/empty-tags                 |   507.944 |     1.8%

[ZLY201]

I'm so glad you can consider my suggestion!

I'm trying to make a PR, but when I run npm run perf, it occurs an error:

Loading:
  Load performance Run #1:  74.4105ms
  Load performance Run #2:  73.857542ms
  Load performance Run #3:  73.10525ms
  Load performance Run #4:  72.192292ms
  Load performance Run #5:  74.429084ms

  Load Performance median:  73.857542ms

Single File:
  CPU Speed is 24 with multiplier 13000000
  Performance Run #1 failed.
STDERR:
Invalid option '--eslintrc' - perhaps you meant '--ignore'?



/Users/xxx/code/myProject/eslint/Makefile.js:994
            throw new Error("Performance test failed.");
            ^

This error also occurs in the main branch.

Maybe I'm using this command incorrectly? I want some help.

Thanks!

[aladdin-add]

looks like it was caused by the new config system: #16235.

I'll make a fix later.

[ZLY201]

Hey, I also get an error in your PR (#16258) when I run npm run test:

  29318 passing (38s)
  1 failing

  1) cli
       when loading a custom rule
         should return an error when rule isn't found:
     AssertionError [ERR_ASSERTION]: The input did not match the regular expression /Error while loading rule 'custom-rule': Cannot read property/u. Input:

"TypeError: Error while loading rule 'custom-rule': Cannot read properties of null (reading 'something')\n" +
  'Occurred while linting /var/folders/b1/0fd1b6hs7lz0fm_mh346lybm0000gn/T/eslint/fixtures/rules/test/test-custom-rule.js'

      at async Context.<anonymous> (tests/lib/cli.js:511:13)




=============================== Coverage summary ===============================
Statements   : 98.82% ( 15543/15728 )
Branches     : 97.61% ( 12685/12995 )
Functions    : 99.47% ( 3600/3619 )
Lines        : 98.81% ( 15274/15457 )
================================================================================
/Users/xxx/code/myProject/perfEslint/eslint/node_modules/shelljs/src/common.js:401
      if (config.fatal) throw e;

[mdjermanovic]

Hey, I also get an error in your PR (#16258) when I run npm run test:

  29318 passing (38s)
  1 failing

  1) cli
       when loading a custom rule
         should return an error when rule isn't found:
     AssertionError [ERR_ASSERTION]: The input did not match the regular expression /Error while loading rule 'custom-rule': Cannot read property/u. Input:

"TypeError: Error while loading rule 'custom-rule': Cannot read properties of null (reading 'something')\n" +
  'Occurred while linting /var/folders/b1/0fd1b6hs7lz0fm_mh346lybm0000gn/T/eslint/fixtures/rules/test/test-custom-rule.js'

      at async Context.<anonymous> (tests/lib/cli.js:511:13)




=============================== Coverage summary ===============================
Statements   : 98.82% ( 15543/15728 )
Branches     : 97.61% ( 12685/12995 )
Functions    : 99.47% ( 3600/3619 )
Lines        : 98.81% ( 15274/15457 )
================================================================================
/Users/xxx/code/myProject/perfEslint/eslint/node_modules/shelljs/src/common.js:401
      if (config.fatal) throw e;

This problem was fixed in #15041, do you have the latest version of the eslint repo locally?

[ZLY201]

Hey, I have submitted a PR(#16267), and the test results of this migration on my computer are as follows:

• environment

Darwin 21.6.0 arm64
Node.JS 16.14.0
V8 9.4.146.24-node.20
Apple M1 Pro × 10

• main branch

eslint (main) $ TIMING=1 eslint lib
Rule                             | Time (ms) | Relative
:--------------------------------|----------:|--------:
indent                           |  3426.544 |    21.7%
jsdoc/check-access               |   516.371 |     3.3%
jsdoc/valid-types                |   495.843 |     3.1%
eslint-plugin/no-identical-tests |   470.911 |     3.0%
jsdoc/check-types                |   355.969 |     2.3%
n/no-missing-require             |   351.201 |     2.2%
jsdoc/check-tag-names            |   318.509 |     2.0%
jsdoc/check-alignment            |   293.297 |     1.9%
jsdoc/check-values               |   292.201 |     1.9%
n/no-extraneous-require          |   279.821 |     1.8%

• migrate branch

eslint git:(perf/migrate-rbtree) TIMING=1 eslint lib
Rule                             | Time (ms) | Relative
:--------------------------------|----------:|--------:
indent                           |  2477.953 |    17.6%
jsdoc/valid-types                |   497.200 |     3.5%
jsdoc/check-access               |   475.173 |     3.4%
eslint-plugin/no-identical-tests |   473.481 |     3.4%
jsdoc/check-types                |   343.164 |     2.4%
n/no-missing-require             |   331.479 |     2.4%
jsdoc/check-tag-names            |   318.575 |     2.3%
jsdoc/check-alignment            |   285.792 |     2.0%
jsdoc/check-values               |   277.397 |     2.0%
jsdoc/check-line-alignment       |   269.985 |     1.9%

I was wondering if this met your expectations, or if it met the requirements as a PR?