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

[Daniel Burrows]

  OK, the core code for promotions is in.  I want to clean up some of
the resolver internals before I go any farther: right now there are two
ways of representing the choices the resolver has made, and it needs to
convert back and forth between them at runtime.  More importantly, it
makes the code hard to follow.  The new system (based on choice and
choice_set) is the way to go IMO: it makes everything a lot more
straightforward, and provides a more straightforward way to add new
types of choices in the future (e.g., "replace this package").  The
new code has been added with an eye to eventually using choice_set or
something like it in the solution class (although I need to figure out
where the "id" value is stored; ideally "action" would become just a
wrapper for choices that adds an ID, but then you still need to convert
to and from it; eh, maybe I can have IDs attached to choices)


  I was a little disappointed with the performance.  It appears to be
visiting fewer search nodes in a simple "safe-upgrade", by about a
factor of 4, but it's not much faster in real time.  End statistics:

open: 5; closed: 4575; defer: 8038; conflict: 15 
real	0m45.121s
user	0m41.787s
sys	0m0.344s

  vs

open: 9; closed: 1511; defer: 2710; conflict: 1
real	0m39.457s
user	0m38.458s
sys	0m0.080s

  That suggests that the promotion set is working to accumulate
information about deferred packages.  However, I wonder whether it's
being accumulated as effectively as possible: perhaps looking at some
logs (tomorrow, when I'm not sleepy) will reveal obvious oversights.
It seems (to me) like an excessive number of steps to decide on 36 new
installs and 18 keeps.

  Another not-at-all unlikely possibility is that the new code just
isn't very efficient.  I eliminated some obvious inefficiencies in the
old code, but probably introduced some new ones.  Also, some of the
obvious inefficiencies might not have been so inefficient after all
(e.g., maybe I replaced a small vector with a balanced tree, where
the vector always has <= 3 elements, or something equally dumb).
I also noticed that there are a number of places where the resolver
does a bunch of redundant computation for sanity-checking; if it
produces a noticeable speed improvement, it might be worth yanking that
out.

  I also tried disabling the new log4cxx stuff completely (i.e.,
compiling it out rather than just turning logging off).  It looks like
there's about a 10% overhead -- bearing in mind that this is a totally
unscientific measurement, that's not too bad considering how useful it
is.  (also kind of surprising, though; I wouldn't think that checking
an integer every once in a while would take so much CPU time!)

  I might try profiling, if I can remember how to profile software on
Linux without it being a horribly miserable experience for all
concerned :).



  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.

  Daniel