Exponential blowup is annoying

I've been spending the last week or so trying to clear out the last few tricky TODO items for a new aptitude release. Aside from clearing out obnoxious old bugs, I had three major features relating to the dependency resolver that I wanted to implement: guided interactive resolution, the ability to produce explanations of dependencies, and the elimination of results that make users go, "Oh, how stupid!"

The first one was pretty straightforward to implement, although it's currently only accessible from the curses UI:



Basically, you can give a thumbs-up ("accept") or thumbs-down ("reject") to individual decisions from the solution; solutions that are generated in the future will be only those that either contain or don't contain that decision. You can always go back and cancel these flags in order to see the solutions that were eliminated by your action.

The second item was also pretty straightforward, although I've only added frontend access from the command-line so far:

pysol-sound-server depends upon libsmpeg0 (>= 0.4.4-7)
 -> Removing pysol-sound-server

python2.3-pygame depends upon libsmpeg0 (>= 0.4.4-7)
 -> Removing python2.3-pygame

tdfsb depends upon libsmpeg0 (>= 0.4.4-7)
 -> Removing tdfsb

python-pygame depends upon python2.3-pygame
 -> Removing python-pygame

pathological depends upon python-pygame
 -> Removing pathological

gltron depends upon libsmpeg0 (>= 0.4.4-7)
 -> Installing gltron 0.70final-6 (unstable)

...

The third item involves the question of whether there's an easy way to eliminate certain types of "redundancies" from solutions: for instance, installing a dependency of a package and then later removing the same package. aptitude was already able to handle some such situations "up front" (reducing the branching factor at the same time), but it wasn't even clear to me if a general solution was possible. In fact, I was stumped on this point for weeks until I realized that the answer was, as usual, much simpler than I thought it would be; it's now implemented and described in the model paper (although I haven't updated the public PDF yet).

So, that brings us to today. I was about to sit down and work on polishing these additions, maybe even going so far as to write test cases for some of them, when I decided to bring my system up-to-date with yesterday's dinstall run.

No solution found within the allotted time.  Try harder? [Y/n]

D'oh! Something about the KDE uploads yesterday triggered a pathological (i.e., exponential) case in aptitude's problem resolver. After reading a lot of of debugging output, the problem seems to be that it was spending too much effort trying to find a "good" solution -- rather than, say, sticking with a solution that just fixed lots of dependencies. Specifically, solutions were only given 300 points for fixing a dependency, and most actions taken by the resolver would actually *decrement* the score of a solution by about 30-50 points. As a result, if the configuration of dependencies was such that the resolver hadn't satisfied some dependencies within about 6-8 steps, the priority of the current "active" solution would actually drop below the priority of the next most interesting solution. As a result, the resolver was behaving more like a breadth-first search (visiting all nodes before reaching a solution) than a depth-first search. Ouch.

The solution I came up with is ad-hoc but it seems to work pretty well: since the problem is that the score drops too fast as new versions are installed, I just adjusted the way solutions are scored. Specifically, it no longer costs anything for the resolver to change the state of an automatically installed package or to install a package that isn't held.

So, how does this tweak perform?

 *** Converged after 524 steps.

Not bad...and the solution it came up with is surprisingly good. I can get even faster results if I make all upgrades and keeps costless or almost costless (converges after 84 steps). Nice!