[cairo] Regression in long random polyline rendering time
M Joonas Pihlaja
jpihlaja at cc.helsinki.fi
Fri Sep 25 13:54:43 PDT 2009
Hi Emmanuel,
On Fri, 25 Sep 2009, Emmanuel Pacaud wrote:
> Please find attached a sample program that shows a regression in current
> cairo when rendering a long random polyline.
Thanks. This is a pretty nasty regression. Here's a guess at what's
happening:
The example is stroking N line segments in an area of size 100 x 100
pixels for N up to 10000. Things get progressively worse as N grows.
Previously (<= 1.8) cairo would not consider self-intersections in the
stroke when it was stroking lines. In your example for N = 10000
random line segments, one may assume that most line segments are going
to intersect with most other line segments, so on average there are
going to be on the order of 50 million segment-segment intersections
in the image. There are only 100^2 pixels in the image however so for
each pixel you're going to see about 5000ish intersections. That's a
lot of intersections per pixel [1].
In your particular case of using the image surface I suspect what's
happening is that the polygon scan converter's twiddle-an-ordered-list
subroutine is being exercised in new and exciting ways it's not really
been designed for: namely completely reshuffling the list every pixel
due to the high number of intersections. The up shot of the changes
in 1.9 is that your stroked line segments are now more beautiful than
ever before!
As a workaround, trading pure gorgeousness for speed, you can stroke
each individual line segment separately. This brings the times for
cairo master vs. cairo 1.6.4 and 1.8 to about the same. Still a bunch
slower than stroking everything at once with proper joins using cairo
<= 1.8, but not nearly as bad as what you're seeing.
Joonas
[1] Give or take an order of magnitude mod sleepyness. Key point:
lots of them.
More information about the cairo
mailing list