import/no-cycle, import/namespace and import/no-deprecated speed regression when switching from legacy config to flat config

[BPScott]

Possible duplicate of #3113.

I'm using using eslint-plugin-import v2.31.0 and eslint v8.57.1.

I've got a large work project that I'm attempting to migrate from a legacy-style config to a flat config in preparation for an eventual eslint 9 update. Unfortunately it's private and ~6000 files so I can't easily publicly reproduce.
I've found that switching the legacy config to a flat config radically increases the amount of time no-cycle takes to complete. I am already setting disableScc: true.

In order to try to isolate this issue I've tried to create a minimal pair of configs - one in the legacy format, one in the flat format that only runs the no-cycle rule.

eslint-legacy-nocycle.cjs

// Run eslint with this config:
// time ESLINT_USE_FLAT_CONFIG=false TIMING=1 pnpm exec eslint --config 'eslint-legacy-nocycle.cjs' .
const typeScriptExtensions = ['.ts', '.cts', '.mts', '.tsx'];
const allExtensions = [...typeScriptExtensions, '.js', '.jsx', '.mjs', '.cjs'];

module.exports = {
  plugins: [
    'eslint-plugin-import',
    // All of these are only needed for rule definitions, to stop eslint complaining
    // if you mention an rule it doesn't know about in an eslint-disable-next-line comment.
    '@babel/eslint-plugin',
    '@shopify/eslint-plugin',
    '@shopify/eslint-plugin-checkout-web',
    '@typescript-eslint/eslint-plugin',
    'eslint-plugin-compat',
    'eslint-plugin-jest',
    'eslint-plugin-jsx-a11y',
    'eslint-plugin-node',
    'eslint-plugin-promise',
    'eslint-plugin-react',
    'eslint-plugin-react-hooks',
    'eslint-plugin-ssr-friendly',
  ],
  parserOptions: {ecmaVersion: 'latest', sourceType: 'module'},
  settings: {
    'import/extensions': allExtensions,
    'import/external-module-folders': ['node_modules', 'node_modules/@types'],
    'import/parsers': {
      '@typescript-eslint/parser': typeScriptExtensions,
    },
    'import/resolver': {
      typescript: true,
      // node: {extensions: allExtensions},
    },
  },
  rules: {
    'import/no-cycle': ['error', {disableScc: true}],
  },
  overrides: [
    {files: ['*.ts', '*.tsx'], parser: '@typescript-eslint/parser'},
  ],
  ignorePatterns: [
    'node_modules',
    '**/node_modules',
    '**/__generated__',
    'build',
    'coverage',
    'dev/extensions/extension.example.tsx',
    'app/graphql/*types/*',
    '!.storybook',
    'packages/session-store/src/proto',
  ],
};

eslint-flat-nocycle.js

// Run eslint with this config:
// time ESLINT_USE_FLAT_CONFIG=true TIMING=1 pnpm exec eslint --config 'eslint-flat-nocycle.js' .
import _import from 'eslint-plugin-import';
import babelEslintPlugin from '@babel/eslint-plugin';
import shopifyEslintPlugin from '@shopify/eslint-plugin';
import typescriptEslintEslintPlugin from '@typescript-eslint/eslint-plugin';
import compat from 'eslint-plugin-compat';
import jest from 'eslint-plugin-jest';
import jsxA11Y from 'eslint-plugin-jsx-a11y';
import node from 'eslint-plugin-node';
import promise from 'eslint-plugin-promise';
import react from 'eslint-plugin-react';
import reactHooks from 'eslint-plugin-react-hooks';
import ssrFriendly from 'eslint-plugin-ssr-friendly';
import tsParser from '@typescript-eslint/parser';
import shopifyEslintPluginCheckoutWeb from '@shopify/eslint-plugin-checkout-web';

const typeScriptExtensions = ['.ts', '.cts', '.mts', '.tsx'];
const allExtensions = [...typeScriptExtensions, '.js', '.jsx', '.mjs', '.cjs'];

