[scaled-font] Global glyph cache

Currently glyphs are cached independently in each font i.e. each font
maintains a cache of up to 256 glyphs, and there can be as many scaled fonts
in use as the application needs and references (we maintain a holdover
cache of 512 scaled fonts as well).

Alternatively, as in this patch, we can maintain a global pool of glyphs
split between all open fonts. This allows a heavily used individual font
to cache more glyphs than we could allow if we used per-font glyph caches,
but at the same time maintains fairness across all fonts (by using random
replacement) and provides a cap on the maximum number of global glyphs.

The glyphs are allocated in pages, which are cached in the global pool.
Using pages means we can exploit spatial locality within the font
(nearby indices are typically used in clusters) to reduce frequency of small
allocations and allow the scaled font to reserve a single MRU page of
glyphs. This caching dramatically reduces the cairo overhead during the
cairo-perf benchmarks, and drastically reduces the number of allocations
made by the application (for example browsing multi-lingual site with
firefox).

9 files changed, 351 insertions, 141 deletions

diff --git a/boilerplate/cairo-boilerplate.c b/boilerplate/cairo-boilerplate.c
index 91032cde9..dd34110c5 100644
--- a/boilerplate/cairo-boilerplate.c
+++ b/boilerplate/cairo-boilerplate.c
@@ -866,10 +866,7 @@ void
 cairo_boilerplate_scaled_font_set_max_glyphs_cached (cairo_scaled_font_t *scaled_font,
 						     int max_glyphs)
 {
-    if (cairo_scaled_font_status (scaled_font))
-	return;
-
-    scaled_font->glyphs->max_size = max_glyphs;
+    /* XXX CAIRO_DEBUG */
 }
 
 #if HAS_DAEMON
diff --git a/src/cairo-cache-private.h b/src/cairo-cache-private.h
index 5ac8cc8b0..8ad0c774a 100644
--- a/src/cairo-cache-private.h
+++ b/src/cairo-cache-private.h
@@ -113,11 +113,19 @@ 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);
 
 cairo_private void
+_cairo_cache_remove (cairo_cache_t	 *cache,
+		     cairo_cache_entry_t *entry);
+
+cairo_private void
 _cairo_cache_foreach (cairo_cache_t		 *cache,
 		      cairo_cache_callback_func_t cache_callback,
 		      void			 *closure);
diff --git a/src/cairo-cache.c b/src/cairo-cache.c
index 07c8b71fe..cab6e1e9f 100644
--- a/src/cairo-cache.c
+++ b/src/cairo-cache.c
@@ -39,10 +39,6 @@
 #include "cairoint.h"
 
 static void
-_cairo_cache_remove (cairo_cache_t	 *cache,
-		     cairo_cache_entry_t *entry);
-
-static void
 _cairo_cache_shrink_to_accommodate (cairo_cache_t *cache,
 				    unsigned long  additional);
 
@@ -225,6 +221,26 @@ _cairo_cache_lookup (cairo_cache_t	  *cache,
 				     (cairo_hash_entry_t *) key);
 }
 
+void *
+_cairo_cache_steal (cairo_cache_t	  *cache,
+		    cairo_cache_entry_t  *key)
+{
+    cairo_cache_entry_t *entry;
+
+    entry = _cairo_hash_table_steal (cache->hash_table,
+				     (cairo_hash_entry_t *) key);
+    if (entry != NULL)
+	cache->size -= entry->size;
+
+    return entry;
+}
+
+static cairo_bool_t
+_cairo_cache_entry_is_non_zero (void *entry)
+{
+    return ((cairo_cache_entry_t *)entry)->size;
+}
+
 /**
  * _cairo_cache_remove_random:
  * @cache: a cache
@@ -239,7 +255,8 @@ _cairo_cache_remove_random (cairo_cache_t *cache)
 {
     cairo_cache_entry_t *entry;
 
-    entry = _cairo_hash_table_random_entry (cache->hash_table, NULL);
+    entry = _cairo_hash_table_random_entry (cache->hash_table,
+					    _cairo_cache_entry_is_non_zero);
     if (unlikely (entry == NULL))
 	return FALSE;
 
@@ -307,13 +324,8 @@ _cairo_cache_insert (cairo_cache_t	 *cache,
  * @entry: an entry that exists in the cache
  *
  * Remove an existing entry from the cache.
- *
- * (Note: If any caller wanted access to a non-static version of this
- * function, an improved version would require only a key rather than
- * an entry. Fixing that would require fixing _cairo_hash_table_remove
- * to return (a copy of?) the entry being removed.)
  **/
