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

[GRAHAM ASHER]

With 14,000 glyphs, I imagine that's a CJK font. I think there might be 
different characteristics from a typical Latin font. I think we also ought to 
try out a similar number of Latin glyphs, which could be done by rasterizing 
all 
the glyphs in a Latin font at varying sizes and rotations. In some ways a CJK 
font is probably a more stressful test, because strokes occur at a greater 
number of angles and sizes; but Latin characters should be part of the 
benchmark. I am not trying to foist more work on you; just musing.

Graham



----- Original Message ----
From: David Bevan <address@hidden>
To: GRAHAM ASHER <address@hidden>
Cc: freetype-devel <address@hidden>
Sent: Tuesday, 7 September, 2010 13:52:35
Subject: RE: [ft-devel] latest patch file for spline flattening


After trying various other fonts, I settled on using a single large (14,000 
glyphs; 800,000 Bezier curves) CID-keyed Type 1 font, which seemed to show 
pretty average behaviour.

I'm working on an implementation of something like Hain's algorithm now.

It'll be interesting to see how it compares.

David %^>


-----Original Message-----
From: GRAHAM ASHER [mailto:address@hidden 
Sent: 07 September 2010 13:46
To: David Bevan
Cc: freetype-devel
Subject: Re: [ft-devel] latest patch file for spline flattening

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