Prefer solving for explicitly required dependencies first

[baszalmstra]

In prefix-dev/pixi#1708 it was noted that the solver does not prefer selecting explicitly requested packages. We should experiment with whether adding that to the decision heuristic is possible and doesn't affect performance too badly.

My idea would be to prefer deciding on explicitly required dependencies first before considering transitive dependencies.

@jjerphan @wolfv Do you have thoughts? Have you experimented with this before?

[traversaro]

To provide a bit more context from prefix-dev/pixi#1708 : I guess this could be a point of confusion for people migrating from conda, where (if I am not wrong) this is taked into account.

[jjerphan]

Thank you for opening the discussion.

I have not explored it yet, but I think it is worth it.

[jaimergp]

We do this in conda-libmamba-solver already, to an extent. See how we sort specs being passed to libsolv at https://github.com/conda/conda-libmamba-solver/blob/65788b94f161ace961bcfefe3d8c6cb17c6b0851/conda_libmamba_solver/state.py#L501-L524

[jjerphan]

How about tackling conda/conda#13861 first or in parallel?

[jjerphan]

Similarly to conda as pointed out by Jaime in #60 (comment), mamba defines a custom comparable to sort MatchSpecs before solving the problems

[baszalmstra]

We do this in conda-libmamba-solver already, to an extent. See how we sort specs being passed to libsolv at conda/conda-libmamba-solver@65788b9/conda_libmamba_solver/state.py#L501-L524

This only works because to my knowledge libsolv does not implement a heuristic to determine which requirements to visit first. So the order in which the requirements are passed in is also the order in which libsolve will try to solve the problem.

Resolvo is different in that it can decide to reorder the requirements to solve first based on heuristics. This can drastically speed it up. However, it also means that it might decide to solve a requirement that was provided by the user after first solving for a transitive dependency. The order in which the requirements are provided also doesn't matter (not entirely true but in practice it is).

With #61 , requirements that are requested directly by the user are prioritized over other requirements this has the benefit that user requests are maximized over transitive dependencies. But the input order of requirements is still relatively unimportant.

How about tackling conda/conda#13861 first or in parallel?

We can do this in parallel I think. I still have to measure the performance impact of #61 properly but other than that I dont see any other negative side effects.

[traversaro]

Thanks @baszalmstra !