export default [
  {
    ignores: [
      '**/node_modules',
      '**/node_modules',
      '**/__generated__',
      '**/build',
      '**/coverage',
      'dev/extensions/extension.example.tsx',
      'app/graphql/*types/*',
      'packages/session-store/src/proto',
    ],
  },
  {
    plugins: {
      import: _import,
      // All of these are only needed for rule definitions, to stop eslint complaining
      // if you mention an rule it doesn't know about in an eslint-disable-next-line comment.      
      '@babel': babelEslintPlugin,
      '@shopify': shopifyEslintPlugin,
      '@shopify/checkout-web': shopifyEslintPluginCheckoutWeb,
      '@typescript-eslint': typescriptEslintEslintPlugin,
      compat,
      jest,
      'jsx-a11y': jsxA11Y,
      node,
      promise,
      react,
      'react-hooks': reactHooks,
      'ssr-friendly': ssrFriendly,
    },

    languageOptions: {ecmaVersion: 'latest', sourceType: 'module'},
    settings: {
      'import/extensions': allExtensions,
      'import/external-module-folders': ['node_modules', 'node_modules/@types'],
      'import/parsers': {
        '@typescript-eslint/parser': typeScriptExtensions,
      },
      'import/resolver': {
        typescript: true,
        // node: {extensions: allExtensions},
      },
    },
    rules: {
      'import/no-cycle': ['error', {disableScc: true}],
    },
  },
  {
    files: ['**/*.ts', '**/*.tsx'],
    languageOptions: {parser: tsParser},
  },
];

Running these two configs over the full repository sees the flat config take about triple the time of the legacy config:

• Using the legacy config takes 1m37s
• Using the flat config takes 4m47s

This 3x increase is somewhat suprising to me. When I try i use my legacy config with no-cycle enabled it completes in ~2m30s, while when trying to run the flat config version I give up waiting for eslint to complete after 20 minutes - with a fuller config no-cycle seems to take 10x as long.
(ignore the jest/expect-expect some random file in the repo turns that rule on in an in-file directive)

>> time ESLINT_USE_FLAT_CONFIG=false TIMING=1  pnpm exec eslint --config 'eslint-legacy-nocycle.cjs' .

Rule               | Time (ms) | Relative
:------------------|----------:|--------:
import/no-cycle    | 84829.827 |   100.0%
jest/expect-expect |     4.581 |     0.0%
ESLINT_USE_FLAT_CONFIG=false TIMING=1 pnpm exec eslint --config  .  93.28s user 22.82s system 118% cpu 1:37.88 total


>> time ESLINT_USE_FLAT_CONFIG=true TIMING=1  pnpm exec eslint --config 'eslint-flat-nocycle.js' .
Rule               |  Time (ms) | Relative
:------------------|-----------:|--------:
import/no-cycle    | 274185.888 |   100.0%
jest/expect-expect |      4.411 |     0.0%
ESLINT_USE_FLAT_CONFIG=true TIMING=1 pnpm exec eslint --config  .  278.24s user 27.20s system 106% cpu 4:47.76 total

---

When testing using my full config (with no-cycle disabled) I also saw import/namespace and import/no-deprecated regress also.

• import/no-deprecated with a legacy config took 0.8s, with a flat config it took 10.2s
• import/namespace with a legacy config took 11.2s, with a flat config it took 18.3s

// Running my full legacy config, with no-cycle disabled
>> time TIMING=1 pnpm exec eslint .
Rule                              | Time (ms) | Relative
:---------------------------------|----------:|--------:
import/namespace                  | 11214.022 |    28.7%
...
import/no-deprecated              |   824.473 |     2.1%
...
TIMING=1 pnpm exec eslint .  86.09s user 4.66s system 135% cpu 1:07.00 total


// Running my full flat config, with no-cycle disabled
>> time TIMING=1 pnpm exec eslint .
Rule                              | Time (ms) | Relative
:---------------------------------|----------:|--------:
import/namespace                  | 18325.475 |    32.3%
import/no-deprecated              | 10224.395 |    18.0%
...
TIMING=1 pnpm exec eslint .  104.67s user 5.00s system 127% cpu 1:26.22 total

---

As this time regression hurts no-cycle, namespace and no-deprecated, I suspect that this might be something to do with the ExportMapBuilder. I saw that ab0941e makes the cache key used in the ExportMap be constructed differently depending on if a legacy or flat config is used.

I'm not sure how to further debug this to try to isolate the change further. Any thoughts on how I might do so would be appreciated.

[ljharb]

cc @soryy708