[mcclim-devel] performance of incremental redisplay

[Robert Strandh]

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.  

-- 
Robert Strandh

---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------