This repository has been archived by the owner on Jan 12, 2024. It is now read-only.
Cycle validation can be very slow with high number of edges #1413
Labels
bug
Something isn't working
Describe the bug
Cycle validation must check not just if there is an edge between generic callables in a cycle, it must check every combination of edges between the callables in the cycle. This requires using a Cartesian product across the edges:
qsharp-compiler/src/QsCompiler/Transformations/CallGraph/CallGraph.cs
Lines 149 to 151 in a268b34
While correct, this can be very slow under some circumstances, such as when there is a type error in a generic cycle with high number of edges. We should investigate how we can optimize this to avoid hitting high time, high memory usage corner cases. With the attached test file that has a compilation error, compile took 8 minutes on my machine to produce 216,002 errors, meanwhile the VSCode extension passively used between 2 GB and 4 GB.
To Reproduce
Steps to reproduce the behavior:
dotnet build
from the cmdlineThe text was updated successfully, but these errors were encountered: