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




commit dee88e6956f40b504d35ee8554d7dd67924bb640
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/meson.build                     |   1 +
 pango/pangofc-coverageorder-private.h |  40 ++++++
 pango/pangofc-coverageorder.c         | 239 ++++++++++++++++++++++++++++++++++
 pango/pangofc-fontmap.c               |  95 ++++++++++++--
 4 files changed, 363 insertions(+), 12 deletions(-)
---
diff --git a/pango/meson.build b/pango/meson.build
index 4c055f52..f4b582ba 100644
--- a/pango/meson.build
+++ b/pango/meson.build
@@ -177,6 +177,7 @@ if build_pangoft2
     'pangofc-font.c',
     'pangofc-fontmap.c',
     'pangofc-decoder.c',
+    'pangofc-coverageorder.c',
     'pango-trace.c',
   ]
 
diff --git a/pango/pangofc-coverageorder-private.h b/pango/pangofc-coverageorder-private.h
new file mode 100644
index 00000000..6537ed06
--- /dev/null
+++ b/pango/pangofc-coverageorder-private.h
@@ -0,0 +1,40 @@
+/* Pango
+ * coverageorder.h:
+ *
+ * Copyright (C) 2020 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Matthias Clasen
+ */
+
+#ifndef __COVERAGE_ORDER_H__
+#define __COVERAGE_ORDER_H__
+
+#include <glib.h>
+#include <fontconfig/fontconfig.h>
+
+G_BEGIN_DECLS
+
+typedef struct _CoverageOrder CoverageOrder;
+
+CoverageOrder * coverage_order_new       (FcFontSet     *fonts);
+void            coverage_order_free      (CoverageOrder *co);
+gboolean        coverage_order_is_subset (CoverageOrder *co,
+                                          FcPattern     *p1,
+                                          FcPattern     *p2);
+
+G_END_DECLS
+
+#endif /* __COVERAGE_ORDER_H__ */
diff --git a/pango/pangofc-coverageorder.c b/pango/pangofc-coverageorder.c
new file mode 100644
index 00000000..86114b38
--- /dev/null
+++ b/pango/pangofc-coverageorder.c
@@ -0,0 +1,239 @@
+/* Pango
+ * coverageorder.c:
+ *
+ * Copyright (C) 2020 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Matthias Clasen
+ */
+
+#include "config.h"
+
+#include "pangofc-coverageorder-private.h"
+#include <glib.h>
+
+/* BitMatrix is a simple matrix of bits that can be
+ * addressed by their row and column.
+ */
+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;
+  int byte = pos / 8;
+  int bit = pos % 8;
+
+  return (b->bits[byte] & (1 << bit)) != 0;
+}
+
+static void
+bit_matrix_set (BitMatrix *b, int i, int j, gboolean value)
+{
+  int pos = i * b->cols + j;
+  int byte = pos / 8;
+  int bit = pos % 8;
+
+  if (value)
+    b->bits[byte] = b->bits[byte] | (1 << bit);
+  else
+    b->bits[byte] = b->bits[byte] & ~(1 << bit);
+}
+
+/* By coverage order, we mean the partial order that is defined on
+ * the fonts by the subset relation on their charsets. This order
+ * only depends on the font configuration, and can be computed
+ * ahead of time or even saved to disk.
+ *
+ * An important aspect of why this works is that in practice,
+ * many fonts have the same coverage, so our matrix stays much
+ * smaller than |fonts| * |fonts|.
+ */
+
+struct _CoverageOrder
+{
+  GHashTable *idx;
+  BitMatrix *order;
+};
+
+/*
+ * coverage_order_free:
+ *
+ * Frees a CoverageOrder struct and all associated memory.
+ */
+void
+coverage_order_free (CoverageOrder *co)
+{
+  g_hash_table_unref (co->idx);
+  bit_matrix_free (co->order);
+  g_free (co);
+}
+
+/*
+ * coverage_order_is_subset:
+ * @co: a #CoverageOrder
+ * @p1: a pattern
+ * @p2: another pattern
+ *
+ * Determines if the charset of @p1 is a subset
+ * of the charset of @p2.
+ *
+ * Returns: %TRUE if @p1 is a subset of @p2
+ */
+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);
+}
+
+/*
+ * coverage_order_new:
+ * @fonts: a set of fonts
+ *
+ * Compute the coverage order for the fonts in @fonts.
+ *
+ * Returns: a new #CoverageOrder
+ */
+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 ();
+
+  /* First group the fonts that have the same
+   * charset, by giving them the same 'index'.
+   */
+  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];
+        }
+    }
+
+  /* Now compute the full incidence matrix for the
+   * remaining charsets.
+   */
+  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;
+}
diff --git a/pango/pangofc-fontmap.c b/pango/pangofc-fontmap.c
index 746e8bd4..ba89c6f1 100644
--- a/pango/pangofc-fontmap.c
+++ b/pango/pangofc-fontmap.c
@@ -55,6 +55,7 @@
 #include "pango-enum-types.h"
 #include "pango-coverage-private.h"
 #include "pango-trace-private.h"
+#include "pangofc-coverageorder-private.h"
 #include <hb-ft.h>
 
 
@@ -167,6 +168,9 @@ struct _PangoFcFontMapPrivate
 
   FcConfig *config;
   FcFontSet *fonts;
+
+  CoverageOrder *coverage_order;
+  GCancellable *coverage_cancellable;
 };
 
 struct _PangoFcFontFaceData
@@ -1073,10 +1077,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 +1088,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 +1485,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);
@@ -2317,6 +2343,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)
@@ -2352,11 +2379,39 @@ pango_fc_font_map_get_config (PangoFcFontMap *fcfontmap)
   return fcfontmap->priv->config;
 }
 
+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 ();
@@ -2364,6 +2419,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;


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]