[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

--- Comment #6 from Andrea Canciani <ranma42 at gmail.com> 2011-11-18 10:32:44 PST ---
(In reply to comment #5)
> > Yes, but it computes a different output.
> Oh.. Now I understand why it should be O(N*lg(N)) :)
> 
> > Also, can you perform your test in the range 10000-1000000 step 10000?
> I perform this test in the range 10000-300000 (on 300000 dots it takes 208
> seconds, so I stop it).

Thanks a lot (oops, I didn't mean to take so much compute-time).
It definitely increases more than I expected, but the overall behavior looks
ok.

> 
> N_INIT=10000; N_STEP=10000; N_MAX=1000000; REPEATS=1
> 10000 dots: 77473.6787 ns
> 20000 dots: 85283.5266 ns
> 30000 dots: 90020.6350 ns
> 40000 dots: 94101.4462 ns
> 50000 dots: 134415.7382 ns
> 60000 dots: 219809.3580 ns
> 70000 dots: 295649.2472 ns
> 80000 dots: 380468.2879 ns
> 90000 dots: 452315.9048 ns
> 100000 dots: 523139.9335 ns
> 110000 dots: 560467.5491 ns
> 120000 dots: 590674.1382 ns
> 130000 dots: 601031.4354 ns
> 140000 dots: 610107.1283 ns
> 150000 dots: 621255.9912 ns
> 160000 dots: 636620.0321 ns
> 170000 dots: 639096.1297 ns
> 180000 dots: 640634.2400 ns
> 190000 dots: 649307.6680 ns
> 200000 dots: 656461.8706 ns
> 210000 dots: 659141.9941 ns
> 220000 dots: 658025.4864 ns
> 230000 dots: 659949.7492 ns
> 240000 dots: 661589.7778 ns
> 250000 dots: 663293.6351 ns
> 260000 dots: 667306.9699 ns
> 270000 dots: 678863.1729 ns
> 280000 dots: 676629.7568 ns
> 290000 dots: 692568.7273 ns
> 300000 dots: 696615.8439 ns
> ^C
> 
> I can rerun it and get all data if required. But timings grows faster N*lg(N)
> (memory reallocation?).

Yes, it might be something like that. Plotting your data shows 2
almost-horizontal parts, with a sudden change in between. Maybe there is room
for improvement in the preallocation size estimation and/or in the reallocation
policy... but, again, in that test you're stroking a huge amount of segments,
so tuning the allocation for such a unusual case might be a bad idea.

(I'm not sure about this, but another possibility is that the change is caused
by a sudden increase in the number of intersections and degeneracies. This is
very possible, because segments are probably almost vertical under those
conditions).

To me, it looks like the bug could already be closed...
Does anybody has a better explanation of the weird performance curve?
Would this kind of benchmark be appropriate for the micro-benchmark suite? (or
do we already have something like this? I remember a couple of similar
benchmarks by Joonas, but I cannot find them in cairo-perf-micro)

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