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