[asdf-devel] TRAVERSE being very slow
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 [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] Economic illiteracy often leads one to take for wealth creation or cost reduction what is only a forced displacement of activity, with no primary gain, and a lot of secondary costs and negative side-effects. — Faré
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
participants (2)
-
Faré -
Robert Goldman