[pango/wip-bitmatrix: 5/5] Compute the coverage order ahead of time

[Matthias Clasen <matthiasc src gnome org>]

commit a5e203b8601ef47e1917638c613e469de53d40a8
Author: Matthias Clasen <mclasen redhat com>
Date:   Sat Aug 22 13:50:55 2020 -0400

    Compute the coverage order ahead of time
    
    Store a full matrix for the partial order of
    coverage subsets. To avoid this growing too
    large, use an indirection to store the information
    only once for identical charsets.
    
    On my system, with 4000 fonts, I see ~300 different
    charsets. Computing the full matrix takes a while -
    ~240ms. But we only have to do this once, we do it
    in a thread, and we can possibly store it and
    load it from disk.
    
    Unlike our other thread use, we won't block for
    the coverage, ever. Until it is available, things
    are simply slower.
    
    With the coverage order data, we can avoid most
    of the expensive charset subset calculations when
    trimming fontsets.
    
    This finally gets a font chooser up on the screen
    in less a second, on my system (~800ms).

 pango/pangofc-fontmap.c | 269 +++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 257 insertions(+), 12 deletions(-)
---
diff --git a/pango/pangofc-fontmap.c b/pango/pangofc-fontmap.c
index b85fb5f8..32e9acbe 100644
--- a/pango/pangofc-fontmap.c
+++ b/pango/pangofc-fontmap.c
@@ -138,6 +138,14 @@ typedef struct _PangoFcFontset      PangoFcFontset;
 #define PANGO_FC_FONTSET(object)        (G_TYPE_CHECK_INSTANCE_CAST ((object), PANGO_FC_TYPE_FONTSET, 
PangoFcFontset))
 #define PANGO_FC_IS_FONTSET(object)     (G_TYPE_CHECK_INSTANCE_TYPE ((object), PANGO_FC_TYPE_FONTSET))
 
+typedef struct _CoverageOrder CoverageOrder;
+
+static CoverageOrder *coverage_order_new       (FcFontSet     *fonts);
+static void           coverage_order_free      (CoverageOrder *co);
+static gboolean       coverage_order_is_subset (CoverageOrder *co,
+                                                FcPattern     *p1,
+                                                FcPattern     *p2);
+
 struct _PangoFcFontMapPrivate
 {
   GHashTable *fontset_hash;    /* Maps PangoFcFontsetKey -> PangoFcFontset  */
@@ -167,6 +175,9 @@ struct _PangoFcFontMapPrivate
 
   FcConfig *config;
   FcFontSet *fonts;
+
+  CoverageOrder *coverage_order;
+  GCancellable *coverage_cancellable;
 };
 
 struct _PangoFcFontFaceData
