no-cycle performance in 2.30 is even worse than 2.27.5

[AnnatarHe]

Hey, Is there any benchmark for the new SCC algorithm?

In a project I am maintaining, 2x more time is used compared with 2.27.5.
it has 544 files project(in monorepo).

Version	2.27.5	2.30.0
Time	~40s	~80s

2.30.0

Rule                                            | Time (ms) | Relative
:-----------------------------------------------|----------:|--------:
import/no-cycle                                 | 58328.676 |    79.2%

2.27.5

Rule                                            | Time (ms) | Relative
:-----------------------------------------------|----------:|--------:
import/no-cycle                                 | 15741.654 |    45.8%

[ljharb]

It depends on the size of the codebase and a number of other factors - try setting the disableScc option to true?

[AnnatarHe]

@ljharb
if set disableScc as true, we are back to 2.27.5. the time is around 40s 😅

this project has around 500 files and 156k lines of code.

Rule                                            | Time (ms) | Relative
:-----------------------------------------------|----------:|--------:
import/no-cycle                                 |  5751.410 |    20.6%

===============================================================================
 Language            Files        Lines         Code     Comments       Blanks
===============================================================================
 JavaScript              5           86           69            6           11
 TypeScript            550       169737       156696         6472         6569
===============================================================================
 Total                 555       169823       156765         6478         6580
===============================================================================

[AnnatarHe]

oh, I just found another similar issue. #3047

[ljharb]

cc @soryy708

[AnnatarHe]

btw, in another project that has more than 7800 files. a 16 cores 32 GB memory server cannot finish in 1 hour, and the node(lint) process took almost 8G memory

[soryy708]

I had a project where SCC clearly made a significant good impact:

#2998 (comment)

With 7k files, and almost 400kloc,

So what is it about your project's configuration that makes it so slow and resource-intensive?

[AnnatarHe]

I posted a result when setting disableScc to true, so I think it's clear that SCC made the performance issue.

And this comment might be the reason: un-ts/eslint-plugin-import-x#113 (comment)

Our project is pretty huge, with over 2 million lines of code... it's quite hard to put it here.

eslint version is 8.39.0

[soryy708]

The linked comment is in eslint-plugin-import-x which is a community fork. If you want them to make a change to their library, please bring it up on their repository.

I doubt that the impact of their proposed replacing of @rtsao/scc with @newdash/graphlib will make much of a difference on performance. Running Tarjan-SCC pre-processing, whether with that library or with another library, will add some work to do so require a performance hit for small projects.

As for your 2mloc project, is that the same that has only 7800 files?
Are you sure the issue is with the choice of SCC library, as opposed to some other step like parsing or ExportMap construction?
Would love to see a profiler output (e.g. flamegraph). How much time are we spending in Tarjan-SCC and how much in other steps?

[soryy708]

It depends on the size of the codebase and a number of other factors - try setting the disableScc option to true?

Created an issue to add disableScc to the docs:

• disableScc option is missing from no-cycle docs #3063

[AnnatarHe]

our project is a mono repo, including many projects. the whole repo is over 2mloc. and one of the largest one is over 7800 files. I'm using a smaller project to test(544 files, the profiling file generated from this project)

here is the profiling file. and using https://www.speedscope.app/ (please let me know once you downloaded, I'll delete it): isolate-0x51a8150-1444136-v8.log.json

[soryy708]

Why are we spending so much time in SCC? It's a linear algorithm. Are we running it many times?
You said mono repo, so I suspect maybe it has something to do with the way ExportMap handles externals?
The projects I tested on didn't have many, so maybe there's a pathology when a monorepo has many eslint/ts configs?

[soryy708]

#3068

[soryy708]

@AnnatarHe Please try version 2.31.0, it includes the fix from #3068.
Is performance better with/without disableScc?

[AnnatarHe]

@soryy708 no significant difference. so it looks like the new version brings the performance back to previous version

disableScc: true

Rule                                            |  Time (ms) | Relative
:-----------------------------------------------|-----------:|--------:
import/no-cycle                                 | 110489.719 |    90.2%
prettier/prettier                               |   9351.288 |     7.6%
import/namespace                                |    834.045 |     0.7%
unused-imports/no-unused-imports                |    531.654 |     0.4%


Executed in  137.36 secs    fish           external
   usr time  163.09 secs  306.00 micros  163.09 secs
   sys time   11.42 secs  173.00 micros   11.42 secs

disableScc: false

Rule                                            |  Time (ms) | Relative
:-----------------------------------------------|-----------:|--------:
import/no-cycle                                 | 116099.013 |    90.8%
prettier/prettier                               |   8842.955 |     6.9%
import/namespace                                |    924.044 |     0.7%
unused-imports/no-unused-imports                |    561.242 |     0.4%

Executed in  143.02 secs    fish           external
   usr time  171.97 secs  327.00 micros  171.97 secs
   sys time   11.48 secs  184.00 micros   11.48 secs

[soryy708]

@AnnatarHe pardon I think I don't follow, which one of the multiple projects mentioned was this recent benchmark in?
Also if we're talking specifically about no-cycle, lets isolate the variables to just that, by disabling all other lint rules, so that we get more repeatable results.

When you say

the new version brings the performance back to previous version

which version do you mean?
did performance return to the same as you had in 2.27.5?