Skip to content
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

Open
swernli opened this issue Apr 15, 2022 · 0 comments
Open

Cycle validation can be very slow with high number of edges #1413

swernli opened this issue Apr 15, 2022 · 0 comments
Labels
bug Something isn't working

Comments

@swernli
Copy link
Contributor

swernli commented Apr 15, 2022

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:

var cycles = this.GetCallCycles()
.Where(cycleSelector)
.SelectMany(x => CartesianProduct(this.GetEdgesWithNames(x).Reverse()));

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:

  1. Open the attached HighEdgeCycles.qs.txt Q# file (remove the .txt extension) in VSCode and put it in a csproj
  2. Perform a dotnet build from the cmdline
  3. Note the memory usage of the Microsoft.Quantum.QsLanguageServer and the high number of errors produced by the build.
@swernli swernli added bug Something isn't working needs triage An initial review by a maintainer is needed labels Apr 15, 2022
@bettinaheim bettinaheim removed the needs triage An initial review by a maintainer is needed label Apr 28, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants