Re: [ft-devel] latest patch file for spline flattening

[GRAHAM ASHER]

That is very interesting and very useful - in fact I think the more surprising 
a 
test is, the more useful it is. I'll have to look into your test case carefully 
as well. I might not be able to do it for a day or to, though.

Where does your test data come from? Actual fonts, cooked up data, or a mixture 
of both?

Best regards,

Graham




----- Original Message ----
From: David Bevan <address@hidden>
To: Graham Asher <address@hidden>
Cc: freetype-devel <address@hidden>
Sent: Tuesday, 7 September, 2010 12:40:21
Subject: RE: [ft-devel] latest patch file for spline flattening


Graham,

Here are the results of my performance testing. I was a bit surprised by the 
results.

In gray_convert_glyph, the time is distributed as follows:

                  OLD    NEW
render_line       20%    15%
render_cubic      15%    33%
render_scanline   14%    10%
split_cubic        6%     9%

OLD is the pre-2.4.0 code; NEW is the latest patch from you.
These percentages are the fraction of time spent in the specific function 
(excluding children).

Including children, we have the following actual times per call for handling 
cubic curves:

                  OLD    NEW
render_cubic      142us  220us

I wasn't expecting your new code to be slower. So I ran my trace code on it 
with 
the following results:

                                 OLD     NEW
average line segs per arc        13.5     11.3
min line segs per arc             2        1
max line segs per arc            32      133

average deviation per line seg    0.29     0.44
min deviation per line seg        0        0
max deviation per line seg       22.2     15.8


Some arcs are creating a very large number of line segments. I expect (though I 
haven't verified) that it is this that is causing the slow-down.

Below is the data for one curve that gets broken down into many tiny line 
segments.

David %^>


4604,0  2080,0  40,2020  40,4496

  40,4496 -> 40,4436
  40,4436 -> 40,4379
  40,4379 -> 41,4321
  41,4321 -> 44,4264
  44,4264 -> 47,4206
  47,4206 -> 51,4149
  51,4149 -> 56,4092
  56,4092 -> 62,4036
  62,4036 -> 68,3979
  68,3979 -> 74,3922
  74,3922 -> 81,3865
  81,3865 -> 90,3811
  90,3811 -> 99,3754
  99,3754 -> 109,3700
  109,3700 -> 119,3645
  119,3645 -> 131,3591
  131,3591 -> 142,3535
  142,3535 -> 154,3481
  154,3481 -> 166,3427
  166,3427 -> 181,3373
  181,3373 -> 195,3319
  195,3319 -> 210,3265
  210,3265 -> 225,3211
  225,3211 -> 243,3160
  243,3160 -> 259,3106
  259,3106 -> 277,3055
  277,3055 -> 295,3002
  295,3002 -> 314,2951
  314,2951 -> 333,2900
  333,2900 -> 354,2849
  354,2849 -> 375,2798
  375,2798 -> 397,2748
  397,2748 -> 418,2697
  418,2697 -> 440,2646
  440,2646 -> 463,2595
  463,2595 -> 487,2547
  487,2547 -> 536,2450
  536,2450 -> 588,2354
  588,2354 -> 641,2258
  641,2258 -> 697,2165
  697,2165 -> 756,2073
  756,2073 -> 817,1984
  817,1984 -> 879,1894
  879,1894 -> 943,1807
  943,1807 -> 1009,1720
  1009,1720 -> 1079,1637
  1079,1637 -> 1149,1554
  1149,1554 -> 1222,1474
  1222,1474 -> 1297,1395
  1297,1395 -> 1375,1319
  1375,1319 -> 1452,1243
  1452,1243 -> 1533,1169
  1533,1169 -> 1614,1097
  1614,1097 -> 1698,1028
  1698,1028 -> 1782,959
  1782,959 -> 1869,894
  1869,894 -> 1958,830
  1958,830 -> 2049,769
  2049,769 -> 2140,708
  2140,708 -> 2233,651
  2233,651 -> 2328,595
  2328,595 -> 2425,543
  2425,543 -> 2522,491
  2522,491 -> 2570,467
  2570,467 -> 2621,443
  2621,443 -> 2671,419
  2671,419 -> 2722,397
  2722,397 -> 2773,375
  2773,375 -> 2825,354
  2825,354 -> 2876,332
  2876,332 -> 2927,311
  2927,311 -> 2978,290
  2978,290 -> 3031,272
  3031,272 -> 3082,253
  3082,253 -> 3136,235
  3136,235 -> 3190,217
  3190,217 -> 3244,202
  3244,202 -> 3297,184
  3297,184 -> 3351,169
  3351,169 -> 3405,154
  3405,154 -> 3460,140
  3460,140 -> 3514,126
  3514,126 -> 3570,114
  3570,114 -> 3625,102
  3625,102 -> 3682,91
  3682,91 -> 3736,79
  3736,79 -> 3793,69
  3793,69 -> 3849,59
  3849,59 -> 3906,50
  3906,50 -> 3963,41
  3963,41 -> 4020,34
  4020,34 -> 4077,28
  4077,28 -> 4136,22
  4136,22 -> 4193,16
  4193,16 -> 4251,11
  4251,11 -> 4308,7
  4308,7 -> 4368,4
  4368,4 -> 4425,1
  4425,1 -> 4485,0
  4485,0 -> 4544,0
  4544,0 -> 4604,0