Restore: improve performance by avoiding linear search in the implementation of the "Nearest wins" rule

[marcin-krystianc]

Details about Problem

I think that the current implementation of nearest wins rule can be improved so it has better performance.

Each time the graph walking algorithm is about to visit a child node (a dependency of a node) it checks whether that child node is not eclipsed or downgraded by any of the dependencies of parent nodes (direct and transitive). If a node is being ignored then all remaining dependencies on that branch of the graph are also ignored which is the key benefit of the "nearest wins" rule. But, when we look closer at the code we can spot that it is implemented using linear search which is potentially bad for performance:

private Func<LibraryRange, (DependencyResult dependencyResult, LibraryDependency conflictingDependency)> ChainPredicate(Func<LibraryRange, (DependencyResult dependencyResult, LibraryDependency conflictingDependency)> predicate, GraphNode<RemoteResolveResult> node, LibraryDependency dependency)
{
    var item = node.Item;

    return library =>
    {
        if (StringComparer.OrdinalIgnoreCase.Equals(item.Data.Match.Library.Name, library.Name))
        {
            return (DependencyResult.Cycle, null);
        }

        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        // LINEAR SEARCH
        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        foreach (var d in item.Data.Dependencies)
        {
            if (d != dependency && library.IsEclipsedBy(d.LibraryRange))
            {
                if (d.LibraryRange.VersionRange != null &&
                    library.VersionRange != null &&
                    !IsGreaterThanOrEqualTo(d.LibraryRange.VersionRange, library.VersionRange))
                {
                    return (DependencyResult.PotentiallyDowngraded, d);
                }

                return (DependencyResult.Eclipsed, d);
            }
        }

        return predicate(library);
    };
}

On the flip side, linear search is not always worse than a dictionary lookup - it all depends on the average number elements the linear search needs to go through. For narrow graphs, i.e. graphs where average number of dependencies of each node is low, the linear search can be equally fast or even outperform the dictionary lookup. Thus any change in this area needs to be well benchmarked using a representative set of solutions.

[erdembayar]

@nkolev92 Do you know why this issue is in Review stage?

[nkolev92]

It had a PR that got closed, and never got moved back cause it wasn't assigned ot anyone.