On 4/16/06, Christophe Rhodes csr21@cam.ac.uk wrote:
Hm. On the one hand, the use of MAP-OVER-OUTPUT-RECORDS is going to lead to O(N^2) behaviour in %TREE-RECOMPUTE-EXTENT* if one output record at a time is added to the graph output record. On the other hand, I think the code for %TREE-RECOMPUTE-EXTENT is completely unnecessary for TREE-OUTPUT-RECORDs (though not for SEQUENCE-OUTPUT-RECORDs). On the gripping hand, I no longer really have much of an idea what's going on at all. You might want to examine the code that draws the graph, maybe trying to insert a graph output record instead of a sequence one if that's possible.
I've finally gotten around to tearing into this issue, adding code to recompute-extent-for-changed-child to handle this particular degenerate behavior. It is considerably faster for me now, although I it still spends a bit more time drawing the arrows than it ought to.
<ramble> I battled similar issues several years ago looking at the text output speed in the interactor pane. Most of the time here was spent drawing the graph arcs. The trouble here was that edge-output-records are created and added to the output history before the edges have been drawn in them. Information about the attached nodes is added, and some time later the arc-drawer is invoked, with the result added to the (previously empty) edge record. As this begins, I had thousands of output records as the immediate children of the graph output record. For each of these, addition of the output from the arc-drawer forces one or more recompute-extent-for-new-child against the edge, which in turn invokes recompute-extent-for-changed-child against the graph.
The existing optimizations in this function were insufficient, forcing the worst case of computing a new bounding rectangle from those of each of the thousands of children. I saw 12,000,000 passes through the inner loop of %tree-recompute-extent* for one rendering of the graph. I've added code to recompute-extent-for-changed-child which handles the case of a previously empty child gaining contents. This differs subtly from the existing case of a child's bounding rectangle growing, because an empty compound-output-record gets a default bounding rectangle of 0,0,0,0 until it gains children, which is obviously bogus, making it look as though the midified child had moved/shrank (these being genuinely painful cases where we do need to examine every child to compute a new bounding rectangle).
If this information can fall directly out of the tree, that is great, because the underlying problem with moving/deleting/resizing large numbers of records still persists to bite the unsuspecting CLIM hacker. Lazily computing the bounding rectangles would mostly solve the problem, provided it doesn't violate the spec somehow. </ramble>