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

[David Turner]

Carl Worth a écrit :
> Hi David. Thanks for joining in on the fun here.
>
>   
Thanks Carl, your invitation is welcomed :-)
> 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.
>
>   
That's exactly what I plan to do, I'm still on the GIT tutorial and 
documentation at the moment though :-)
The patch is an easy way to provide something useful and testable, and 
to foster comments and analysis.

> 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).
>
>   
I'm looking forwards to seeing this new code. I'm pretty curious about 
anything related to
discrete geometry these days.


>>     * 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.
>
>   
I can't provide formal evidence at the moment, but I hope to provide a 
lot of code in the future
that can prove it.

I can give you a small example though: the code used in 
_cairo_spline_decompose to determine if
a bezier is "straight" enough to be approximated by a single line 
fragment tries to check wether the
two control points are within a given distance from the support segment. 
This requires computing
one projection and two eclidian distances, which are quite costly 
operations, even when performed
with doubles.

There are several ways to perform this kind of thresholding using only 
shifts and adds, due to the
nature of the bezier curve; however, I haven't introduced it yet since 
it slightly changes the interpretation
of the "tolerance" parameter, which could modify the number of points 
found in a given spline
decomposition, having the potential to fail the unit test suites which 
do nothing else than matching
exact pixel values.

>>                       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.
I suppose that you mean that it's not possible to tessellate without 
finding intersections, which is
true. However, tessellation is certainly not a requirement to perform 
high-quality anti-aliased
rendering, there are several alternative algorithms that can be used, 
each one having its own
advantages and inconveniences.

Also, tessellation doesn't guarantee perfection, for example the current 
Cairo software
rasterizer uses some form of super-sampling, which doesn't deal 
correctly with ultra-thin
nearly-horizontal lines (a pathological case)

> 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).
>
>   
Another option would be to put the tessellation code within the X 
server, which would only be
used if accellerated quad rendering is available on the hardware. If 
not, a normal non-tessellating
rasterization algorithm would be used to generate alpha horizontal 
spans, with just as much quality
as the current code.

But as you say, it's really too early to consider this.

> 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).
>
>   
First of all, I've said lowering rendering constraints (e.g. getting rid 
of abutting edges, which has nearly
no practical value in an alpha-based world anyway, except if you're 
generating an alpha mask), not
lowering the quality of the output.

Second, you must consider the possibility that some of Cairo's current 
design might not lend itself to that much
performance optimizations, and would be tramped by a factor of 2 or 3 by 
something that works differently.

Also, I don't know how Xara LX achieves its high-quality high-throughput 
results, but I would be
surprised if this involved any tessellation. Hope to see that code soon.

>>     * 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.
>
>   
Thanks for the info, now I really need to dig git :-)

Regards,

- David Turner
- The FreeType Project  (www.freetype.org)


> -Carl
>   


***********************************************************************************
Information contained in this email message is confidential and may be privileged, and is intended only for use of the individual or entity named above. If the reader of this message is not the intended recipient, or the employee or agent responsible to deliver it to the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the postmaster at nds.com and destroy the original message.
***********************************************************************************