[cairo] Adventures in caching

[Owen Taylor]

Today I was working on implementing the central cairo_scaled_font_t
cache:
 
 cairo_font_face_t
 font matrix        => cairo_scaled_font_t
 CTM                                 

And wanted the following behavior:

 - All otherwise referenced cairo_scaled_font_t objects are in the
   cache. If Pango is keeping a cairo_scaled_font_t object around,
   and sets the cairo_font_face_t for it via cairo_set_font_face(),
   the *same* cairo_scaled_font_t should be used.

 - Some number of not otherwise referenced cairo_scaled_font_t
   objects should also be kept in the cache.

   If someone is drawing with a couple of fonts via the toy API,
   then we shouldn't continually be creating new cairo_scaled_font_t
   objects each time they switch fonts. (This is an expensive 
   operation since it involves fontconfig lookups)

Now, this behavior isn't easily implementable with cairo_cache_t.
What cairo_cache_t allows is

 A) A size-limited cache. Once the cache goes over the limit, 
    a random element is removed and replaced.

    When the cache is used this way (e.g., the glyph cache), it usually
    keeps strong references to the values.

 B) A infinite-sized cache (hash table). The cache never automatically
    removes elements.

    When the cache is used this way (e.g. the cache of unscaled fonts
    for the FreeType backend) the cache typically does not hold a 
    reference to the fonts, and fonts are removed from the cache when
    their refcount drops to zero.

It would be possible to extend cairo_cache_t to support the desired 
behavior ... the basic scheme would be:

 - Each element in the cache table has a 'referenced' flag
 - We add 'reference' and 'dereference' functions to 
   cairo_cache_backend_t
 - Only referenced elements contribute to the "total size" of the 
   cache table.
 - Whenever a unreferenced element is retrieved, it's referenced.
 - If referencing an element makes the size go over the limit,
   we unreference a random other element.

But I didn't really want to make cairo_cache_t more complex, so what
I did instead was to use a two level cache. Both caches have the
same key/value setup

 cairo_font_face_t
 font matrix        => cairo_scaled_font_t
 CTM                                 

The outer cache is size limited (to MAX_CACHED_FONTS, currently 24),
and references the values, the inner cache is infinite size and
doesn't reference the values. If the lookup in the outer cache
fails, then we look up in the inner cache and store the result
in the outer cache. If the lookup in the inner cache fails, we
create the scaled font.

This gives the desired behavior ... we keep around MAX_CACHED_FONTS 
even when not otherwise used, but we will always find any currently
loaded cairo_scaled_font_t even if it isn't in that set.

The main extra overhead is the double cache lookup in the case
where the lookup in the outer cache fails ... if an application
is using more than MAX_CACHED_FONTS at once, then this could
be on every font lookup, but that seems unlikely to happen
frequently. 

If it turns out that lookups in the scaled font cache are a 
performance bottleneck, we may want to look at redoing this by
extending cairo_cache_t.

Regards,
					Owen

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050406/776d95c2/attachment.pgp