search

mamba-org / resolvo

Fast package resolver written in Rust (CDCL based SAT solving)
BSD 3-Clause "New" or "Revised" License
154 stars 13 forks source link

Prefer solving for explicitly required dependencies first #60

Closed baszalmstra closed 3 days ago

baszalmstra commented 1 month ago

In https://github.com/prefix-dev/pixi/issues/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 commented 1 month ago

To provide a bit more context from https://github.com/prefix-dev/pixi/issues/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 commented 1 month ago

Thank you for opening the discussion.

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

jaimergp commented 1 month ago

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 commented 1 month ago

How about tackling https://github.com/conda/conda/issues/13861 first or in parallel?

jjerphan commented 1 month ago

Similarly to conda as pointed out by Jaime in https://github.com/mamba-org/resolvo/issues/60#issuecomment-2284082332, mamba defines a custom comparable to sort MatchSpecs before solving the problems

baszalmstra commented 1 month ago

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 https://github.com/conda/conda/issues/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 commented 3 days ago

Thanks @baszalmstra !