[cairo] [cairo-commit] 18 commits - src/cairo-analysis-surface.c src/cairo-clip.c src/cairo-clip-private.h src/cairo-directfb-surface.c src/cairo.h src/cairo-image-surface.c src/cairoint.h src/cairo-paginated-surface.c src/cairo-region.c src/cairo-region-private.h src/cairo-surface.c src/cairo-surface-fallback.c src/cairo-traps.c src/cairo-types-private.h src/cairo-win32-surface.c src/cairo-xcb-surface.c src/cairo-xlib-surface.c src/Makefile.sources

[Soeren Sandmann]

Chris Wilson <chris at chris-wilson.co.uk> writes:

> Preliminary profiling indicates that this is a factor of 6-8 slower for
> region heavy perf cases like dragon and rectangles. (I suspect that is
> due to the elimination of cairo_region_create_rectangles() which is,
> IIRC, an O(n log n) operation as compared to the O(n^2) of iteration
> over the unions.)  

Yes, that does seem to be the case. An obvious fix is to reinstate
cairo_region_create_rectangles(). There is a patch to do that here:

        http://www.daimi.au.dk/~sandmann/reinstate-rectangles.patch

Without that patch, cairo_region_union() is at ~24% on the profile of
dragon. With it, it completely disappears.

There is a possibility other than reinstating, which is to make
cairo_region_union_rectangle() magically fast. This could be done by
maintaining a list of "extra rectangles" inside the region, and then
whenever the region was used for anything other than union_rectangle()
those would first be automatically added to the region.

The appeal of that is that no new API would be needed and people
naively building regions with union_rectangle() would automatically
get good performance.

The drawback is that it makes errors happen out of band. For example
cairo_region_num_rectangles() currently can't fail; if it had to first
validate the region, failing would become possible.

Unfortunately it looks to me like this drawback is fundamental. There
is no way to know ahead of time whether turning n rectangles into a
region will succeed because the union of n rectangles can produce a
region of size O(N^2) [1], not without allocating O(n^2) rectangles
anyway.


Soren

[1] Which also indicates that the worst case complexity of
cairo_region_create_rectangles() is necessarily Omega(n^2) even if
that doesn't happen in practice.