[scaled-font] Lean and mean global glyph cache.

Jeff Muizelaar pointed out that the severe overallocation implicit in the
current version of the glyph cache is obnoxious and prevents him from
accepting the trunk into Mozilla. Jeff captured a trace of scaled font
and glyph usage during a tp run and presented his analysis in
http://lists.cairographics.org/archives/cairo/2009-March/016706.html

Using that data, the design was changed to allocate pages of glyphs from a
capped global pool but with per-font hash tables. This should allow the
glyph cache to have tight memory bounds with fair allocation according to
usage. Note that both the old design and the 1.8 glyph cache had
essentially unbounded memory constraints, since each scaled font could
cache up to 256 glyphs (1.8) or had a reserved page (old), with no limit
on the number of active fonts. Currently the eviction policy is a simple
random strategy, this gives a 'fair' allotment of the cache, but a LRU
variant might perform better.

On a sample run of firefox-3.0.7 perusing BBC news in 32 languages:
1.8:  cache allocation 8190x, ~1.2 MiB; elapsed 88.2s
old:  cache allocation 771x, ~13.8 MiB; elapsed 81.7s
lean: cache allocation 433x,  ~1.8 MiB; elapsed 82.4s

1 files changed, 1 insertions, 4 deletions

diff --git a/src/cairo-cache-private.h b/src/cairo-cache-private.h
index 8ad0c774a..25858e544 100644
--- a/src/cairo-cache-private.h
+++ b/src/cairo-cache-private.h
@@ -97,6 +97,7 @@ typedef void
 
 cairo_private cairo_cache_t *
 _cairo_cache_create (cairo_cache_keys_equal_func_t keys_equal,
+		     cairo_cache_predicate_func_t  predicate,
 		     cairo_destroy_func_t	   entry_destroy,
 		     unsigned long		   max_size);
 
@@ -113,10 +114,6 @@ cairo_private void *
 _cairo_cache_lookup (cairo_cache_t	  *cache,
 		     cairo_cache_entry_t  *key);
 
-cairo_private void *
-_cairo_cache_steal (cairo_cache_t	  *cache,
-		     cairo_cache_entry_t  *key);
-
 cairo_private cairo_status_t
 _cairo_cache_insert (cairo_cache_t	 *cache,
 		     cairo_cache_entry_t *entry);