@@ -1073,10 +1084,7 @@ pango_fc_patterns_get_font_pattern (PangoFcPatterns *pats, int i, gboolean *prep
     {
       int f, k;
 
-      /* Find the i'th fontset skipping the ones that are
-       * not adding coverage.
-       */
-
+      /* Find the i'th fontset while doing coverage trimming. */
       if (!pats->skip)
         {
           pats->skip = g_new0 (char, fontset->nfont);
@@ -1087,14 +1095,33 @@ pango_fc_patterns_get_font_pattern (PangoFcPatterns *pats, int i, gboolean *prep
         {
           if (pats->skip[f] == 0) /* calculate whether to skip */
             {
-              FcCharSet *fcs;
-              FcBool added = FcFalse;
-
-              FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs);
-
-              FcCharSetMerge (pats->cs, fcs, &added);
-
-              pats->skip[f] = added ? 2 : 1;
+              int l;
+
+              if (pats->fontmap->priv->coverage_order)
+                {
+                  for (l = 0; l < f; l++) /* see if a previous font covers it */
+                    {
+                      if (coverage_order_is_subset (pats->fontmap->priv->coverage_order,
+                                                    fontset->fonts[f],
+                                                    fontset->fonts[l]))
+                        {
+                          pats->skip[f] = 1;
+                          break;
+                        }
+                    }
+                }
+
+              if (pats->skip[f] == 0) /* have to do it the hard way */
+                {
+                  FcCharSet *fcs;
+                  FcBool added = FcFalse;
+
+                  FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs);
+
+                  FcCharSetMerge (pats->cs, fcs, &added);
+
+                  pats->skip[f] = added ? 2 : 1;
+                }
             }
 
           if (pats->skip[f] == 2) /* don't skip */
@@ -1465,6 +1492,12 @@ pango_fc_font_map_fini (PangoFcFontMap *fcfontmap)
   PangoFcFontMapPrivate *priv = fcfontmap->priv;
   int i;
 
+  if (priv->coverage_cancellable)
+    {
+      g_cancellable_cancel (priv->coverage_cancellable);
+      g_clear_object (&priv->coverage_cancellable);
+    }
+  g_clear_pointer (&priv->coverage_order, coverage_order_free);
   g_clear_pointer (&priv->fonts, FcFontSetDestroy);
 
   g_queue_free (priv->fontset_cache);
@@ -2319,6 +2352,7 @@ pango_fc_font_map_set_config (PangoFcFontMap *fcfontmap,
 
   fcfontmap->priv->config = fcconfig;
 
+  g_clear_pointer (&fcfontmap->priv->coverage_order, coverage_order_free);
   g_clear_pointer (&fcfontmap->priv->fonts, FcFontSetDestroy);
 
   if (oldconfig != fcconfig)
@@ -2354,11 +2388,206 @@ pango_fc_font_map_get_config (PangoFcFontMap *fcfontmap)
   return fcfontmap->priv->config;
 }
 
+typedef struct _BitMatrix BitMatrix;
+
+struct _BitMatrix
+{
+  int rows;
+  int cols;
+  char *bits;
+};
+
+static void
+bit_matrix_free (BitMatrix *b)
+{
+  g_free (b->bits);
+  g_free (b);
+}
+
+static BitMatrix *
+bit_matrix_new (int rows, int cols)
+{
+  BitMatrix *b = g_new (BitMatrix, 1);
+
+  b->rows = rows;
+  b->cols = cols;
+  b->bits = g_new0 (char, (rows * cols) / 8 + 1);
+
+  return b;
+}
+
+static gboolean
+bit_matrix_get (BitMatrix *b, int i, int j)
+{
+  int pos = i * b->cols + j;
+
+  return (b->bits[pos / 8] & (1 << (pos % 8))) != 0;
+}
+
+static void
+bit_matrix_set (BitMatrix *b, int i, int j, gboolean value)
+{
+  int pos = i * b->cols + j;
+
+  if (value)
+    b->bits[pos / 8] = b->bits[pos / 8] | (1 << (pos % 8));
+  else
+    b->bits[pos / 8] = b->bits[pos / 8] & ~(1 << (pos % 8));
+}
+
+struct _CoverageOrder
+{
+  GHashTable *idx;
+  BitMatrix *order;
+};
+
+static void
+coverage_order_free (CoverageOrder *co)
+{
+  g_hash_table_unref (co->idx);
+  bit_matrix_free (co->order);
+  g_free (co);
+}
+
+static gboolean
+coverage_order_is_subset (CoverageOrder *co,
+                          FcPattern     *p1,
+                          FcPattern     *p2)
+{
+  int idx1, idx2;
+
+  idx1 = GPOINTER_TO_INT (g_hash_table_lookup (co->idx, p1)) - 1;
+  idx2 = GPOINTER_TO_INT (g_hash_table_lookup (co->idx, p2)) - 1;
+
+  return bit_matrix_get (co->order, idx1, idx2);
+}
+
+static CoverageOrder *
+coverage_order_new (FcFontSet *fonts)
+{
+  CoverageOrder *co;
+  int *idx;
+  GPtrArray *coverages;
+  int max, i, j;
+
+  co = g_new (CoverageOrder, 1);
+
+  co->idx = g_hash_table_new (g_direct_hash, g_direct_equal);
+
+  idx = g_new (int, fonts->nfont);
+  coverages = g_ptr_array_new ();
+
+  max = -1;
+  for (i = 0; i < fonts->nfont; i++)
+    {
+      FcPattern *p1 = fonts->fonts[i];
+      FcCharSet *c1;
+
+      FcPatternGetCharSet (p1, "charset", 0, &c1);
+      idx[i] = max + 1;
+      for (j = 0; j < i; j++)
+        {
+          FcPattern *p2 = fonts->fonts[j];
+          FcCharSet *c2;
+
+          FcPatternGetCharSet (p2, "charset", 0, &c2);
+
+          if (FcCharSetEqual (c1, c2))
+            {
+              idx[i] = idx[j];
+              break;
+            }
+        }
+
+      g_hash_table_insert (co->idx, p1, GINT_TO_POINTER (idx[i] + 1));
+      if (idx[i] > max)
+        {
+          g_ptr_array_add (coverages, c1);
+          max = idx[i];
+        }
+    }
+
+  co->order = bit_matrix_new (coverages->len, coverages->len);
+
+  for (i = 0; i < coverages->len; i++)
+    {
+      FcCharSet *ci = g_ptr_array_index (coverages, i);
+      bit_matrix_set (co->order, i, i, TRUE);
+      for (j = 0; j < i; j++)
+        {
+          FcCharSet *cj = g_ptr_array_index (coverages, j);
+          gboolean v;
+          int k;
+
+          v = FALSE;
+          for (k = 0; k < coverages->len; k++)
+            {
+              if (bit_matrix_get (co->order, j, k) &&
+                  bit_matrix_get (co->order, k, i))
+                {
+                  v = TRUE;
+                  break;
+                }
+            }
+
+          if (v || FcCharSetIsSubset (cj, ci))
+            bit_matrix_set (co->order, j, i, TRUE);
+
+          v = FALSE;
+          for (k = 0; k < coverages->len; k++)
+            {
+              if (bit_matrix_get (co->order, i, k) &&
+                  bit_matrix_get (co->order, k, j))
+                {
+                  v = TRUE;
+                  break;
+                }
+            }
+
+          if (v || FcCharSetIsSubset (ci, cj))
+            bit_matrix_set (co->order, i, j, TRUE);
+        }
+    }
+
+  g_ptr_array_unref (coverages);
+  g_free (idx);
+
+  return co;
+}
+
+static void
+compute_coverage_order_in_thread (GTask        *task,
+                                  gpointer      source_object,
+                                  gpointer      task_data,
+                                  GCancellable *cancellable)
+{
+  FcFontSet *fonts = task_data;
+  CoverageOrder *coverage_order;
+  gint64 before = PANGO_TRACE_CURRENT_TIME;
+
+  coverage_order = coverage_order_new (fonts);
+
+  pango_trace_mark (before, "compute_coverage_order", NULL);
+
+  g_task_return_pointer (task, coverage_order, (GDestroyNotify)coverage_order_free);
+}
+
+static void
+coverage_computed (GObject      *source_object,
+                   GAsyncResult *result,
+                   gpointer      data)
+{
+  PangoFcFontMap *fcfontmap = PANGO_FC_FONT_MAP (source_object);
+
+  fcfontmap->priv->coverage_order = g_task_propagate_pointer (G_TASK (result), NULL);
+}
+
 static FcFontSet *
 pango_fc_font_map_get_config_fonts (PangoFcFontMap *fcfontmap)
 {
   if (fcfontmap->priv->fonts == NULL)
     {
+      GTask *task;
       FcFontSet *sets[2];
 
       wait_for_fc_init ();
@@ -2366,6 +2595,22 @@ pango_fc_font_map_get_config_fonts (PangoFcFontMap *fcfontmap)
       sets[0] = FcConfigGetFonts (fcfontmap->priv->config, 0);
       sets[1] = FcConfigGetFonts (fcfontmap->priv->config, 1);
       fcfontmap->priv->fonts = filter_by_format (sets, 2);
+
+      g_clear_pointer (&fcfontmap->priv->coverage_order, coverage_order_free);
+
+      if (fcfontmap->priv->coverage_cancellable)
+        {
+          g_cancellable_cancel (fcfontmap->priv->coverage_cancellable);
+          g_clear_object (&fcfontmap->priv->coverage_cancellable);
+        }
+
+      fcfontmap->priv->coverage_cancellable = g_cancellable_new ();
+
+      task = g_task_new (fcfontmap, fcfontmap->priv->coverage_cancellable, coverage_computed, NULL);
+      g_task_set_name (task, "[pango] compute_coverage_order");
+      g_task_set_task_data (task, font_set_copy (fcfontmap->priv->fonts), (GDestroyNotify)FcFontSetDestroy);
+      g_task_run_in_thread (task, compute_coverage_order_in_thread);
+      g_object_unref (task);
     }
 
   return fcfontmap->priv->fonts;