[cairo] Regression in long random polyline rendering time
M Joonas Pihlaja
jpihlaja at cc.helsinki.fi
Sat Sep 26 14:31:37 PDT 2009
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.
More information about the cairo