[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 #5 from Oleg Bulatov <oleg at bulatov.mobi> 2011-11-18 09:06:15 PST ---
> 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).

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?).

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