-static void
+void
 _cairo_cache_remove (cairo_cache_t	 *cache,
 		     cairo_cache_entry_t *entry)
 {
@@ -336,7 +348,7 @@ _cairo_cache_remove (cairo_cache_t	 *cache,
  * non-specified order.
  **/
 void
-_cairo_cache_foreach (cairo_cache_t	 	      *cache,
+_cairo_cache_foreach (cairo_cache_t		      *cache,
 		      cairo_cache_callback_func_t      cache_callback,
 		      void			      *closure)
 {
diff --git a/src/cairo-hash-private.h b/src/cairo-hash-private.h
index a0be097a8..8ab085822 100644
--- a/src/cairo-hash-private.h
+++ b/src/cairo-hash-private.h
@@ -68,6 +68,10 @@ _cairo_hash_table_lookup (cairo_hash_table_t  *hash_table,
 			  cairo_hash_entry_t  *key);
 
 cairo_private void *
+_cairo_hash_table_steal (cairo_hash_table_t *hash_table,
+			 cairo_hash_entry_t *key);
+
+cairo_private void *
 _cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
 				cairo_hash_predicate_func_t predicate);
 
diff --git a/src/cairo-hash.c b/src/cairo-hash.c
index 973281d40..c0c9f7d86 100644
--- a/src/cairo-hash.c
+++ b/src/cairo-hash.c
@@ -312,17 +312,17 @@ void *
 _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
 			  cairo_hash_entry_t *key)
 {
-    cairo_hash_entry_t **entry;
+    cairo_hash_entry_t *entry;
     unsigned long table_size, i, idx, step;
 
     table_size = hash_table->arrangement->size;
     idx = key->hash % table_size;
-    entry = &hash_table->entries[idx];
 
-    if (ENTRY_IS_LIVE (*entry)) {
-	if (hash_table->keys_equal (key, *entry))
-	    return *entry;
-    } else if (ENTRY_IS_FREE (*entry))
+    entry = hash_table->entries[idx];
+    if (ENTRY_IS_LIVE (entry)) {
+	if (hash_table->keys_equal (key, entry))
+	    return entry;
+    } else if (ENTRY_IS_FREE (entry))
 	return NULL;
 
     i = 1;
@@ -334,11 +334,66 @@ _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
 	if (idx >= table_size)
 	    idx -= table_size;
 
-	entry = &hash_table->entries[idx];
-	if (ENTRY_IS_LIVE (*entry)) {
-	    if (hash_table->keys_equal (key, *entry))
-		return *entry;
-	} else if (ENTRY_IS_FREE (*entry))
+	entry = hash_table->entries[idx];
+	if (ENTRY_IS_LIVE (entry)) {
+	    if (hash_table->keys_equal (key, entry))
+		return entry;
+	} else if (ENTRY_IS_FREE (entry))
+	    return NULL;
+    } while (++i < table_size);
+
+    return NULL;
+}
+
+/**
+ * _cairo_hash_table_steal:
+ * @hash_table: a hash table
+ * @key: the key of interest
+ *
+ * Performs a lookup in @hash_table looking for an entry which has a
+ * key that matches @key, (as determined by the keys_equal() function
+ * passed to _cairo_hash_table_create) and removes that entry from the
+ * hash table.
+ *
+ * Return value: the matching entry, of %NULL if no match was found.
+ **/
+void *
+_cairo_hash_table_steal (cairo_hash_table_t *hash_table,
+			 cairo_hash_entry_t *key)
+{
+    cairo_hash_entry_t *entry;
+    unsigned long table_size, i, idx, step;
+
+    table_size = hash_table->arrangement->size;
+    idx = key->hash % table_size;
+
+    entry = hash_table->entries[idx];
+    if (ENTRY_IS_LIVE (entry)) {
+	if (hash_table->keys_equal (key, entry)) {
+	    hash_table->entries[idx] = DEAD_ENTRY;
+	    hash_table->live_entries--;
+	    return entry;
+	}
+    } else if (ENTRY_IS_FREE (entry))
+	return NULL;
+
+    i = 1;
+    step = key->hash % hash_table->arrangement->rehash;
+    if (step == 0)
+	step = 1;
+    do {
+	idx += step;
+	if (idx >= table_size)
+	    idx -= table_size;
+
+	entry = hash_table->entries[idx];
+	if (ENTRY_IS_LIVE (entry)) {
+	    if (hash_table->keys_equal (key, entry)) {
+		hash_table->entries[idx] = DEAD_ENTRY;
+		hash_table->live_entries--;
+		return entry;
+	    }
+	} else if (ENTRY_IS_FREE (entry))
 	    return NULL;
     } while (++i < table_size);
 
@@ -348,11 +403,10 @@ _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
 /**
  * _cairo_hash_table_random_entry:
  * @hash_table: a hash table
- * @predicate: a predicate function, or %NULL for any entry.
+ * @predicate: a predicate function.
  *
  * Find a random entry in the hash table satisfying the given
- * @predicate. A %NULL @predicate is taken as equivalent to a function
- * which always returns %TRUE, (eg. any entry in the table will do).
+ * @predicate.
  *
  * We use the same algorithm as the lookup algorithm to walk over the
  * entries in the hash table in a pseudo-random order. Walking
@@ -369,36 +423,33 @@ void *
 _cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
 				cairo_hash_predicate_func_t predicate)
 {
-    cairo_hash_entry_t **entry;
+    cairo_hash_entry_t *entry;
     unsigned long hash;
     unsigned long table_size, i, idx, step;
 
-    table_size = hash_table->arrangement->size;
+    assert (predicate != NULL);
 
+    table_size = hash_table->arrangement->size;
     hash = rand ();
     idx = hash % table_size;
-    step = 0;
 
-    for (i = 0; i < table_size; ++i)
-    {
-	entry = &hash_table->entries[idx];
-
-	if (ENTRY_IS_LIVE (*entry) &&
-	    (predicate == NULL || predicate (*entry)))
-	{
-	    return *entry;
-	}
-
-	if (step == 0) {
-	    step = hash % hash_table->arrangement->rehash;
-	    if (step == 0)
-		step = 1;
-	}
+    entry = hash_table->entries[idx];
+    if (ENTRY_IS_LIVE (entry) && predicate (entry))
+	return entry;
 
+    i = 1;
+    step = hash % hash_table->arrangement->rehash;
+    if (step == 0)
+	step = 1;
+    do {
 	idx += step;
 	if (idx >= table_size)
 	    idx -= table_size;
-    }
+
+	entry = hash_table->entries[idx];
+	if (ENTRY_IS_LIVE (entry) && predicate (entry))
+	    return entry;
+    } while (++i < table_size);
 
     return NULL;
 }
diff --git a/src/cairo-mutex-list-private.h b/src/cairo-mutex-list-private.h
index 7d43481cb..8f62cb9f9 100644
--- a/src/cairo-mutex-list-private.h
+++ b/src/cairo-mutex-list-private.h
@@ -42,6 +42,7 @@ CAIRO_MUTEX_DECLARE (_cairo_pattern_solid_surface_cache_lock)
 CAIRO_MUTEX_DECLARE (_cairo_toy_font_face_mutex)
 CAIRO_MUTEX_DECLARE (_cairo_intern_string_mutex)
 CAIRO_MUTEX_DECLARE (_cairo_scaled_font_map_mutex)
+CAIRO_MUTEX_DECLARE (_cairo_scaled_glyph_page_cache_mutex)
 CAIRO_MUTEX_DECLARE (_cairo_scaled_font_error_mutex)
 
 #if CAIRO_HAS_FT_FONT
diff --git a/src/cairo-scaled-font-private.h b/src/cairo-scaled-font-private.h
index 86a50bbbd..13d89ebe5 100644
--- a/src/cairo-scaled-font-private.h
+++ b/src/cairo-scaled-font-private.h
@@ -44,6 +44,8 @@
 #include "cairo-mutex-type-private.h"
 #include "cairo-reference-count-private.h"
 
+typedef struct _cairo_scaled_glyph_page cairo_scaled_glyph_page_t;
+
 struct _cairo_scaled_font {
     /* For most cairo objects, the rule for multiple threads is that
      * the user is responsible for any locking if the same object is
@@ -75,7 +77,6 @@ struct _cairo_scaled_font {
      *    scaled_font->mutex in the generic scaled_font code.
      */
 
-    /* must be first to be stored in a hash table */
     cairo_hash_entry_t hash_entry;
 
     /* useful bits for _cairo_scaled_font_nil */
@@ -103,7 +104,8 @@ struct _cairo_scaled_font {
     /* The mutex protects modification to all subsequent fields. */
     cairo_mutex_t mutex;
 
-    cairo_cache_t *glyphs;	  /* glyph index -> cairo_scaled_glyph_t */
+    int cache_frozen;
+    cairo_scaled_glyph_page_t *mru_page;
 
     /*
      * One surface backend may store data in each glyph.
diff --git a/src/cairo-scaled-font.c b/src/cairo-scaled-font.c
index 1d5798f7a..727ab2ecb 100644
--- a/src/cairo-scaled-font.c
+++ b/src/cairo-scaled-font.c
@@ -35,11 +35,30 @@
  *      Graydon Hoare <graydon@redhat.com>
  *      Owen Taylor <otaylor@redhat.com>
  *      Behdad Esfahbod <behdad@behdad.org>
+ *      Chris Wilson <chris@chris-wilson.co.uk>
  */
 
 #include "cairoint.h"
 #include "cairo-scaled-font-private.h"
 
+#define CAIRO_SCALED_GLYPH_PAGE_SHIFT 7
+#define CAIRO_SCALED_GLYPH_PAGE_SIZE (1 << CAIRO_SCALED_GLYPH_PAGE_SHIFT)
+#define CAIRO_SCALED_GLYPH_PAGE_INDEX(I) \
+    ((I) & (CAIRO_SCALED_GLYPH_PAGE_SIZE - 1))
+#define CAIRO_SCALED_GLYPH_PAGE_BASE_INDEX(I) ((I) & -CAIRO_SCALED_GLYPH_PAGE_SIZE)
+#define CAIRO_SCALED_GLYPH_PAGE_HAS_INDEX(P, I) \
+    ((I) - (P)->base_index < CAIRO_SCALED_GLYPH_PAGE_SIZE)
+typedef struct _cairo_scaled_glyph_page_key {
+    cairo_cache_entry_t cache_entry;
+    cairo_scaled_font_t *scaled_font;
+} cairo_scaled_glyph_page_key_t;
+
+struct _cairo_scaled_glyph_page {
+    cairo_scaled_glyph_page_key_t key;
+    unsigned long base_index;
+    cairo_scaled_glyph_t glyphs[CAIRO_SCALED_GLYPH_PAGE_SIZE];
+};
+
 /*
  *  Notes:
  *
@@ -131,16 +150,16 @@
  *  Now compare the scaled-glyph space to device-space and surface-space
  *  and convince yourself that:
  *
- *  	(x_bearing,y_bearing) = (-x,-y) = - device_offset
+ *	(x_bearing,y_bearing) = (-x,-y) = - device_offset
  *
  *  That's right.  If you are not convinced yet, contrast the definition
  *  of the two:
  *
- *  	"(x_bearing,y_bearing) is the coordinates of top-left of the
- *  	 glyph relative to the glyph origin."
+ *	"(x_bearing,y_bearing) is the coordinates of top-left of the
+ *	 glyph relative to the glyph origin."
  *
- *  	"In other words: device_offset is the coordinates of the
- *  	 device-space origin relative to the top-left of the surface."
+ *	"In other words: device_offset is the coordinates of the
+ *	 device-space origin relative to the top-left of the surface."
  *
  *  and note that glyph origin = device-space origin.
  */
@@ -148,15 +167,9 @@
 static void
 _cairo_scaled_font_fini_internal (cairo_scaled_font_t *scaled_font);
 
-static cairo_bool_t
-_cairo_scaled_glyph_keys_equal (const void *abstract_key_a, const void *abstract_key_b)
-{
-    const cairo_scaled_glyph_t *key_a = abstract_key_a;
-    const cairo_scaled_glyph_t *key_b = abstract_key_b;
-
-    return (_cairo_scaled_glyph_index (key_a) ==
-	    _cairo_scaled_glyph_index (key_b));
-}
+static void
+_cairo_scaled_glyph_page_cache_remove_scaled_font (cairo_scaled_font_t
+						   *scaled_font);
 
 static void
 _cairo_scaled_glyph_fini (cairo_scaled_glyph_t *scaled_glyph)
@@ -166,20 +179,17 @@ _cairo_scaled_glyph_fini (cairo_scaled_glyph_t *scaled_glyph)
 
     if (surface_backend != NULL && surface_backend->scaled_glyph_fini != NULL)
 	surface_backend->scaled_glyph_fini (scaled_glyph, scaled_font);
+
     if (scaled_glyph->surface != NULL)
 	cairo_surface_destroy (&scaled_glyph->surface->base);
+
     if (scaled_glyph->path != NULL)
 	_cairo_path_fixed_destroy (scaled_glyph->path);
+
     if (scaled_glyph->meta_surface != NULL)
 	cairo_surface_destroy (scaled_glyph->meta_surface);
-}
 
-static void
-_cairo_scaled_glyph_destroy (void *abstract_glyph)
-{
-    cairo_scaled_glyph_t *scaled_glyph = abstract_glyph;
-    _cairo_scaled_glyph_fini (scaled_glyph);
-    free (scaled_glyph);
+    scaled_glyph->scaled_font = NULL;
 }
 
 #define ZOMBIE 0
@@ -203,7 +213,8 @@ static const cairo_scaled_font_t _cairo_scaled_font_nil = {
     { 0., 0., 0., 0., 0. },	/* extents */
     { 0., 0., 0., 0., 0. },	/* fs_extents */
     CAIRO_MUTEX_NIL_INITIALIZER,/* mutex */
-    NULL,			/* glyphs */
+    FALSE,			/* cache_frozen */
+    NULL,			/* mru_page */
     NULL,			/* surface_backend */
     NULL,			/* surface_private */
     NULL			/* backend */
@@ -310,7 +321,7 @@ typedef struct _cairo_scaled_font_map {
     int num_holdovers;
 } cairo_scaled_font_map_t;
 
-static cairo_scaled_font_map_t *cairo_scaled_font_map = NULL;
+static cairo_scaled_font_map_t *cairo_scaled_font_map;
 
 static int
 _cairo_scaled_font_keys_equal (const void *abstract_key_a, const void *abstract_key_b);
@@ -400,6 +411,112 @@ _cairo_scaled_font_map_destroy (void)
     CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_map_mutex);
 }
 
+/* Global Glyph Cache
+ *
+ * We maintain a global pool of glyphs split between all open fonts. This
+ * allows a heavily used individual font to cache more glyphs than we could
+ * manage if we used per-font glyph caches, but at the same time maintains
+ * fairness across all fonts and provides a cap on the maximum number of
+ * global glyphs.
+ *
+ * The glyphs are allocated in pages, which are cached in the global pool.
+ * Using pages means we can exploit spatial locality within the font (nearby
+ * indices are typically used in clusters) to reduce frequency of small
+ * allocations and allow the scaled font to reserve a single MRU page of
+ * glyphs.
+ */
+
+/* XXX: This number is arbitrary---we've never done any measurement of this. */
+#define MAX_GLYPH_PAGES_CACHED 512
+
+static cairo_cache_t *cairo_scaled_glyph_page_cache;
+
+static cairo_bool_t
+_cairo_scaled_glyph_pages_equal (const void *key_a, const void *key_b)
+{
+    const cairo_scaled_glyph_page_key_t *a = key_a;
+    const cairo_scaled_glyph_page_key_t *b = key_b;
+
+    return
+	a->cache_entry.hash == b->cache_entry.hash &&
+	a->scaled_font == b->scaled_font;
+}
+
+static void
+_cairo_scaled_glyph_page_destroy (void *closure)
+{
+    cairo_scaled_glyph_page_t *page = closure;
+    int n;
+
+    for (n = 0; n < CAIRO_SCALED_GLYPH_PAGE_SIZE; n++) {
+	if (page->glyphs[n].scaled_font != NULL)
+	    _cairo_scaled_glyph_fini (&page->glyphs[n]);
+    }
+
+    free (page);
+}
+
+static cairo_scaled_glyph_page_t *
+_cairo_scaled_glyph_page_cache_lookup (cairo_scaled_font_t *scaled_font,
+				       unsigned long index)
+{
+    cairo_scaled_glyph_page_key_t key;
+    cairo_scaled_glyph_page_t *page;
+
+    key.cache_entry.hash =
+	(index >> CAIRO_SCALED_GLYPH_PAGE_SHIFT) ^
+	(unsigned long) scaled_font;
+    key.scaled_font = scaled_font;
+
+    if (scaled_font->cache_frozen) {
+	CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+	page = _cairo_cache_steal (cairo_scaled_glyph_page_cache,
+				   &key.cache_entry);
+	CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
+    } else
+	page = NULL;
+
+    if (page == NULL) {
+	/* On miss, create glyph page and insert into cache */
+	page = malloc (sizeof (cairo_scaled_glyph_page_t));
+	if (unlikely (page == NULL))
+	    return NULL;
+
+	page->key.cache_entry.hash = key.cache_entry.hash;
+	/* We currently don't differentiate on glyph size at all */
+	page->key.cache_entry.size = 1;
+	page->key.scaled_font = scaled_font;
+	page->base_index = CAIRO_SCALED_GLYPH_PAGE_BASE_INDEX (index);
+
+	memset (page->glyphs, 0, sizeof (page->glyphs));
+    }
+
+    return page;
+}
+
+static void
+_cairo_scaled_glyph_page_cache_remove_scaled_font_cb (void *entry,
+						      void *closure)
+{
+    cairo_scaled_glyph_page_key_t *key = entry;
+
+    if (key->scaled_font == closure)
+	_cairo_cache_remove (cairo_scaled_glyph_page_cache, entry);
+}
+
+static void
+_cairo_scaled_glyph_page_cache_remove_scaled_font (cairo_scaled_font_t *scaled_font)
+{
+    CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+
+    if (cairo_scaled_glyph_page_cache != NULL) {
+	_cairo_cache_foreach (cairo_scaled_glyph_page_cache,
+			      _cairo_scaled_glyph_page_cache_remove_scaled_font_cb,
+			      scaled_font);
+    }
+
+    CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
+}
 
 /* If a scaled font wants to unlock the font map while still being
  * created (needed for user-fonts), we need to take extra care not
@@ -591,13 +708,6 @@ _cairo_scaled_font_keys_equal (const void *abstract_key_a, const void *abstract_
 	    cairo_font_options_equal (&key_a->options, &key_b->options));
 }
 
-/* XXX: This 256 number is arbitrary---we've never done any measurement
- * of this. In fact, having a per-font glyph caches each managed
- * separately is probably not what we want anyway. Would probably be
- * much better to have a single cache for glyphs with random
- * replacement across all glyphs of all fonts. */
-#define MAX_GLYPHS_CACHED_PER_FONT 256
-
 /*
  * Basic #cairo_scaled_font_t object management
  */
@@ -648,12 +758,7 @@ _cairo_scaled_font_init (cairo_scaled_font_t               *scaled_font,
     }
 
     scaled_font->finished = FALSE;
-
-    scaled_font->glyphs = _cairo_cache_create (_cairo_scaled_glyph_keys_equal,
-					       _cairo_scaled_glyph_destroy,
-					       MAX_GLYPHS_CACHED_PER_FONT);
-    if (unlikely (scaled_font->glyphs == NULL))
-	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    scaled_font->cache_frozen = FALSE;
 
     CAIRO_REFERENCE_COUNT_INIT (&scaled_font->ref_count, 1);
 
@@ -663,6 +768,8 @@ _cairo_scaled_font_init (cairo_scaled_font_t               *scaled_font,
 
     CAIRO_MUTEX_INIT (scaled_font->mutex);
 
+    scaled_font->mru_page = NULL;
+
     scaled_font->surface_backend = NULL;
     scaled_font->surface_private = NULL;
 
@@ -678,13 +785,19 @@ _cairo_scaled_font_freeze_cache (cairo_scaled_font_t *scaled_font)
     assert (scaled_font->status == CAIRO_STATUS_SUCCESS);
 
     CAIRO_MUTEX_LOCK (scaled_font->mutex);
-    _cairo_cache_freeze (scaled_font->glyphs);
 }
 
 void
 _cairo_scaled_font_thaw_cache (cairo_scaled_font_t *scaled_font)
 {
-    _cairo_cache_thaw (scaled_font->glyphs);
+    if (scaled_font->cache_frozen) {
+	CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+	_cairo_cache_thaw (cairo_scaled_glyph_page_cache);
+	CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
+
+	scaled_font->cache_frozen = FALSE;
+    }
+
     CAIRO_MUTEX_UNLOCK (scaled_font->mutex);
 }
 
@@ -693,10 +806,12 @@ _cairo_scaled_font_reset_cache (cairo_scaled_font_t *scaled_font)
 {
     assert (CAIRO_MUTEX_IS_LOCKED (scaled_font->mutex));
 
-    _cairo_cache_destroy (scaled_font->glyphs);
-    scaled_font->glyphs = _cairo_cache_create (_cairo_scaled_glyph_keys_equal,
-					       _cairo_scaled_glyph_destroy,
-					       MAX_GLYPHS_CACHED_PER_FONT);
+    if (scaled_font->mru_page != NULL) {
+	_cairo_scaled_glyph_page_destroy (scaled_font->mru_page);
+	scaled_font->mru_page = NULL;
+    }
+
+    _cairo_scaled_glyph_page_cache_remove_scaled_font (scaled_font);
 }
 
 cairo_status_t
@@ -733,12 +848,16 @@ _cairo_scaled_font_fini_internal (cairo_scaled_font_t *scaled_font)
 {
     scaled_font->finished = TRUE;
 
+    if (scaled_font->mru_page != NULL) {
+	_cairo_scaled_glyph_page_destroy (scaled_font->mru_page);
+	scaled_font->mru_page = NULL;
+    }
+
+    _cairo_scaled_glyph_page_cache_remove_scaled_font (scaled_font);
+
     if (scaled_font->font_face != NULL)
 	cairo_font_face_destroy (scaled_font->font_face);
 
-    if (scaled_font->glyphs != NULL)
-	_cairo_cache_destroy (scaled_font->glyphs);
-
     CAIRO_MUTEX_FINI (scaled_font->mutex);
 
     if (scaled_font->surface_backend != NULL &&
@@ -981,6 +1100,13 @@ _cairo_scaled_font_reset_static_data (void)
 	}
     }
     CAIRO_MUTEX_UNLOCK (_cairo_scaled_font_error_mutex);
+
+    CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+    if (cairo_scaled_glyph_page_cache != NULL) {
+	_cairo_cache_destroy (cairo_scaled_glyph_page_cache);
+	cairo_scaled_glyph_page_cache = NULL;
+    }
+    CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
 }
 
 /**
@@ -1038,9 +1164,9 @@ cairo_scaled_font_destroy (cairo_scaled_font_t *scaled_font)
     assert (font_map != NULL);
 
     if (_cairo_reference_count_dec_and_test (&scaled_font->ref_count)) {
-
-
-	if (!scaled_font->placeholder && scaled_font->hash_entry.hash != ZOMBIE) {
+	if (! scaled_font->placeholder &&
+	    scaled_font->hash_entry.hash != ZOMBIE)
+	{
 	    /* Rather than immediately destroying this object, we put it into
 	     * the font_map->holdovers array in case it will get used again
 	     * soon (and is why we must hold the lock over the atomic op on
@@ -1066,7 +1192,6 @@ cairo_scaled_font_destroy (cairo_scaled_font_t *scaled_font)
 	    font_map->num_holdovers++;
 	} else
 	    lru = scaled_font;
-
     }
 
     _cairo_scaled_font_map_unlock ();
@@ -1160,13 +1285,6 @@ cairo_scaled_font_set_user_data (cairo_scaled_font_t	     *scaled_font,
 }
 slim_hidden_def (cairo_scaled_font_set_user_data);
 
-static cairo_bool_t
-_cairo_scaled_font_is_frozen (cairo_scaled_font_t *scaled_font)
-{
-    return CAIRO_MUTEX_IS_LOCKED (scaled_font->mutex) &&
-	   scaled_font->glyphs->freeze_count > 0;
-}
-
 /* Public font API follows. */
 
 /**
@@ -2378,58 +2496,72 @@ _cairo_scaled_glyph_lookup (cairo_scaled_font_t *scaled_font,
 			    cairo_scaled_glyph_t **scaled_glyph_ret)
 {
     cairo_status_t		status = CAIRO_STATUS_SUCCESS;
-    cairo_cache_entry_t		key;
+    cairo_scaled_glyph_page_t	*page;
     cairo_scaled_glyph_t	*scaled_glyph;
     cairo_scaled_glyph_info_t	need_info;
 
-    if (scaled_font->status)
+    if (unlikely (scaled_font->status))
 	return scaled_font->status;
 
-    assert (_cairo_scaled_font_is_frozen (scaled_font));
+    page = scaled_font->mru_page;
+    if (page != NULL && ! CAIRO_SCALED_GLYPH_PAGE_HAS_INDEX (page, index)) {
+	CAIRO_MUTEX_LOCK (_cairo_scaled_glyph_page_cache_mutex);
+	if (! scaled_font->cache_frozen) {
+	    if (cairo_scaled_glyph_page_cache == NULL) {
+		cairo_scaled_glyph_page_cache =
+		    _cairo_cache_create (_cairo_scaled_glyph_pages_equal,
+					 _cairo_scaled_glyph_page_destroy,
+					 MAX_GLYPH_PAGES_CACHED);
+		if (unlikely (cairo_scaled_glyph_page_cache == NULL)) {
+		    status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+		    goto BAIL;
+		}
+	    }
+
+	    _cairo_cache_freeze (cairo_scaled_glyph_page_cache);
+	    scaled_font->cache_frozen = TRUE;
+	}
+	status = _cairo_cache_insert (cairo_scaled_glyph_page_cache,
+				      &page->key.cache_entry);
+      BAIL:
+	CAIRO_MUTEX_UNLOCK (_cairo_scaled_glyph_page_cache_mutex);
+	if (unlikely (status))
+	    return _cairo_scaled_font_set_error (scaled_font, status);
+
+	page = scaled_font->mru_page = NULL;
+    }
+
+    if (page == NULL) {
+	page = _cairo_scaled_glyph_page_cache_lookup (scaled_font, index);
+	if (unlikely (page == NULL)) {
+	    return _cairo_scaled_font_set_error (scaled_font,
+						 _cairo_error (CAIRO_STATUS_NO_MEMORY));
+	}
+    }
+
+    scaled_font->mru_page = page;
 
-    key.hash = index;
     /*
      * Check cache for glyph
      */
     info |= CAIRO_SCALED_GLYPH_INFO_METRICS;
