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

[sqal]

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:

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]

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 5cce946 is the commit that slowed down this rule. With fe3121a 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 import-js#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.