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.