The slowness of my example from the other day seems to be caused by the fact that each top-level output record (of which there are 1000 in my example) is moved individually, and moving an output record triggers a call to recompute-extent-for-changed-child. The parent then scans all the children to compute the new bounding rectangle, resulting in quadratic behavior.
The solution to this problem seems to be to realize that incremental redisplay must traverse all the output records anyway (to see what has changed), and so it would be a better idea to put off the computation of the bounding rectangle until the end of this entire process.
I maintain my previous analysis that it would be a better idea to store relative positions in output records, so that moving an output record does not require traversing its children.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Robert Strandh wrote:
The slowness of my example from the other day seems to be caused by the fact that each top-level output record (of which there are 1000 in my example) is moved individually, and moving an output record triggers a call to recompute-extent-for-changed-child. The parent then scans all the children to compute the new bounding rectangle, resulting in quadratic behavior.
The solution to this problem seems to be to realize that incremental redisplay must traverse all the output records anyway (to see what has changed), and so it would be a better idea to put off the computation of the bounding rectangle until the end of this entire process.
I maintain my previous analysis that it would be a better idea to store relative positions in output records, so that moving an output record does not require traversing its children.
It's interesting to note that early versions of CLIM did store the child positions as relative coordinates; it was considered an important optimization to move to fixed coordinates! :) I believe that relative coordinates were identified as a bottleneck in the comparison part of updating-output.
Trade-offs that were important 20 years ago may not be relevant today...
Tim
On 1/2/07, Robert Strandh strandh@labri.fr wrote:
I maintain my previous analysis that it would be a better idea to store relative positions in output records, so that moving an output record does not require traversing its children.
I agree completely. Use of absolute coordinates here is a particularly boneheaded aspect of CLIM, particularly in contrast with the very nice sheet/windowing functions based on transformations.
The solution to this problem seems to be to realize that incremental redisplay must traverse all the output records anyway (to see what has changed), and so it would be a better idea to put off the computation of the bounding rectangle until the end of this entire process.
Do you think it makes sense to generally make bounding rectangles computed lazily, caching them? Having ran into quadratic behavior a couple times myself (during normal text output, and in the grapher), this seemed like the logical approach.
Andy Hefner writes:
The solution to this problem seems to be to realize that incremental redisplay must traverse all the output records anyway (to see what has changed), and so it would be a better idea to put off the computation of the bounding rectangle until the end of this entire process.
Do you think it makes sense to generally make bounding rectangles computed lazily, caching them? Having ran into quadratic behavior a couple times myself (during normal text output, and in the grapher), this seemed like the logical approach.
I don't think so (depending on what you mean by "lazily"). There are essentially two kinds of applications as far as I can see. The first type has :display-time nil or t and has commands that issue calls to drawing functions. The second type has :display-time :command-loop and runs a large display function each time around the command loop, possibly using incremental display.
The first type of application is not likely to run into quadratic behavior if the bounding rectangle is computed immediately. In the general case (say if you delete an output record), computing the bounding rectangle will have to go through all the output records and compute min and max coordinates, but there are special cases where you only add an output record, where this can be avoided, and I think the first type of application is like that.
The second type of application is more likely to move or delete output records, that makes it necessary to go through all output records to determine the bounding rectangle. For this type of application it would just be easier to compute the bounding rectangle at the end of the command loop.
In fact, I don't think we would take a performance hit for the first type of application either if we would just go through all output records at the end of the command loop, but perhaps to be on the safe side, we could do it that way only of :display-time is :command-loop.
On 1/3/07, Robert Strandh strandh@labri.fr wrote:
Andy Hefner writes:
Do you think it makes sense to generally make bounding rectangles computed lazily, caching them? Having ran into quadratic behavior a couple times myself (during normal text output, and in the grapher), this seemed like the logical approach.
I don't think so (depending on what you mean by "lazily"). There are essentially two kinds of applications as far as I can see. The first type has :display-time nil or t and has commands that issue calls to drawing functions. The second type has :display-time :command-loop and runs a large display function each time around the command loop, possibly using incremental display.
To clarify, I imagined setting the coordinates slot of the bounding rectangle to nil as a signal that the bounding rectangle needs to be recomputed. Recompute-extent-for-changed-child can set the slot to nil rather than immediately recomputing the bounding rectangle, and bounding-rectangle* checks for the nil case and can call tree-recompute-extent itself, saving the value in the slot (until the next change that invalidates it). That way the bounding rectangle is only computed when it is needed, and moving/deleting a number of records does not cause it to be recomputed each time only to be discarded.
The second type of application is more likely to move or delete output records, that makes it necessary to go through all output records to determine the bounding rectangle. For this type of application it would just be easier to compute the bounding rectangle at the end of the command loop.
Can you elaborate on when and for what records recomputing of bounding rectangles would be supressed? Formatting utilities such as surrounding-output-with-border and the table formatter require correct bounding rectangles for their contained output, the process of producing which may at some point require a call to tree-recompute-extent. Restricting this to the topmost (stream-output-history) record would be safer and sufficient for some applications, but others may encounter the same problems deeper in the output tree.
Andy Hefner writes:
To clarify, I imagined setting the coordinates slot of the bounding rectangle to nil as a signal that the bounding rectangle needs to be recomputed. Recompute-extent-for-changed-child can set the slot to nil rather than immediately recomputing the bounding rectangle, and bounding-rectangle* checks for the nil case and can call tree-recompute-extent itself, saving the value in the slot (until the next change that invalidates it). That way the bounding rectangle is only computed when it is needed, and moving/deleting a number of records does not cause it to be recomputed each time only to be discarded.
This sounds like a good idea, and easy to implement.
The second type of application is more likely to move or delete output records, that makes it necessary to go through all output records to determine the bounding rectangle. For this type of application it would just be easier to compute the bounding rectangle at the end of the command loop.
Can you elaborate on when and for what records recomputing of bounding rectangles would be supressed? Formatting utilities such as surrounding-output-with-border and the table formatter require correct bounding rectangles for their contained output, the process of producing which may at some point require a call to tree-recompute-extent. Restricting this to the topmost (stream-output-history) record would be safer and sufficient for some applications, but others may encounter the same problems deeper in the output tree.
I haven't thought this through completely, but it seems to me that even table formatting only needs to be computed right before the output is to be replayed. What I am suggesting is to suppress all such computations and just go through the entire tree once, right before replay. Doing that would have to invoke the table-formatting code, of course. But again, I don't know for sure that it will work.
-
Andy Hefner -
Robert Strandh -
Timothy Moore