[Aptitude-devel] The resolver is functional.
dburrows at debian.org
Fri Jun 5 14:50:29 UTC 2009
On Thu, Jun 04, 2009 at 09:57:22AM -0700, Daniel Burrows <dburrows at debian.org> was heard to say:
> But performance is > utterly lousy. I guess I'll probably have to
> profile it to see why: I wasn't sure it would be hugely faster, but
> orders of magnitude slower seems like I messed up part of the design.
I haven't been able to do a complete profile run, because the program
exhausts my memory first. I have been able to get a heap profile, and
it confirms my suspicion: it's allocating utterly ridiculous amounts of
memory to store the global reverse index of steps by what they contain.
Luckily, there's a pretty straightforward optimization here that I
only left out because I thought it wouldn't be necessary (silly me).
Instead of repeating the entire list of choices at each step in that
reverse index, I can store only the new choices, along with a set of the
choices that have been dropped. When something needs all the steps
associated with a choice, it can start at each step where the choice was
first added, then recursively walk all the descendants of that step,
pruning each branch when the choice shows up as having been dropped in
That should be a lot more reasonable: it'll allocate far less memory,
and it means that the cost of traversing the tree is mostly paid at the
time of traversal (which should be rare), rather than forcing every step
to do costly work to keep a big reverse index up to date.
This will also make everything run faster, but I doubt it's the only
performance problem I need to find. I'm also curious why the memory
overhead was *so* large -- my back-of-the-envelope estimates don't
explain why it's allocating a megabyte every few steps (!). That may be
partly pile-up from the slightly inefficient way the low-level
structures are allocated (one of the other outstanding optimizations I
have is to fix that), but it still seems like an awful lot.
More information about the Aptitude-devel