[cairo] Regression in long random polyline rendering time

[Zack Weinberg]

M Joonas Pihlaja <jpihlaja at cc.helsinki.fi> wrote:

> 
> 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.

Is there any chance that we can get optimized PDF/PS/SVG output for
inputs like these? For instance, in the original example, it'd be nice
to wind up with "0 0 100 100 rect fill" in PS rather than duplicating
the exact path that was stroked.  I've written papers with embedded
graphs (not dissimilar to the noisy sinusoid example) that took so long
to render that they tripped the infinite-loop timeout in my printer!

zw