On Thu, Jun 04, 2009 at 09:57:22AM -0700, Daniel Burrows <[email protected]> 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 branch. 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. Daniel _______________________________________________ Aptitude-devel mailing list [email protected] http://lists.alioth.debian.org/mailman/listinfo/aptitude-devel
