NuGet's dependency graph resolution algorithm should scale better for large graphs

[jeffkl]

NuGet Product(s) Affected

MSBuild.exe, dotnet.exe

Current Behavior

NuGet's current dependency graph resolution algorithm can be rather slow for large, complex graphs. It walks the entire tree and for each level expands out every single node. This creates more of a tree representation but also includes duplicates. Consider a popular package, PackageX, that might show up as a common dependency for lots of packages. NuGet will create a graph in memory like this:

ProjectA
 ├─ PackageA
 │  └─ PackageX
 │     ├─ PackageY
 │     └─ PackageZ
 ├─ PackageB
 │  └─ PackageX
 │     ├─ PackageY
 │     └─ PackageZ
 ├─ PackageC
 │  └─ PackageX
 │     ├─ PackageY
 │     └─ PackageZ
 ├─ PackageD
 │  └─ PackageX
 │     ├─ PackageY
 │     └─ PackageZ
 └─ PackageE
    └─ PackageX
       ├─ PackageY
       └─ PackageZ

In restores for large repos internal to Microsoft, individual projects end up with millions of nodes in the graph.

After create the graph, NuGet then walks through the graph N times looking for versions to eclipse, detecting cycles, detecting version conflicts, and detecting downgrades. Walking millions of nodes several times causes restore times for 2,500 projects to be around 15 minutes.

Desired Behavior

We should rewrite the dependency graph resolution algorithm to be linear by having it only walk each node once, resolving versions as it goes. Doing this in a single pass will greatly reduce the amount of time it takes to resolve complex graphs.

Additional Context

No response

[meokullu]

If there are more than one to solve, walk each node once, wouldn't it increase the amount of time? If version conflicts are detecting by comparing only versions of packages, I think it should keep looking on background. User will eventually attempt to solve those too.