[Aptitude-devel] Resolver update

[Daniel Burrows]

  Coding on the resolver has slowed down partly because I took a few
days off, and partly because it's gotten to the point where it takes
longer to figure out what to do next than to do it.

  The resolver is now optimized to the point that it's as fast as the
pre-optimized version ;-).  This is mostly because I've applied some
optimizations that existed in the previous version, but weren't worked
into the new code.  Hopefully this doesn't mean that it was completely
nutty to restructure everything.


  The current biggest time sink, based on profile runs (although note
that I have only one large input set that I'm using for all of these),
appears to be the code that maintains step tiers as promotions are
added to the promotion set.

  In the previous implementation, we handled promotions by retesting the
step against the entire promotion set when it was being processed.  This
requires time proportional to the number of actions performed by the
step, plus the number of promotions that each action intersects.  (note:
if two separate actions intersect the same promotion, count it twice)

  In the new implementation, whenever a new promotion is inserted, we
test it against all the steps that have been generated.  This requires
time proportional to the size of the promotion, plus the number of steps
that each action contained in the promotion intersects.


  The previous implementation is efficient when most promotions don't
overlap most steps, and the size of a step is much smaller than the size
of the set of active promotions.

  The new implementation is efficient when ... well, it really isn't.
The idea was that if the promotion is small (say, 2 choices large), then
we only pay for the choices it contains.  The problem with this idea is
that we have to find all the steps that it intersects, and there might
be a *lot* of them, test whether each one contains the promotion, and
increase the appropriate solver tiers if it does.  This is expensive and
requires a lot of book-keeping to pull off.  Also, it requires us to pay
for lots of steps that we might not ever return, because they already
come after another step that the user will pick as a solution.  All that
time is simply wasted.


  I think it will be important to find a better way of doing this.  One
option is to simply revert to what we were doing before: when a step is
pulled from the queue, match it against the full promotion set and apply
any promotions that it hits.  This might be good enough, especially if I
combine it with a change to base the promotion set on hash tables
(courtesy of Boost).

  A second idea is to do what we're doing now (sort of), but lazily.
Maintain a queue of new promotions that have been added to the store.

    Promotion 1 --> Promotion 2 --> Promotion 3 --> X
    ^               ^               ^               ^
    |               |               |               |
    Step A          Step B          Step C          Step D

  Each step contains a link to the location in the promotion queue that
was active when it was created.  When we examine a step, we apply every
promotion from its link to the end of the queue (X above) to the step.
So, for instance, when we examine step B, we'll process promotions 2 and
3 against it.  If step B produces its own promotion, it will be inserted
into the queue at X and step D will now point to the new promotion.  In
contrast, under the current algorithm, a new promotion produced at step
B would cause the resolver to scan the search tree for intersections and
apply the promotion immediately to them.

  This is similar to the current algorithm with the work rearranged and
made lazier, but it does more work overall (doesn't attempt to
pre-filter irrelevant promotions), and it will process a potentially
very large queue of promotions if it needs to examine an old step.  It
also has a small potential risk of not detecting conflicts as early as
possible (the current algorithm could theoretically find dead-ends
without ever examining them, which in turn could be propagated to
generate even more dead-ends).

  A third idea I have is a hybrid.  Recognizing what the various costs
are, the goal is to use the queue I described above if we have reason to
believe it will be cheaper, and to fall back to a test against the full
promotion set if not.  To do this, augment the elements of the queue
above with a note indicating the *total size of all promotions up to and
including the current one*.

    Promotion 1 --> Promotion 2 --> Promotion 3 --> X
    (4 choices)     (15 choices)    (1 choice)
    Total: 0        Total: 4        Total: 19       Total: 20
    ^               ^               ^               ^
    |               |               |               |
    Step A          Step B          Step C          Step D
    (0 choices)     (5 choices)     (4 choices)     (7 choices)

  When processing a step, we check how large the promotions between it
and the end of the promotion queue are.  That's simply the total of X
minus the total of the promotion pointed to by the step, so for instance
for step C, we see that the promotion between it and X contains only 1
choices, while for step A, we see that the promotions between it and X
contain 20 choices.

  If the promotions contain fewer choices in total than the step itself
(including both actions and solvers), then it's probably better to
process them individually.  Otherwise, the resolver should check the
global promotion set.  So for step A, we would check the whole set of
promotions (since 20 > 0), but for step C, we would just apply the one
promotion that's left in the list (since 1 < 4).

  One other idea would be to check against some constant multiple of the
step size, reflecting the fact that it's a bit costly to check the
promotion set.  Also, I suspect that "small" promotion queues (say, less
than 5-10 choices) should always be processed in full, even if the step
is smaller.  The idea there is just that it's not that expensive to
apply a few promotions to a step.  These are just speculative notions at
the moment, though; I'll wait and see how things turn out before I try
to put too many curlicues on this.

  Daniel