[3.0.1] Huge performance regression in import/no-cycle

sqal commented 3 months ago

Hi. Today I upgraded the plugin to version 3.0.1 and noticed a huge drop in performance in the no-cycle rule. Details below.

Setup

Depencecies:

{
  "eslint": "^9.6.0",
  "eslint-import-resolver-typescript": "^3.6.1",
  "eslint-plugin-import": "npm:eslint-plugin-import-x@^3.0.1",
  "eslint-plugin-import-x": "^3.0.1",
  "typescript": "^5.5.3",
  "typescript-eslint": "^8.0.0-alpha.39"
}

Eslint config, I only left the no-cycle rule

```js import importX from 'eslint-plugin-import-x'; import tseslint from 'typescript-eslint'; export default [ { languageOptions: { parser: tseslint.parser, sourceType: 'module', }, }, { files: ['**/*.ts'], plugins: { 'import-x': importX, }, settings: { ...importX.configs.typescript.settings, 'import-x/resolver': { typescript: {}, }, }, rules: { 'import-x/no-cycle': ['error', { maxDepth: 3 }], }, }, ]; ```

I ran the test on these two machines.

macOS

``` System: OS: macOS 13.6.7 CPU: (4) x64 Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz Memory: 5.96 GB / 16.00 GB Shell: 5.9 - /bin/zsh Binaries: Node: 22.4.0 - /usr/local/bin/node npm: 10.8.1 - /usr/local/bin/npm pnpm: 9.5.0 - /usr/local/bin/pnpm ```

Windows

``` System: OS: Windows 10 10.0.19045 CPU: (4) x64 Intel(R) Core(TM) i5-4690K CPU @ 3.50GHz Memory: 2.80 GB / 7.94 GB Binaries: Node: 22.4.1 - C:\Program Files\nodejs\node.EXE npm: 10.8.2 - C:\Program Files\nodejs\npm.CMD pnpm: 9.5.0 - C:\Program Files\nodejs\pnpm.CMD ```

Results:

MacOS:

eslint-plugin-import-x@0.5.3

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  8580.409 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  8101.124 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  8239.801 |   100.0%

eslint-plugin-import-x@3.0.1

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 25850.526 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 24692.786 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 26082.004 |   100.0%

Windows:

eslint-plugin-import-x@0.5.3

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 20999.926 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 19591.972 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 19811.106 |   100.0%

eslint-plugin-import-x@3.0.1

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 78557.409 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 82919.007 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 78773.430 |   100.0%

Summary

So these are the numbers. I ran the test on a fairly large TS codebase (~680 files). You can see that 3.0.1 is at least 3x slower on both machines, which is strange because this release was supposed to significantly improve no-cycle performance. What is also noteworthy to me are the test times on Windows compared to macOS with eslint-plugin-import-x@0.5.3 , they're like ~2.5 times slower. I know both my pc's are old and rather slow, but Windows have slightly better cpu, it's also overclocked, so I don't understand why it's so slow there. But the times with eslint-plugin-import-x@3.0.1 on Windows are really bad, which worries me the most. I would appreciate your help with this issue and let me know if you need more info from me.

SukkaW commented 3 months ago

I will look into this!

SukkaW commented 3 months ago

@sqal In the meantime, would you mind sharing the repo w/ me privately so that I can do some profiling? I didn't notice significant performance regression in a few of my repos.

sqal commented 3 months ago

@SukkaW Hi. I am sorry but unfortunately can't share the code because it's company's repository. Regarding your benchmarks, are you saying that tests you have done with 3.0.1 are a little slower or actually faster? I am sorry I didn't mention it earlier, but I've just found that eslint-import-resolver-typescript is the bottleneck here. As you can see I had it enabled in my config because I use import alias extensively in my codebase (tsconfig paths "~/*": ["./src/*"]). So now I've disabled it and managed to replace all alias imports with relative imports and here are the results:

macOS:

0.5.3

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  3797.711 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  3588.827 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  3627.157 |   100.0%

