diff --git a/addressbook/gui/widgets/e-addressbook-reflow-adapter.c b/addressbook/gui/widgets/e-addressbook-reflow-adapter.c
index 236ccbb..b6d26e6 100644
--- a/addressbook/gui/widgets/e-addressbook-reflow-adapter.c
+++ b/addressbook/gui/widgets/e-addressbook-reflow-adapter.c
@@ -181,8 +181,35 @@ addressbook_height (EReflowModel *erm, gint i, GnomeCanvasGroup *parent)
 	return height;
 }
 
+static GHashTable *
+addressbook_create_cmp_cache (EReflowModel *erm)
+{
+	EAddressbookReflowAdapter *adapter = E_ADDRESSBOOK_REFLOW_ADAPTER (erm);
+	EAddressbookReflowAdapterPrivate *priv = adapter->priv;
+	GHashTable *cmp_cache;
+	gint ii, count;
+
+	count = e_reflow_model_count (erm);
+
+	if (priv->loading || count <= 0)
+		return NULL;
+
+	cmp_cache = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, /*(GDestroyNotify)*/ g_free);
+
+	for (ii = 0; ii < count; ii++) {
+		EContact *contact = (EContact*) e_addressbook_model_contact_at (priv->model, ii);
+		if (contact) {
+			const gchar *file_as = e_contact_get_const (contact, E_CONTACT_FILE_AS);
+			if (file_as)
+				g_hash_table_insert (cmp_cache, GINT_TO_POINTER (ii), g_utf8_collate_key (file_as, -1));
+		}
+	}
+
+	return cmp_cache;
+}
+
 static gint
