If the overhead-per-rectangle is pretty cheap, then I won’t bother
to try to coalesce the rectangles. If the overhead is rather high,
I’ll try to coalesce, and if I have more than a certain % dirty, I’ll
just refresh the whole screen.
When I wrote the code for SDL Maelstrom, I did rectangle calesc-ing (sp?)
and refreshed the whole screen if more than a certain % was dirty. The
code to do it was pretty easy, and can be found in the screenlib example
library. I don’t think I actually refresh the whole screen if a certain
% is dirty, I think the coalesc-ing code does that for me, but I haven’t
really tested it a whole lot. Oh - if you improve it, let me know! 
The per-rectangle overhead isn’t that much for the blitting itself, but
is fairly high for the rectangle updating on the X server.
-Sam Lantinga (slouken at devolution.com)