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.