[cairo] Where's the bottleneck in using glitz/cairo/librsvg?

[Carl Worth]

On Fri, 09 Jun 2006 11:16:11 +0200, David Turner wrote:
> 
> Hello Mirco, and all Cairo hackers,

Hi David. Thanks for joining in on the fun here.

> I've taken the liberty of using your original "cairo-dock" program to 
> profile Cairo.

I appreciate this very much, (as I imagine Mirco does as well since he
asked for help in finding bottlenecks).

> You'll find the patch, the modified program and a lot more information 
> at the
> following page:
> 
>   http://turnerdavid.neuf.fr/desktop/index.html

Thanks for converting the program to have a benchmark mode. That's
exactly what I would have done if I had sat down with this.

As for the performance patch you've got so far, there are at least two
things that need to be done before this can go in to cairo:

1) Just drop the "#ifdef DAVID" stuff. We've got enough help from git
   in keeping different branches separate that this only gets in the
   way.

2) You've got an 8-point bulleted list of things your patch does so
   far. I would greatly prefer to see a comparable number of patches
   rather than one. Incidentally, installing git, (as you mentioned
   you plan to do), actually makes this much easier to achieve. You
   can just "git commit -a" each change as you implement it, then do
   something like:

	git format-patch --stdout origin.. > dturner_performance.patchset

   to still get the convenience of a single file that you can mail to
   the list, but with the benefit that it will be applied (via git-am)
   as a series of independent commits with their own commit messages.

> I believe there are still very important opportunities for optimization,
> but these will require very hard work. And I don't have that much free 
> time :-)

Yes. And fortunately, this is the exact work I'm already planning on
working on full-time over the next several months. If you don't mind,
I'll comment a bit on the summary points you make in your writeup:

> As a final note, keep in mind that it should be possible to speed up
> Cairo even more by working on the following highly non-trivial
> points:
> 
>     * Rewrite the tesselator so that it uses a more efficient
>       algorithm.

The tessellator is something I've been itching to rewrite since about
forever, (long before 1.0), but I've been busy just getting the print
backends to work well. The current code is known to not be robust and
to have horrible performance characteristics, (something like O(n**3)
for what should be more like O(n log n)). I've got a plan in place for
this, and I've even got a prototype mostly done already, (it's already
much better-performing (algorithmically speaking), but there's a bit
more work to be done for getting the better robustness).

>     * Change the pixman gradient computations to avoid many function
>       calls and array scans per pixel.

Yes. We've seen the gradient computation hit the top of profiles
before. There are several things that could be done here:

	o Make the gradients waste less time computing source pixels
	  that will never be used.

	o Make the computation of each source pixel more efficient.

	o Implement some caching of gradient surfaces.

	o Just go apply the existing patch from David Reveman that
	  switches from pixman gradients to X server gradients.

There's still some exploration needed to find what the most important
things to focus on here should be, (except for the last point which is
simple and obvious I think).

>     * Cairo's 'pixel-perfection' comes at a very high-price in terms
>       of performance,

Can you provide evidence to back up this assertion? I'm not aware of
any. Otherwise, I'll just focus on the remainder of the paragraph
which does have some good points.

>                       mainly because tessellating polygons is such a
>       CPU-intensive operation, no matter how you implement it.

Yes, tessellation is expensive. The hardest part of it, though, comes
down to identifying all intersections among a set of line segments. I
don't know any approach that avoids that piece. (So any time I've
talked about the "new tessellator" you can imagine I said "new segment
intersector" since that new algorithm implementation will be useful
whether or not we end up with tessellation in cairo).

But tessellation does have other costs in terms of a potential
increase in data being sent to describe all the primitive polygons, as
well as extra work being necessary during rasterization that could be
avoided if we rasterized directly from the intersection finder, rather
than emitting trapezoids.

The trapezoid interface in cairo came to be because of the trapezoid
interface in Render. And there, it was invented to provide access to
hardware-based rasterization. If we had that, I think the overhead of
using tessellation could end up being very worth it.

However, we're not currently getting any hardware rasterization in
cairo, and I haven't seen any evidence that it will be appearing
soon. So we're paying a performance price here without a benefit. The
answer may very well be to stop emitting trapezoids and just have
cairo compute rasterized masks directly from the complex polygons,
(via the new and improved intersection-finding code).

Significantly, though, this performance benefit should be possible
without any adverse effect on the output quality.

>       However, it's possible to render high-quality anti-aliased
>       vectors a lot faster if you slightly lower rendering
>       constraints. I believe many users would likely prefer the
>       alternative algorithms (e.g. when rendering SVG icons), if given
>       a choice.

It's not worth talking about lowering the output quality before we
have the a high-speed implementation for our current high-quality
output. And considering that we have some dog-slow algorithms here
that have never seen any optimization, let's do that first, and then
see if there is any need for knobs to control a quality vs. speed
performance knob. (I really don't think it will be necessary. Software
such as Xara LX shows that high-quality results can be achieved with
good performance in an all-software environment).

>                 However, this would go contrary to the current
>       rendering model which is totally based on trapezoids, which are
>       not the most efficient data structure to do that (though they're
>       very accurate). Changing this has very deep consequences on the
>       rendering stack, reaching the X11 Server !.

As I described above, we can explore not using trapezoids without
giving up output quality. And we might just ignore the
CompositeTrapezoids parts of the Render extension, but it's not
obvious to me yet whether any new support would be needed in the X
server for this kind of approach.

But that's enough prose and hand-waving from me on the topic. Next
we'll need some numbers to attach to all this stuff, which brings us
to...

>     * There are also several other aspects of Cairo that need a good
>       benchmark and profiling to be optimized. If you have some
>       working code, don't hesitate to send them to me.

There are at least two prior efforts at putting together a cairo
benchmarking suite. One called cairo-benchmarks was started by Billy
Biggs last August:

http://lists.freedesktop.org/archives/cairo/2005-August/004929.html

It had been imported into CVS at some point, but it looks like
something may be amiss with it currently (webcvs is reporting nothing
but dead files). Anyway, it would be available here:

http://cvs.cairographics.org/cairo-benchmarks/

More recently, in March Vladimir Vukicevic put together the second
suite called cairo-bench. His announcement is here:

http://lists.freedesktop.org/archives/cairo/2006-March/006547.html

which contains a pointer to the git tree housing it.

I don't know that either effort has ever been applied to cairo's
development in a systematic way. But that's exactly my plan for as
soon as cairo 1.2 is out the door. Then, instead of using the cairo
test suite on a daily basis to track the improvement of cairo's
quality, I plan to setup a canonical suite of benchmarks for tracking
the improvement of cairo's performance as development continues.

Oh, and Bryce Harrington has recently started looking into setting up
a system to automatically run cairo's test suite on a regular basis
for tracking. It would be nice to have a similar automatic system, (or
several, for different platforms, backends, etc.) for tracking the
improvement of cairo's performance.

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20060609/746ea85c/attachment.pgp