[no-cycle] a possible reason of the performance issue

[yifanwww]

I noticed that many issues have reported the performance degradation issue with no-cycle. I wasn't sure which issue to comment my findings, so I decided to open a new one.

Relevant issues:

• import/no-cycle, import/namespace and import/no-deprecated speed regression when switching from legacy config to flat config #3148
• Even larger import/no-cycle performance downgrade in 2.30.0 #3047
• no-cycle performance in 2.30 is even worse than 2.27.5 #3060
• eslint-plugin-import upgrade issues on no-cycle #3113

Reason

disableScc: false always traverse the files in node_modules if:

• import/extensions or import/parsers[parser] allow the extensions of the files in node_modules (like .js, .jsx)
• import/ignore doesn't contain node_modules

ignoreExternal: true doesn't work with disableScc: false

Possible Solution

make ignoreExternal: true work with disableScc: false

Tests

maxDepth is set to ∞

1. disableScc: false, ignoreExternal: false, import/ignore doesn't contain node_modules

Rule                                    | Time (ms) | Relative
:---------------------------------------|----------:|--------:
import/no-cycle                         | 12518.457 |    87.0%
@typescript-eslint/no-unsafe-assignment |   624.835 |     4.3%
prettier/prettier                       |   476.463 |     3.3%
@typescript-eslint/no-misused-promises  |    81.059 |     0.6%
import/no-relative-packages             |    80.742 |     0.6%
@typescript-eslint/no-unsafe-return     |    74.946 |     0.5%
import/order                            |    64.003 |     0.4%
import/no-duplicates                    |    51.688 |     0.4%
import/no-self-import                   |    41.741 |     0.3%
@typescript-eslint/naming-convention    |    37.769 |     0.3%

2. disableScc: false, ignoreExternal: true, import/ignore doesn't contain node_modules

Rule                                    | Time (ms) | Relative
:---------------------------------------|----------:|--------:
import/no-cycle                         | 12802.937 |    87.4%
@typescript-eslint/no-unsafe-assignment |   619.635 |     4.2%
prettier/prettier                       |   477.088 |     3.3%
import/no-relative-packages             |    79.608 |     0.5%
@typescript-eslint/no-misused-promises  |    73.669 |     0.5%
import/order                            |    60.475 |     0.4%
@typescript-eslint/no-unsafe-return     |    51.776 |     0.4%
@typescript-eslint/naming-convention    |    47.074 |     0.3%
import/no-duplicates                    |    46.995 |     0.3%
import/no-self-import                   |    43.525 |     0.3%

3. disableScc: false, ignoreExternal: true, import/ignore contains node_modules

Rule                                    | Time (ms) | Relative
:---------------------------------------|----------:|--------:
@typescript-eslint/no-unsafe-assignment |   661.048 |    26.5%
import/no-cycle                         |   563.195 |    22.5%
prettier/prettier                       |   493.190 |    19.7%
import/no-relative-packages             |    81.750 |     3.3%
@typescript-eslint/no-misused-promises  |    77.599 |     3.1%
import/order                            |    62.108 |     2.5%
@typescript-eslint/no-unsafe-return     |    51.690 |     2.1%
import/no-duplicates                    |    50.320 |     2.0%
import/no-self-import                   |    45.716 |     1.8%
@typescript-eslint/naming-convention    |    40.678 |     1.6%

4. disableScc: true, ignoreExternal: false

Rule                                    | Time (ms) | Relative
:---------------------------------------|----------:|--------:
import/no-cycle                         | 35442.592 |    94.9%
@typescript-eslint/no-unsafe-assignment |   601.643 |     1.6%
prettier/prettier                       |   513.087 |     1.4%
import/no-relative-packages             |    81.385 |     0.2%
@typescript-eslint/no-unsafe-return     |    76.666 |     0.2%
@typescript-eslint/no-misused-promises  |    75.370 |     0.2%
import/order                            |    60.338 |     0.2%
import/no-duplicates                    |    57.670 |     0.2%
import/no-self-import                   |    44.472 |     0.1%
@typescript-eslint/naming-convention    |    42.661 |     0.1%

5. disableScc: true, ignoreExternal: true

Rule                                    | Time (ms) | Relative
:---------------------------------------|----------:|--------:
@typescript-eslint/no-unsafe-assignment |   667.579 |    26.3%
import/no-cycle                         |   570.987 |    22.5%
prettier/prettier                       |   500.888 |    19.8%
@typescript-eslint/no-misused-promises  |    83.531 |     3.3%
import/no-relative-packages             |    79.151 |     3.1%
import/order                            |    63.131 |     2.5%
@typescript-eslint/no-unsafe-return     |    53.353 |     2.1%
import/no-duplicates                    |    49.024 |     1.9%
import/no-self-import                   |    46.231 |     1.8%
@typescript-eslint/naming-convention    |    43.361 |     1.7%

From above tests, we can see a huge performance improvement from disableScc: true, ignoreExternal: false to disableScc: false, ignoreExternal: false. However ignoreExternal doesn't work with disableScc: false thus disableScc: false performs worse than disableScc: true, ignoreExternal: true

Reproduce Steps

1. git clone https://github.com/yifanwww/easy-projs.git
2. pnpm install
3. do a basic build: pnpm run build
4. check configs\eslint-config\src\rules\eslint.ts, change no-cycle config, then pnpm run --filter @easy-config/eslint-config build
5. pnpm run --filter @easy-proj/webapp lint with TIMING=0

Limits

I don't have a large enough project to benchmark the performance, so I'm not sure whether the conclusion above would still hold for very large projects.

[ljharb]

ignoreExternal: true doesn't work with disableScc: false

cc @soryy708

this seems like something worth fixing.