-addressbook_compare (EReflowModel *erm, gint n1, gint n2)
+addressbook_compare (EReflowModel *erm, gint n1, gint n2, GHashTable *cmp_cache)
 {
 	EAddressbookReflowAdapter *adapter = E_ADDRESSBOOK_REFLOW_ADAPTER (erm);
 	EAddressbookReflowAdapterPrivate *priv = adapter->priv;
@@ -198,10 +225,18 @@ addressbook_compare (EReflowModel *erm, gint n1, gint n2)
 		if (contact1 && contact2) {
 			const gchar *file_as1, *file_as2;
 			const gchar *uid1, *uid2;
-			file_as1 = e_contact_get_const (contact1, E_CONTACT_FILE_AS);
-			file_as2 = e_contact_get_const (contact2, E_CONTACT_FILE_AS);
-			if (file_as1 && file_as2)
-				return g_utf8_collate (file_as1, file_as2);
+
+			if (cmp_cache) {
+				file_as1 = g_hash_table_lookup (cmp_cache, GINT_TO_POINTER (n1));
+				file_as2 = g_hash_table_lookup (cmp_cache, GINT_TO_POINTER (n2));
+				if (file_as1 && file_as2)
+					return strcmp (file_as1, file_as2);
+			} else {
+				file_as1 = e_contact_get_const (contact1, E_CONTACT_FILE_AS);
+				file_as2 = e_contact_get_const (contact2, E_CONTACT_FILE_AS);
+				if (file_as1 && file_as2)
+					return g_utf8_collate (file_as1, file_as2);
+			}
 			if (file_as1)
 				return -1;
 			if (file_as2)
@@ -473,6 +508,7 @@ e_addressbook_reflow_adapter_class_init (GObjectClass *object_class)
 	model_class->set_width = addressbook_set_width;
 	model_class->count = addressbook_count;
 	model_class->height = addressbook_height;
+	model_class->create_cmp_cache = addressbook_create_cmp_cache;
 	model_class->compare = addressbook_compare;
 	model_class->incarnate = addressbook_incarnate;
 	model_class->reincarnate = addressbook_reincarnate;
diff --git a/e-util/e-sorter-array.c b/e-util/e-sorter-array.c
index e19084c..3e559ac 100644
--- a/e-util/e-sorter-array.c
+++ b/e-util/e-sorter-array.c
@@ -58,7 +58,7 @@ esort_callback (gconstpointer data1, gconstpointer data2, gpointer user_data)
 	int1 = *(gint *)data1;
 	int2 = *(gint *)data2;
 
-	ret_val = esa->compare (int1, int2, esa->closure);
+	ret_val = esa->compare (int1, int2, esa->cmp_cache, esa->closure);
 	if (ret_val != 0)
 		return ret_val;
 
@@ -84,10 +84,19 @@ esa_sort (ESorterArray *esa)
 	for (i = 0; i < rows; i++)
 		esa->sorted[i] = i;
 
-	if (esa->compare)
+	if (esa->compare) {
+		if (esa->create_cmp_cache)
+			esa->cmp_cache = esa->create_cmp_cache (esa->closure);
+
 		g_qsort_with_data (
 			esa->sorted, rows, sizeof (gint),
 			esort_callback, esa);
+
+		if (esa->cmp_cache) {
+			g_hash_table_destroy (esa->cmp_cache);
+			esa->cmp_cache = NULL;
+		}
+	}
 }
 
 static void
@@ -225,20 +234,22 @@ e_sorter_array_append  (ESorterArray *esa, gint count)
 
 ESorterArray *
 e_sorter_array_construct  (ESorterArray *esa,
+			   ECreateCmpCacheFunc create_cmp_cache,
 			   ECompareRowsFunc  compare,
 			   gpointer      closure)
 {
+	esa->create_cmp_cache = create_cmp_cache;
 	esa->compare = compare;
 	esa->closure = closure;
 	return esa;
 }
 
 ESorterArray *
-e_sorter_array_new (ECompareRowsFunc compare, gpointer closure)
+e_sorter_array_new (ECreateCmpCacheFunc create_cmp_cache, ECompareRowsFunc compare, gpointer closure)
 {
 	ESorterArray *esa = g_object_new (E_SORTER_ARRAY_TYPE, NULL);
 
-	return e_sorter_array_construct (esa, compare, closure);
+	return e_sorter_array_construct (esa, create_cmp_cache, compare, closure);
 }
 
 static void
@@ -257,6 +268,8 @@ static void
 e_sorter_array_init (ESorterArray *esa)
 {
 	esa->rows       = 0;
+	esa->cmp_cache  = NULL;
+	esa->create_cmp_cache = NULL;
 	esa->compare    = NULL;
 	esa->closure    = NULL;
 	esa->sorted     = NULL;
diff --git a/e-util/e-sorter-array.h b/e-util/e-sorter-array.h
index 9a1d3fc..94ca518 100644
--- a/e-util/e-sorter-array.h
+++ b/e-util/e-sorter-array.h
@@ -39,12 +39,17 @@ G_BEGIN_DECLS
 #define _E_COMPARE_ROWS_FUNC_H_
 typedef gint (*ECompareRowsFunc) (gint row1,
 				 gint row2,
+				 GHashTable *cmp_cache,
 				 gpointer closure);
 #endif
 
+typedef GHashTable * (*ECreateCmpCacheFunc) (gpointer closure);
+
 typedef struct {
 	ESorter      base;
 
+	GHashTable *cmp_cache;
+	ECreateCmpCacheFunc create_cmp_cache;
 	ECompareRowsFunc compare;
 	gpointer     closure;
 
@@ -61,9 +66,11 @@ typedef struct {
 
 GType         e_sorter_array_get_type   (void);
 ESorterArray *e_sorter_array_construct  (ESorterArray     *sorter,
+					 ECreateCmpCacheFunc create_cmp_cache,
 					 ECompareRowsFunc  compare,
 					 gpointer          closure);
-ESorterArray *e_sorter_array_new        (ECompareRowsFunc  compare,
+ESorterArray *e_sorter_array_new        (ECreateCmpCacheFunc create_cmp_cache,
+					 ECompareRowsFunc  compare,
 					 gpointer          closure);
 void          e_sorter_array_clean      (ESorterArray     *esa);
 void          e_sorter_array_set_count  (ESorterArray     *esa,
diff --git a/widgets/text/e-reflow-model.c b/widgets/text/e-reflow-model.c
index 6f8223a..d7a5ffe 100644
--- a/widgets/text/e-reflow-model.c
+++ b/widgets/text/e-reflow-model.c
@@ -109,24 +109,50 @@ e_reflow_model_incarnate (EReflowModel *e_reflow_model, gint n, GnomeCanvasGroup
 }
 
 /**
+ * e_reflow_model_create_cmp_cache:
+ * @e_reflow_model: The e-reflow-model to operate on
+ *
+ * Creates a compare cache for quicker sorting. The sorting function
+ * may not depend on the cache, but it should benefit from it if available.
+ *
+ * Returns: Newly created GHashTable with cached compare values. This will be
+ * automatically freed with g_hash_table_destroy() when no longer needed.
+ **/
+GHashTable *
+e_reflow_model_create_cmp_cache (EReflowModel *e_reflow_model)
+{
+	g_return_val_if_fail (e_reflow_model != NULL, NULL);
+	g_return_val_if_fail (E_IS_REFLOW_MODEL (e_reflow_model), NULL);
+
+	if (!E_REFLOW_MODEL_GET_CLASS (e_reflow_model)->create_cmp_cache)
+		return NULL;
+
+	return E_REFLOW_MODEL_GET_CLASS (e_reflow_model)->create_cmp_cache (e_reflow_model);
+}
+
+/**
  * e_reflow_model_compare:
  * @e_reflow_model: The e-reflow-model to operate on
  * @n1: The first item to compare
  * @n2: The second item to compare
+ * @cmp_cache: #GHashTable of cached compare values, created by
+ *    e_reflow_model_create_cmp_cache(). This can be NULL, when
+ *    caching is not available, even when @e_reflow_model defines
+ *    the create_cmp_cache function.
  *
  * Compares item n1 and item n2 to see which should come first.
  *
  * Returns: strcmp like semantics for the comparison value.
  */
 gint
-e_reflow_model_compare (EReflowModel *e_reflow_model, gint n1, gint n2)
+e_reflow_model_compare (EReflowModel *e_reflow_model, gint n1, gint n2, GHashTable *cmp_cache)
 {
 #if 0
 	g_return_val_if_fail (e_reflow_model != NULL, 0);
 	g_return_val_if_fail (E_IS_REFLOW_MODEL (e_reflow_model), 0);
 #endif
 
-	return E_REFLOW_MODEL_GET_CLASS (e_reflow_model)->compare (e_reflow_model, n1, n2);
+	return E_REFLOW_MODEL_GET_CLASS (e_reflow_model)->compare (e_reflow_model, n1, n2, cmp_cache);
 }
 
 /**
diff --git a/widgets/text/e-reflow-model.h b/widgets/text/e-reflow-model.h
index ebbf3c1..f6f096d 100644
--- a/widgets/text/e-reflow-model.h
+++ b/widgets/text/e-reflow-model.h
@@ -51,7 +51,8 @@ typedef struct {
 	gint              (*count)          (EReflowModel *etm);
 	gint              (*height)         (EReflowModel *etm, gint n, GnomeCanvasGroup *parent);
 	GnomeCanvasItem *(*incarnate)      (EReflowModel *etm, gint n, GnomeCanvasGroup *parent);
-	gint              (*compare)        (EReflowModel *etm, gint n1, gint n2);
+	GHashTable *     (*create_cmp_cache) (EReflowModel *etm);
+	gint              (*compare)         (EReflowModel *etm, gint n1, gint n2, GHashTable *cmp_cache);
 	void             (*reincarnate)    (EReflowModel *etm, gint n, GnomeCanvasItem *item);
 
 	/*
@@ -83,9 +84,11 @@ gint              e_reflow_model_height          (EReflowModel     *e_reflow_mod
 GnomeCanvasItem *e_reflow_model_incarnate       (EReflowModel     *e_reflow_model,
 						 gint               n,
 						 GnomeCanvasGroup *parent);
+GHashTable *     e_reflow_model_create_cmp_cache (EReflowModel *e_reflow_model);
 gint              e_reflow_model_compare         (EReflowModel     *e_reflow_model,
 						 gint               n1,
-						 gint               n2);
+						 gint               n2,
+						 GHashTable        *cmp_cache);
 void             e_reflow_model_reincarnate     (EReflowModel     *e_reflow_model,
 						 gint               n,
 						 GnomeCanvasItem  *item);
diff --git a/widgets/text/e-reflow.c b/widgets/text/e-reflow.c
index d7522d6..a796d92 100644
--- a/widgets/text/e-reflow.c
+++ b/widgets/text/e-reflow.c
@@ -74,11 +74,18 @@ enum {
 
 static guint signals[LAST_SIGNAL] = {0, };
 
+static GHashTable *
+er_create_cmp_cache (gpointer user_data)
+{
+	EReflow *reflow = user_data;
+	return e_reflow_model_create_cmp_cache (reflow->model);
+}
+
 static gint
-er_compare (gint i1, gint i2, gpointer user_data)
+er_compare (gint i1, gint i2, GHashTable *cmp_cache, gpointer user_data)
 {
 	EReflow *reflow = user_data;
-	return e_reflow_model_compare (reflow->model, i1, i2);
+	return e_reflow_model_compare (reflow->model, i1, i2, cmp_cache);
 }
 
 static gint
@@ -1594,7 +1601,7 @@ e_reflow_init (EReflow *reflow)
 	reflow->set_scroll_adjustments_id = 0;
 
 	reflow->selection                 = E_SELECTION_MODEL (e_selection_model_simple_new ());
-	reflow->sorter                    = e_sorter_array_new (er_compare, reflow);
+	reflow->sorter                    = e_sorter_array_new (er_create_cmp_cache, er_compare, reflow);
 
 	g_object_set (reflow->selection,
 		      "sorter", reflow->sorter,
