Re: Text drawing caches

[Alexander Malmberg]

Fred Kiefer wrote:
> Hi Alexander,
> 
> I just looked through your new code for caching a few text frameworks
> for faster drawing. The code surely is nice, but it does not convince me
> that it is needed. As mostly with optimisation this adds some additional
> complexity and memory usage and I would like to know what we get for it.
> 
> No doubt some caching for this drawing code was needed. The most likely
> usage pattern here is that a cell first asks for the size of its text
> and than draws it.

True, this is a very common idiom, and it seems wasteful. There are
other ways of addressing this, at least for some cases. Eg. NSCell could
cache the size itself, or use its own shared layout manager/text storage
directly instead of via NSStringDrawing.

> So a simple cache of size one should give a big boost
> at almost no addional costs. But it is hard to understand why a bigger
> and complexer cache could improve things much more.

A cache of size one would be no less complex than the current cache. All
the code necessary to check for cache hits would still be necessary, or
we'd risk reusing layout information from a not-quite-identical string.

> In your comments you
> say that some testing was done by people at #gnustep. Would you like to
> share some of the results with us?

That testing was used to determine expected hit/miss rates.

> I am not so much asking for counts on cache hits and misses, this are
> internal data to the implementation, but for overall speed up of text
> drawing applications. For example, and this used to be one of Nicolas
> favourit examples whenever I dared to touch NSCell drawing, what about a
> NSOpenPanel browsing through some big directory structures. How much do
> we gain here?

I've attached a text file with recent benchmarking results.

Some quick comments:

* Cache misses are almost as fast as having no cache at all. Speed is
better with a cache for hit rates >~10% in all cases, and even with no
hits, it's no worse most of the time.

* With the exception of inrect, the old text system has much lower flat
overhead for these calls, but scales _much_ worse (without a cache, new
is ~200000+1000*length of string, old is ~45000+25000*length of string).
Lowering that overhead would be very nice. :)

* Testing for cache hits turned out to be much more expensive than I
thought it would be (can't check reliably against an existing text
storage without setting up a new text storage due to attribute fixups;
alternatives aren't attractive, although I haven't tested all of them
yet). The cache hit size results are pure cache checking overhead.

Given the current amount of overhead (both in the caching, and in the
text system in general), and, well, lack of slowness :), I'm not sure
that caching is worthwhile currently. If the layout overhead could be
lowered, and the caching overhead can't, the gains would shrink pretty
quickly.

OTOH, there are situations where text drawing may be significantly
slower (I'm worried about eg. automatic language/script tagging and font
changes), and caching would help more there. We don't have any such
things currently, though.

> What I do like is that you finally do the NSString drawing without
> building up a NSAttributedString, which was always a bit of a waste.

Yes, a nice part of the reorganization. :)

I have a few other cleanups in there pending. I'm working on a few
different approaches to optimizing things. Depending on which overhead
turns out to be the easiest to get rid of, I may switch to the
cache-less version I have locally. At least the cache is now in cvs, so
if it ever turns out to be useful, it's easy to get it back. :)

- Alexander Malmberg

(clock cycles (on a PII 400mhz) per call)
Old text system                        2004-01-26 hit                2004-01-26 
miss             2004-01-26 no cache
Length    size   atPoint    inRect
  0      24400     25600     41200  x   26000    40000    41600   x   33200    
46400    46400  x   31200    44800    45200   x
  1      71200     88400   1474800  x   48800   184000   185200   x  200400   
333200   334800  x  196000   331200   331200   x
  2      93600    110400   1506400  x   48400   184800   191200   x  201200   
337600   342000  x  200800   334000   332800   x
  3     114000    129200   1486400  x   49200   186000   186800   x  207200   
344000   340000  x  199600   334000   335200   x
  4     139600    155200   1519600  x   49200   188400   189600   x  202000   
336400   337200  x  200800   335600   335600   x
  5     164800    181200   1573200  x   50400   188800   190000   x  204400   
337600   339200  x  202400   336800   339200   x
  8     258400    273600   1615600  x   52000   189600   190800   x  208000   
342000   343200  x  213600   338000   339200   x
 10     300400    316400   1730400  x   52400   192400   193200   x  209600   
343600   344800  x  206400   342000   342400   x
 16     438400    454400   1881200  x   55600   194400   202400   x  214800   
353200   365600  x  212000   349600   359600   x
 32     830000    839200   2248800  x   63600   206800   218800   x  229200   
368800   390400  x  226400   365600   386000   x
 64    1350800   1375200            x   89200   257600   288800   x  277200   
434800   524000  x  255600   403200   472000   x
128    2568800   2595600            x  120800   304400   327600   x  339600   
526000   632400  x  323200   488800   592400   x