[cairo] intersect_lines in Bentley Ottman implementation
pcjc2 at cam.ac.uk
Wed Jun 4 04:51:28 PDT 2008
On Sun, 2008-06-01 at 00:56 -0400, Antoine Azar wrote:
> I've profiled a couple of performance tests, and the stroking
> benchmarks reveal the intersect_lines function (part of the Bentley
> Ottman algo) takes up quite some time. The 64/128 bit functions inside
> are costly. I was wondering why we didn't use floats inside
> that function? I tried re-writing it with floats, and the function
> runs 8x faster and the tests still seem to pass. The range of floats
> should be quite enough to handle overflow cases. We might lose a tiny
> bit in the precision of the computation but it's all rounded to the
> nearest integer anyways.
> Comments welcome, if there's no potential problem with that approach
> I'll clean up the code and send a patch.
I'd be interested to see that (no need to clean it up), but in my
profiles, it is mostly:
(below) pixman_rasterize_trapezoid :
pixman_edge_init (and below)
which are hot.
I notice those are using 64 bit fixed point internally.
I'm not sure the sysprof output is as helpful / detailed as it could be,
but oprofile makes my head hurt.
Electrical Engineering Division,
University of Cambridge,
9, JJ Thomson Avenue,
Tel: +44 (0)7729 980173 - (No signal in the lab!)
More information about the cairo