isCircularImport complexity impacting Vite performance

[hanford]

Describe the bug

I have a multimillion LOC codebase that includes >25,000 TypeScript modules.

Our development server currently takes around 3 minutes to start.

We discovered that disabling the isCircularImport check, (or simply returning false), cuts startup time by ~60 to 90 seconds. That check performs a DFS, which runs in O(V + E) time, so its cost becomes significant in a very large codebase with deep dependency chains.

ChatGPT suggested implementing a disjoint set, aka union find which could remove the need for recursion and reduce the check to O(1) complexity.

But I think some small tweaks to the current DFS could get us pretty far, so I've started there!

refs: #20085

System Info

Mac OX 15.1
Vite 6.3.2

Used Package Manager

pnpm

Validations

• Follow our Code of Conduct
• Read the Contributing Guidelines.
• Read the docs.
• Check that there isn't already an issue that reports the same bug to avoid creating a duplicate.
• Make sure this is a Vite issue and not a framework-specific issue. For example, if it's a Vue SFC related bug, it should likely be reported to vuejs/core instead.
• Check that this is a concrete bug. For Q&A open a GitHub Discussion or join our Discord Chat Server.
• The provided reproduction is a minimal reproducible example of the bug.