Fwd: Re: [mcclim-devel] Severe performance regression with latest CVS sources?

[Andy Hefner]

On 4/16/06, Christophe Rhodes <csr21 at 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>