-    scaled_glyph = _cairo_cache_lookup (scaled_font->glyphs, &key);
-    if (scaled_glyph == NULL) {
-	/*
-	 * On miss, create glyph and insert into cache
-	 */
-	scaled_glyph = malloc (sizeof (cairo_scaled_glyph_t));
-	if (unlikely (scaled_glyph == NULL)) {
-	    status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
-	    goto CLEANUP;
-	}
-
-	_cairo_scaled_glyph_set_index(scaled_glyph, index);
-	scaled_glyph->cache_entry.size = 1;	/* We currently don't differentiate on glyph size at all */
+    scaled_glyph = &page->glyphs[CAIRO_SCALED_GLYPH_PAGE_INDEX (index)];
+    if (scaled_glyph->scaled_font == NULL) {
+	scaled_glyph->index = index;
 	scaled_glyph->scaled_font = scaled_font;
-	scaled_glyph->surface = NULL;
-	scaled_glyph->path = NULL;
-	scaled_glyph->meta_surface = NULL;
-	scaled_glyph->surface_private = NULL;
 
 	/* ask backend to initialize metrics and shape fields */
 	status = (*scaled_font->backend->
 		  scaled_glyph_init) (scaled_font, scaled_glyph, info);
 	if (unlikely (status)) {
-	    _cairo_scaled_glyph_destroy (scaled_glyph);
-	    goto CLEANUP;
-	}
-
-	/* on success, the cache takes ownership of the scaled_glyph */
-	status = _cairo_cache_insert (scaled_font->glyphs,
-				      &scaled_glyph->cache_entry);
-	if (unlikely (status)) {
-	    _cairo_scaled_glyph_destroy (scaled_glyph);
+	    _cairo_scaled_glyph_fini (scaled_glyph);
 	    goto CLEANUP;
 	}
     }
+
     /*
      * Check and see if the glyph, as provided,
-     * already has the requested data and ammend it if not
+     * already has the requested data and amend it if not
      */
     need_info = 0;
     if ((info & CAIRO_SCALED_GLYPH_INFO_SURFACE) != 0 &&
diff --git a/src/cairoint.h b/src/cairoint.h
index 6b38fd46c..e3869d377 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -351,21 +351,24 @@ typedef struct _cairo_unscaled_font {
 } cairo_unscaled_font_t;
 
 typedef struct _cairo_scaled_glyph {
-    cairo_cache_entry_t	    cache_entry;	/* hash is glyph index */
+    unsigned long index;
     cairo_scaled_font_t	    *scaled_font;	/* font the glyph lives in */
+
     cairo_text_extents_t    metrics;		/* user-space metrics */
     cairo_text_extents_t    fs_metrics;		/* font-space metrics */
     cairo_box_t		    bbox;		/* device-space bounds */
     int16_t                 x_advance;		/* device-space rounded X advance */
     int16_t                 y_advance;		/* device-space rounded Y advance */
+
     cairo_image_surface_t   *surface;		/* device-space image */
     cairo_path_fixed_t	    *path;		/* device-space outline */
     cairo_surface_t         *meta_surface;	/* device-space meta-surface */
+
     void		    *surface_private;	/* for the surface backend */
 } cairo_scaled_glyph_t;
 
-#define _cairo_scaled_glyph_index(g) ((g)->cache_entry.hash)
-#define _cairo_scaled_glyph_set_index(g,i)  ((g)->cache_entry.hash = (i))
+#define _cairo_scaled_glyph_index(g) ((g)->index)
+#define _cairo_scaled_glyph_set_index(g, i)  ((g)->index = (i))
 
 #include "cairo-scaled-font-private.h"