On Friday, June 17, 2005, at 12:48 pm, Christophe Rhodes wrote:

Hi,

The new(ish) code for optimizing incremental redisplay by replaying move-overlapping and erase-overlapping records all at once is actually a huge pessimization for many disconnected records: I think that region-union is a precise operation, so the asymptotic complexity of the union operation is O(n^2), and I think the complexity of the replay is O(n^3). Specifically, for my tablature editor, an operation which causes most records to be redraw takes 200 seconds with the current code, with most time (about 77%) being spent in BANDS-OP.

The attached fixes the performance problem by being a little less precise. Is it right?

Disclaimer: I'm not an incremental redisplay expert. Even less wrt the McCLIM incremental redisplay code. So I should probably be quiet on this ;-) However...

Won't this potentially cause large parts of the output to be redrawn unnecessarily? For example:

+-------------------+ | A | <- output record gets changed +-------------------+ | B | +-------------------+ | C | +-------------------+ | D | +-------------------+ ... +-------------------+ | X | <- output record gets changed +-------------------+

The bounding rect of the region union of output records A + X includes the bounds of the output records B - W (so they'll be redrawn I think).

Obviously this is a worst-case type scenario; I don't know if it's worth worrying about, just thought I'd throw it into the mixer.

-Duncan

<ir.diff> Cheers,

Christophe _______________________________________________ mcclim-devel mailing list mcclim-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/mcclim-devel