[Aptitude-devel] Resolver news (it's good)

[Daniel Burrows]

  After hacking on the resolver code for the last few months, I finally
have my changes in a state where they appear to run and produce
identical results (disclaimer: on one test case, albeit a fairly
complicated one; YMMV) to the old code.  The new code is also a bit more
than twice as fast.

  I plan to work on this for a few more weeks before putting it aside:
profiling turns up a few hotspots that look like they should be very
optimizable.  The current top one on my list is the code that, whenever
a new user constraint is added, updates all the solvers in all active
steps to account for that constraint.  According to the profiler, this
is invoked some 800 times and it accounts for about 30-40% of the
run-time.  The reason seems to be that it spawns 100 instances of
increase_solver_tier() each time it's invoked, and those add up fast.
Presumably increase_solver_tier could be made faster; on the other hand,
it's probably easier to just avoid actually invoking it until the last
moment, like I do with promotion applications.  It should be a win for
the same reason.

  The question of why increase_solver_tier itself is slow is also
interesting -- if it was a trivial operation, I'd expect that it would
take a negligible amount of time on a modern processor, even invoked
800,000 times.  It looks like it's spending a lot of time memoizing
dependency solver lists, and that in turn spends most of its time
comparing dependency solver lists -- 13% of the total runtime is spent
just in dep_solvers::operator==.  That isn't surprising; the
implementation of operator== is hideously inefficient.  Changing the
representation of dep solver sets to something flat would help, and
they're so small that it would probably be a flat-out win across the
board.  It was on my speculative TODO, and I think it just got bumped up
in priority.

  (all those numbers are from gprof, so take them with a grain of salt,
   but it's usually ok at pointing out broad cost centers)

  Daniel