[Aptitude-devel] Resolver tiering complete.

[Daniel Burrows]

On Mon, Mar 30, 2009 at 09:14:56PM -0700, Daniel Burrows <dburrows at debian.org> was heard to say:
>   There's a serious lingering problem with the resolver, though.  After
> implementing all this stuff, I noticed that the GUI upgrade calculator
> was massively slow on my computer (in fact, I thought at first that it
> was failing to terminate).  "safe-upgrade" worked fine.

  Well, that was a brown-paper-bag bug if I ever saw one.

  So, after spending a weeks working on this problem, building auxiliary
tools to visualize resolver searches, writing the groundwork to
implement new optimizations of the search code, and covering my entire
bedroom floor in a printout of a huge dot graph of one resolver search,
I found the problem:

  When I replaced conflicts with promotions, I removed the line of code
that added new conflicts to the conflict set, but I forgot to write the
line of code that added new promotions to the promotion set.
"safe-upgrade" was "faster" because it was actually timing out and
falling back to the classic apt resolver; the GUI just kept going after
the first timeout.

  So, a happy ending, sort of.  The dependency solver is quite fast for
safe-upgrade even on very complex upgrade problems.

  I just wish I had an example that was still intractable -- I want to
hook up promotion backpropagation and see whether it helps out. :-)

  Daniel