[asdf-devel] TRAVERSE being very slow

[Robert Goldman]

On 4/14/10 Apr 14 -8:56 PM, Faré wrote:
> On a large flat system (automatically generated by XCVB from QRes),
> TRAVERSE takes a whole lot of time. More like O(n^2) or O(n^3) than
> either O(n) or O(n log n).
> I suspect suboptimal algorithms are used somewhere, either in
> component lookup or in topological sorting.
> Sigh. The amount of memory consed suggests it's not just lookup time,
> but hugely inefficient intermediate data structures.
> 
> (time (length (asdf::traverse (make-instance 'asdf:load-op)
> (asdf:find-system :qres-ccl-xne)))
> ==>
> took 140,642,274 microseconds (140.642270 seconds) to run
>                     with 8 available CPU cores.
> During that period, 140,484,780 microseconds (140.484790 seconds) were
> spent in user mode
>                     148,010 microseconds (0.148010 seconds) were spent
> in system mode
> 996,129 microseconds (0.996129 seconds) was spent in GC.
>  8,182,948,112 bytes of memory allocated.
> 2748

Just how many files do you have here?

Inside TRAVERSE there are a lot of calls to APPENDF which might indeed
be slow on a very long list.  That's pretty much enough to make this an
O(n^2) operation, if we operate on n components and in the worst case
need to walk to the end of a full plan...

Also, there's this at the end of FORCED:

(setf forced (append (delete 'pruned-op forced :key #'car)
                     (delete 'pruned-op module-ops :key #'car)
                     (list (cons operation c)))))))

That might not be cheap.  Also, I'm not sure whether we're not making
multiple passes over the same sublists, since FORCED is composed by
recursive calls to TRAVERSE.

But clearly I'm not at my best game tonight, and I haven't had time to
very carefully review this code, so take this with a grain of salt.

best,
r