[cairo] Regression in long random polyline rendering time

[M Joonas Pihlaja]

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.