[Aptitude-devel] Resolver tiering complete.
dburrows at debian.org
Mon Apr 6 15:57:36 UTC 2009
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. :-)
More information about the Aptitude-devel