[cairo] perf: long dashed lines

[Vladimir Vukicevic]

On Feb 5, 2008, at 5:18 PM, Behdad Esfahbod wrote:

> On Tue, 2008-02-05 at 16:33 -0800, Vladimir Vukicevic wrote:
>> One more...
>>
>> This is somewhat minor speed-wise, but it may help a lot more on FPU-
>> less platforms.  If the line segment we're dashing is entirely out of
>> bounds, just run the dasher through the loop without calculating each
>> individual dash segment.  (This could be further optimized by  
>> figuring
>> out the total length of the dash pattern, figuring out the remainder
>> from 'remain', and just running with that bit instead of looping over
>> the entire line segment, but that's going to be an even smaller win.)
>
> Looks good.  Go ahead.
>
> Did you get any real numbers on these yet?

Before:

[  0]    image-rgba          long-dashed-lines0-512  163679215    
58.560   58.744  0.45%   5
[  1]    image-rgba          long-dashed-lines3-512  877734466   
314.029  314.516  0.09%   4
[  2]    image-rgba              dashed-borders-1024  796016480   
284.792  285.331  0.12%   5

After, without the additional patch:

[  0]    image-rgba          long-dashed-lines0-512  129712093    
46.406   46.700  0.28%   5
[  1]    image-rgba          long-dashed-lines3-512  307336225   
109.954  110.801  0.43%   5
[  2]    image-rgba              dashed-borders-1024  444903312   
159.170  159.739  0.37%   5

So:

long-dashed-lines0  1.26x faster
long-dashed-lines3  2.87x faster
dashed-borders  1.78x faster

The 0 variant is when the line is entirely in-bounds; for the 3  
variant, the (purely horizontal) line extends 3x in both directions  
(left and right).  Dashed-borders takes a 1024x1024 surface and draws  
ten width x (height*10) dashed rectangles inside it (each one 2px  
narrower than the previous).

As I write this, I realize there's even a yet further optimization  
that can be done -- if we have to check each dash segment, when we get  
to the first one that's in-bounds, after we go out of bounds we can  
stop checking and just fast-forward the dasher.  If we add a bit of  
extra work to both fast forward the dasher and to compute the  
intersect points, we should be able to get the lines3 case to be very  
close to lines0.  Though oddly enough, the followup patch had no  
effect on either of these tests... though on dashed-borders, the one  
fully-out-of-bounds horizontal segment is entirely dwarfed by the huge  
vertical segments.  Doing the optimization I mentioned earlier should  
show up as an additional significant win.  I'll leave out this  
additional patch here for now.

I'll get a fix in for the issues you mentioned on irc as well (pen  
calculation, line_segment name change).

     - vlad