[Aptitude-devel] Design notes on producing better (or at least more predictable) resolver results.

[Daniel Burrows]

On Tue, Mar 03, 2009 at 11:32:17PM -0800, Daniel Burrows <dburrows at debian.org> was heard to say:
>   One interesting thing from the search: I ran it with tracing on, and
> I notice that it finds the solution that it ultimately uses quickly,
> then at the end of the log we see:
> 
> INFO  aptitude.resolver.search -  *** Out of solutions after 1985 steps.
> INFO  aptitude.resolver.search -  *** open: 0; closed: 1518; promotions: 4; deferred: 2721
> 
>   That suggests that it isn't doing a very good job of figuring out
> that it can just throw out the rest of the solutions.  Something to
> look into tomorrow.

  Well, that was easy. :-)

INFO  aptitude.resolver.search -  *** Converged after 49 steps.
INFO  aptitude.resolver.search -  *** open: 30; closed: 49; promotions: 3; deferred: 54
real	0m4.333s
user	0m3.980s
sys	0m0.068s

  All I had to do was disable the code that forces the resolver to
prefer solving dependencies that are affected by a "user" constraint
(such as rejecting or approving a version), rather than using its
default heuristic of picking the dependency with the least branching
factor.  I haven't put my finger on exactly what was going on, but
safe-upgrade is heavily based on user constraints, and I'm guessing
there was some pathological interaction that was causing it to never
pick the one dependency that would have made it obvious that all those
packages had to be held back.

  I'm still disturbed by how much time the resolver takes per search
node, but I'll happily take an order-of-magnitude improvement in
runtimes.  Now I just need a bigger upgrade so I can make it slow
again for testing purposes. :)

  Daniel