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

[sqal]

trafficstars

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

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:

[email protected]
    
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%


[email protected]

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:

[email protected]

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%


[email protected]

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 [email protected] , 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 [email protected] 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]

I will look into this!

[SukkaW]

@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]

@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]

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]

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]

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]

Update:

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

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

[sqal]

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]

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]

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]

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

[cjnoname]

Investigate eslint v9 perf regression arktypeio/arktype#1114

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

[SukkaW]

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]

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]

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.

[silverwind]

Would it be possible to port the disableScc option to this plugin?

https://github.com/import-js/eslint-plugin-import/blob/main/docs/rules/no-cycle.md#disablescc

In one of my repos, I had a 20x speed gain with disableScc: true, but I guess results will vary per repo.

[silverwind]

To add one data point, here is the rule's performance on this repo.

$ TIMING=1 make lint-js
npx eslint --color --max-warnings=0 --ext js,ts,vue web_src/js tools *.js *.ts *.cjs tests/e2e
Rule                                   | Time (ms) | Relative
:--------------------------------------|----------:|--------:
import-x/no-cycle                      | 81008.693 |    69.5%
import-x/no-unused-modules             | 19396.903 |    16.6%
import-x/extensions                    |  7068.636 |     6.1%
import-x/named                         |  4869.273 |     4.2%
@typescript-eslint/no-deprecated       |  1446.464 |     1.2%
vue-scoped-css/no-unused-selector      |   370.138 |     0.3%
unicorn/no-unnecessary-polyfills       |   235.655 |     0.2%
@typescript-eslint/no-misused-promises |   212.189 |     0.2%
import-x/no-extraneous-dependencies    |   186.998 |     0.2%
sonarjs/no-ignored-return              |   146.101 |     0.1%

[SukkaW]

Would it be possible to port the disableScc option to this plugin?

https://github.com/import-js/eslint-plugin-import/blob/main/docs/rules/no-cycle.md#disablescc

In one of my repos, I had a 20x speed gain with disableScc: true, but I guess results will vary per repo.

But if you enable the detailed error message output you will double or even triple the workload since the rule now not only detects the loop but also trying to figure out the details.

[silverwind]

I should have noted that those 20x gains were for eslint-plugin-import, maybe this plugin things differently and there are no gains to be had.

Still I guess I could not hurt to have that option available. Willing to PR it.

[SukkaW]

Still I guess I could not hurt to have that option available. Willing to PR it.

Indeed it doesn't hurt, so please do!

[JounQin]

What's the next step on this issue?

cc @silverwind @SukkaW

[silverwind]

Running https://github.com/un-ts/eslint-plugin-import-x/issues/113#issuecomment-2682085698 again with updated dependencies, it seems much improved:

$ TIMING=1 make lint-js
npx eslint --color --max-warnings=0 --ext js,ts,vue web_src/js tools *.js *.ts *.cjs tests/e2e
Rule                                   | Time (ms) | Relative
:--------------------------------------|----------:|--------:
@typescript-eslint/no-deprecated       |  1350.187 |    26.6%
import-x/no-unused-modules             |  1216.474 |    24.0%
vue-scoped-css/no-unused-selector      |   338.322 |     6.7%
import-x/named                         |   283.690 |     5.6%
unicorn/no-unnecessary-polyfills       |   212.447 |     4.2%
@typescript-eslint/no-misused-promises |   199.483 |     3.9%
sonarjs/no-ignored-return              |   122.331 |     2.4%
import-x/no-cycle                      |    93.411 |     1.8%
@stylistic/js/indent                   |    93.134 |     1.8%
@typescript-eslint/no-unused-vars      |    58.379 |     1.2%

So from my viewpoint, this might be resolved, but I'd still suggest we add the disableScc option for users who want to experiment with it.

[JounQin]

So from my viewpoint, this might be resolved, but I'd still suggest we add the disableScc option for users who want to experiment with it.

@silverwind So would you like to raise a PR for it?

[silverwind]

Yes I will. Haven't gotten around to it yet, but it's on my list 😉.

[silverwind]

So I checked and did not find the @rtsao/scc dependency in this repo which was used for SCC at some point in the past.

With that said, there is no reason to have a disableScc option and I suggest we close this, referencing the performance improvement demonstrated in https://github.com/un-ts/eslint-plugin-import-x/issues/113#issuecomment-2891463772.

[JounQin]

So I checked and did not find the @rtsao/scc dependency in this repo which was used for SCC at some point in the past.

https://github.com/un-ts/eslint-plugin-import-x/issues/113#issuecomment-2244143173

#118