3.0.1

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  6650.798 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  5998.482 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  6081.399 |   100.0%

Windows:

0.5.3

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  8333.971 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  7466.189 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle |  7552.176 |   100.0%

3.0.1

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 17822.868 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 18841.721 |   100.0%

Rule              | Time (ms) | Relative
:-----------------|----------:|--------:
import-x/no-cycle | 18822.910 |   100.0%

This is much, much better. Windows still runs slower :/ but what an improvement overall. 3.0.1 is still slower than 0.5.3 though 🤔

SukkaW commented 3 months ago

I've just found that eslint-import-resolver-typescript is the bottleneck here.

It means there must be some regression related to resolving and parsing. I will be looking into this!

In the meantime, there is a resolver made by @9romise: https://github.com/9romise/eslint-import-resolver-oxc

zloirock commented 3 months ago

core-js repo, config, no-cycle from 0.5.3 on my laptop takes 2937.782ms, from 3.0.1 - 4865.651ms. Without custom resolvers.

SukkaW commented 3 months ago

core-js repo, config, no-cycle from 0.5.3 on my laptop takes 2937.782ms, from 3.0.1 - 4865.651ms. Without custom resolvers.

Thanks for the info! I will profile on the core-js repo then!

SukkaW commented 3 months ago

Update:

@zloirock @sqal I have successfully grabbed the flamegraph from core-js repo:

For any one is also interested: flamegraph.html.txt

sqal commented 3 months ago

I tried eslint-import-resolver-oxc but didn't notice significant improvement over eslint-import-resolver-typescript, times are very similar to those in my issue report. I will go back to 0.5.3 for now.

sqal commented 3 months ago

I cloned the repository and built the plugin and can confirm that https://github.com/un-ts/eslint-plugin-import-x/commit/5cce9461c2863c31af126afb7c59d67deb13a6e7 is the commit that slowed down this rule. With https://github.com/un-ts/eslint-plugin-import-x/commit/fe3121a2d74db1c2178d1ab189ef59b80c5b90c4 it was working fine.

SukkaW commented 3 months ago

The problem might be caused by SCC. Calculating SCC introduces extra overhead, while it doesn't actually reduce any heavy works.

Before completely removing SCC, I might try to optimize SCC first.

SukkaW commented 3 months ago

@sqal @zloirock I've reverted #111 and I am currently working on creating a new rule no-cycle-next using graph.

cjnoname commented 2 months ago

Investigate eslint v9 perf regression arktypeio/arktype#1114

Any news on no-cycle-next? Really interested to see how it performs

SukkaW commented 2 months ago

Investigate eslint v9 perf regression arktypeio/arktype#1114

Any news on no-cycle-next? Really interested to see how it performs

We can't backport https://github.com/import-js/eslint-plugin-import/pull/2998. It actually introduces an extra step (SCC doesn't replace the original detection algorithm, instead it is a new additional check) without introducing a proper early return. That's why it becomes slower and I have reverted it.

I am interested in using https://www.npmjs.com/package/@newdash/graphlib to implement a dependency graph, this should be faster than the no-cycle current hand-made implementation.

soryy708 commented 4 weeks ago

eslint-plugin-import merged changes to SCC and fixes to performance, so you may want to try porting it again, or comparing your performance to the original rule.

Idk why would graphlib be faster than scc upstream uses?

SukkaW commented 4 weeks ago

eslint-plugin-import merged changes to SCC and fixes to performance, so you may want to try porting it again, or comparing your performance to the original rule.

Your implementation is done by adding an early return, with an overhead for building up the SCC graph. If SCC does detect any cycle import, it immediately falls back to the original detection implementation, which doubles the work per file linted. So it'd be slower rather than faster.

Idk why would graphlib be faster than scc upstream uses?

I want to build a cycle import detection from the ground up. It would calculate SCC once per module and doesn't need any extra detection steps at all. You can't attach extra objects (E.g. AST) with @rtsao/scc.

un-ts / eslint-plugin-import-x