[cairo-bugs] [Bug 43064] stroke performance is super-linear in number of points in the path

[bugzilla-daemon at freedesktop.org]

https://bugs.freedesktop.org/show_bug.cgi?id=43064

Andrea Canciani <ranma42 at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |NEEDINFO

--- Comment #4 from Andrea Canciani <ranma42 at gmail.com> 2011-11-18 07:54:08 PST ---
(In reply to comment #3)
> Drawing straight line between two points shouldn't depend on its background. I
> I suspect drawing time for broken line O(N), where N = number of points. If it
> O(N*sqrt(N)) or something like that, calling stroke and new_path after each

I would wish something like O(N*lg(n)), which IIRC is optimal.
Anything better than that would just mean that you're hitting a special case
that's "easier" than the average one.
(The optimal tessellation and segment intersection algorithms are superlinear,
hence you should expect superlinear performance when stroking)

Can you please provide references which indicate why you expect stroking to be
linear?
(Also, can you perform your test in the range 10000-1000000 step 10000? The
second run of results looks quite stable, which might mean that you're actually
in one of the special "lucky" cases and the first few runs had different
timings because most of the path could fit in faster caches)

> point will give O(N) if sublines approximently equal.
> 
> For range 1000..6000 dots it is true.
> 
> cairo_set_antialias(cr, CAIRO_ANTIALIAS_NONE); do not solve this problem.

Cairo quality and performance when doing non-antialiased drawing can and should
improve, but it is mostly unrelated to your problem (drawing an opaque source
OVER a destination through a non-antialiased stroke using a
non-intersecting/non-antialiased clipping might probably be optimized for your
use case... but it is worth it? how often are such conditions going to be met
in general software?).

> 
> This loop works faster for large N:
> for (i = 1; i < n; ++i)
> {
>     cairo_new_path(cr);
>     cairo_move_to(cr, (double)(i - 1) / n * WIDTH, data[i - 1]);
>     cairo_line_to(cr, (double)i / n * WIDTH, data[i]);
>     cairo_stroke(cr);
> }

Yes, but it computes a different output.
Example: when using a half opaque color, you draw multiple times where the
strokes overlap.
(When using a fully-opaque color, you have the same issue because of
antialiasing, but it is much less visible).

> 
> What do you mean by 'intersections'? If line has intersection, then it should
> be darker here.

No, that's not the definition of stroking in Cairo.
When you perform a stroke in Cairo, the library computes which region is
affected by the stroke, then draws the source through it.

-- 
Configure bugmail: https://bugs.freedesktop.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA Contact for the bug.