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

[Daniel Burrows]

On Mon, Jun 29, 2009 at 08:16:04AM -0700, Daniel Burrows <dburrows at debian.org> was heard to say:
>   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.

  I've implemented just this change (flattening all the structures in
sight).

daniel at emurlahn:~/programming/aptitude/head$ time ./src/aptitude -sy safe-upgrade
(...)
real	0m4.141s
user	0m3.944s
sys	0m0.152s
daniel at emurlahn:~/programming/aptitude/head$ 

  That's down from around 22 seconds before, and around 1-2 seconds of
what's left is startup overhead.  I'm inclined to stop performance
optimization here -- there are a few cleanups that would be nice, but
at this point it's probably a waste of time to keep working on this
aspect of the code until someone shows me an example where it's still
too slow.

  According to a heap profiler (massif), peak memory usage in my test
case is now about 16MB (on top of the mmap'ed cache).  If this is true,
I probably don't even need to optimize for memory -- I have a few ideas
of ways the per-step memory overhead could be cut down (just switching
from iterators to raw pointers in the low-level objects would probably
cut it in half or so), but I also don't want to chase shadows or
optimize for Ataris.  :-) 16MB is probably reasonable these days, so
I won't worry about that side of things until I see an example of a
search where too much memory is being used.


  In short, I think I can suspend work on this sub-project and get
back to things users will actually care about. :-P

  Daniel