[cairo] Regression in long random polyline rendering time

[M Joonas Pihlaja]

On Sat, 26 Sep 2009, Emmanuel Pacaud wrote:

> Le samedi 26 septembre 2009 à 09:45 +0200, Emmanuel Pacaud a écrit : 
> > I have another example which exhibits this regression. It consists in
> > drawing a noisy sinusoid y = sin (x) + rand() * noise_amplitude. You are
> > right, the new rendering is nicer. But sooo slow... And unfortunately,
> > in this case, it's something you may actually have to draw in real
> > life. 
> 
> Here's a test code Joonas wrote that renders a noisy sinusoid. Cairo
> master is slow only when CAIRO_LINE_JOIN_ROUND is used though, with
> n-iterations > 50000.

As a follow-up to cairo-l: we've confirmed the time is being spent in 
both cases in maintaining the active list of the scan converter.  The 
vast majority of time is being spent in merge_unsorted_edges() due to 
an O(N^2) algorithm which usually performs like O(N), but obviously 
not in this case -- or indeed any case where the geometry is very 
fine.  There's a good chance we'll be able to claw ourselves out of 
this hole, hopefully without affecting scan converting simple 
geometries too much.

Joonas