[gtk/speed-up-event-matching] keymap: Cache key info

[Matthias Clasen <matthiasc src gnome org>]

commit 29b4c8db8dfb91e0cdeb002c42e07ca97191a002
Author: Matthias Clasen <mclasen redhat com>
Date:   Thu Apr 30 00:33:06 2020 -0400

    keymap: Cache key info
    
    We currently calling gdk_display_map_keyval up to
    once per key event per shortcut trigger, and that function
    does an expensive loop over the entire keymap and
    allocates an array. Avoid this by caching the entries
    in a single array, and have a lookup table for finding
    the entries for a keyval.
    
    To do this, change the GdkKeymap.get_entries_for_keyval
    signature. This is possible now, since keymaps are no
    longer public API.

 gdk/broadway/gdkkeys-broadway.c | 19 ++++-----
 gdk/gdkevents.c                 | 12 ++----
 gdk/gdkkeys.c                   | 94 +++++++++++++++++++++++++++++++++++++----
 gdk/gdkkeysprivate.h            |  9 +++-
 gdk/wayland/gdkkeys-wayland.c   | 16 +++----
 gdk/win32/gdkkeys-win32.c       | 26 ++----------
 gdk/x11/gdkkeys-x11.c           | 29 +++----------
 7 files changed, 120 insertions(+), 85 deletions(-)
---
diff --git a/gdk/broadway/gdkkeys-broadway.c b/gdk/broadway/gdkkeys-broadway.c
index f58f332dc6..60d8715663 100644
--- a/gdk/broadway/gdkkeys-broadway.c
+++ b/gdk/broadway/gdkkeys-broadway.c
@@ -123,17 +123,16 @@ gdk_broadway_keymap_get_scroll_lock_state (GdkKeymap *keymap)
 
 static gboolean
 gdk_broadway_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
-                                           guint          keyval,
-                                           GdkKeymapKey **keys,
-                                           gint          *n_keys)
+                                            guint          keyval,
+                                            GArray        *retval)
 {
-  if (n_keys)
-    *n_keys = 1;
-  if (keys)
-    {
-      *keys = g_new0 (GdkKeymapKey, 1);
-      (*keys)->keycode = keyval;
-    }
+  GdkKeymapKey key;
+
+  key.keycode = keyval;
+  key.group = 0;
+  key.level = 0;
+
+  g_array_append_val (retval, key);
 
   return TRUE;
 }
diff --git a/gdk/gdkevents.c b/gdk/gdkevents.c
index 41706885af..3393e944fa 100644
--- a/gdk/gdkevents.c
+++ b/gdk/gdkevents.c
@@ -1604,6 +1604,7 @@ gdk_key_event_matches (GdkEvent        *event,
                        GdkModifierType  modifiers)
 {
   GdkKeyEvent *self = (GdkKeyEvent *) event;
+  GdkKeymap *keymap;
   guint keycode;
   GdkModifierType state;
   guint ev_keyval;
@@ -1644,7 +1645,6 @@ gdk_key_event_matches (GdkEvent        *event,
     {
       /* modifier match */
       GdkKeymapKey *keys;
-      int n_keys;
       int i;
       guint key;
 
@@ -1667,23 +1667,19 @@ gdk_key_event_matches (GdkEvent        *event,
           return GDK_KEY_MATCH_EXACT;
         }
 
-      gdk_display_map_keyval (gdk_event_get_display (event), keyval, &keys, &n_keys);
+      keymap = gdk_display_get_keymap (gdk_event_get_display (event));
+      keys = gdk_keymap_get_cached_entries_for_keyval (keymap, keyval);
 
-      for (i = 0; i < n_keys; i++)
+      for (i = 0; keys[i].keycode != 0; i++)
         {
           if (keys[i].keycode == keycode &&
               keys[i].level == level &&
               /* Only match for group if it's an accel mod */
               (!group_mod_is_accel_mod || keys[i].group == layout))
             {
-              /* partial match */
-              g_free (keys);
-
               return GDK_KEY_MATCH_PARTIAL;
             }
         }
-
-      g_free (keys);
     }
 
   return GDK_KEY_MATCH_NONE;
diff --git a/gdk/gdkkeys.c b/gdk/gdkkeys.c
index 469d204e0b..ebc4d734f4 100644
--- a/gdk/gdkkeys.c
+++ b/gdk/gdkkeys.c
@@ -195,14 +195,44 @@ gdk_keymap_set_property (GObject      *object,
     }
 }
 
+static void
+gdk_keymap_finalize (GObject *object)
+{
+  GdkKeymap *keymap = GDK_KEYMAP (object);
+
+  g_array_free (keymap->cached_keys, TRUE);
+  g_hash_table_unref (keymap->cache);
+
+  G_OBJECT_CLASS (gdk_keymap_parent_class)->finalize (object);
+}
+
+static void
+gdk_keymap_keys_changed (GdkKeymap *keymap)
+{
+  GdkKeymapKey key;
+
+  g_array_set_size (keymap->cached_keys, 0);
+
+  key.keycode = 0;
+  key.group = 0;
+  key.level = 0;
+
+  g_array_append_val (keymap->cached_keys, key);
+
+  g_hash_table_remove_all (keymap->cache);
+}
+
 static void
 gdk_keymap_class_init (GdkKeymapClass *klass)
 {
   GObjectClass *object_class = G_OBJECT_CLASS (klass);
 
+  object_class->finalize = gdk_keymap_finalize;
   object_class->get_property = gdk_keymap_get_property;
   object_class->set_property = gdk_keymap_set_property;
 
+  klass->keys_changed = gdk_keymap_keys_changed;
+
   props[PROP_DISPLAY] =
     g_param_spec_object ("display",
                          "Display",
@@ -237,13 +267,13 @@ gdk_keymap_class_init (GdkKeymapClass *klass)
    */
   signals[KEYS_CHANGED] =
     g_signal_new (g_intern_static_string ("keys-changed"),
-                 G_OBJECT_CLASS_TYPE (object_class),
-                 G_SIGNAL_RUN_LAST,
-                 G_STRUCT_OFFSET (GdkKeymapClass, keys_changed),
-                 NULL, NULL,
-                 NULL,
-                 G_TYPE_NONE,
-                 0);
+                  G_OBJECT_CLASS_TYPE (object_class),
+                  G_SIGNAL_RUN_FIRST,
+                  G_STRUCT_OFFSET (GdkKeymapClass, keys_changed),
+                  NULL, NULL,
+                  NULL,
+                  G_TYPE_NONE,
+                  0);
 
   /**
    * GdkKeymap::state-changed:
@@ -267,6 +297,17 @@ gdk_keymap_class_init (GdkKeymapClass *klass)
 static void
 gdk_keymap_init (GdkKeymap *keymap)
 {
+  GdkKeymapKey key;
+
+  keymap->cached_keys = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+
+  key.keycode = 0;
+  key.group = 0;
+  key.level = 0;
+
+  g_array_append_val (keymap->cached_keys, key);
+
+  keymap->cache = g_hash_table_new (g_direct_hash, g_direct_equal);
 }
 
 /**
@@ -502,13 +543,48 @@ gdk_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
                                    GdkKeymapKey **keys,
                                    gint          *n_keys)
 {
+  GArray *array;
+
   g_return_val_if_fail (GDK_IS_KEYMAP (keymap), FALSE);
   g_return_val_if_fail (keys != NULL, FALSE);
   g_return_val_if_fail (n_keys != NULL, FALSE);
   g_return_val_if_fail (keyval != 0, FALSE);
 
-  return GDK_KEYMAP_GET_CLASS (keymap)->get_entries_for_keyval (keymap, keyval,
-                                                                keys, n_keys);
+  array = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+
+  GDK_KEYMAP_GET_CLASS (keymap)->get_entries_for_keyval (keymap, keyval, array);
+
+  *n_keys = array->len;
+  *keys = (GdkKeymapKey *)g_array_free (array, FALSE);
+
+  return TRUE;
+}
+
+GdkKeymapKey *
+gdk_keymap_get_cached_entries_for_keyval (GdkKeymap *keymap,
+                                          guint      keyval)
+{
+  guint offset;
+
+  offset = GPOINTER_TO_UINT (g_hash_table_lookup (keymap->cache, GUINT_TO_POINTER (keyval)));
+  if (offset == 0)
+    {
+      GdkKeymapKey key;
+
+      offset = keymap->cached_keys->len;
+
+      GDK_KEYMAP_GET_CLASS (keymap)->get_entries_for_keyval (keymap, keyval, keymap->cached_keys);
+
+      key.keycode = 0;
+      key.group = 0;
+      key.level = 0;
+
+      g_array_append_val (keymap->cached_keys, key);
+
+      g_hash_table_insert (keymap->cache, GUINT_TO_POINTER (keyval), GUINT_TO_POINTER (offset));
+    }
+
+  return (GdkKeymapKey *)&g_array_index (keymap->cached_keys, GdkKeymapKey, offset);
 }
 
 /**
diff --git a/gdk/gdkkeysprivate.h b/gdk/gdkkeysprivate.h
index c7cf7424b6..d8fe13d528 100644
--- a/gdk/gdkkeysprivate.h
+++ b/gdk/gdkkeysprivate.h
@@ -43,8 +43,7 @@ struct _GdkKeymapClass
   gboolean (* get_scroll_lock_state)    (GdkKeymap *keymap);
   gboolean (* get_entries_for_keyval)   (GdkKeymap     *keymap,
                                          guint          keyval,
-                                         GdkKeymapKey **keys,
-                                         gint          *n_keys);
+                                         GArray        *array);
   gboolean (* get_entries_for_keycode)  (GdkKeymap     *keymap,
                                          guint          hardware_keycode,
                                          GdkKeymapKey **keys,
@@ -73,6 +72,9 @@ struct _GdkKeymap
 {
   GObject     parent_instance;
   GdkDisplay *display;
+
+  GArray *cached_keys;
+  GHashTable *cache;
 };
 
 GType gdk_keymap_get_type (void) G_GNUC_CONST;
@@ -106,6 +108,9 @@ gboolean       gdk_keymap_get_num_lock_state       (GdkKeymap           *keymap)
 gboolean       gdk_keymap_get_scroll_lock_state    (GdkKeymap           *keymap);
 guint          gdk_keymap_get_modifier_state       (GdkKeymap           *keymap);
 
+GdkKeymapKey * gdk_keymap_get_cached_entries_for_keyval (GdkKeymap *keymap,
+                                                         guint      keyval);
+
 G_END_DECLS
 
 #endif
diff --git a/gdk/wayland/gdkkeys-wayland.c b/gdk/wayland/gdkkeys-wayland.c
index 1b98c73e85..802463298e 100644
--- a/gdk/wayland/gdkkeys-wayland.c
+++ b/gdk/wayland/gdkkeys-wayland.c
@@ -126,17 +126,14 @@ gdk_wayland_keymap_get_scroll_lock_state (GdkKeymap *keymap)
 }
 
 static gboolean
-gdk_wayland_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
-                                          guint          keyval,
-                                          GdkKeymapKey **keys,
-                                          gint          *n_keys)
+gdk_wayland_keymap_get_entries_for_keyval (GdkKeymap *keymap,
+                                           guint      keyval,
+                                           GArray    *retval)
 {
   struct xkb_keymap *xkb_keymap = GDK_WAYLAND_KEYMAP (keymap)->xkb_keymap;
-  GArray *retval;
   guint keycode;
   xkb_keycode_t min_keycode, max_keycode;
-
-  retval = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+  guint len = retval->len;
 
   min_keycode = xkb_keymap_min_keycode (xkb_keymap);
   max_keycode = xkb_keymap_max_keycode (xkb_keymap);
@@ -170,10 +167,7 @@ gdk_wayland_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
         }
     }
 
-  *n_keys = retval->len;
-  *keys = (GdkKeymapKey*) g_array_free (retval, FALSE);
-
-  return TRUE;
+  return retval->len > len;
 }
 
 static gboolean
diff --git a/gdk/win32/gdkkeys-win32.c b/gdk/win32/gdkkeys-win32.c
index bae9a8e24d..972008492d 100644
--- a/gdk/win32/gdkkeys-win32.c
+++ b/gdk/win32/gdkkeys-win32.c
@@ -1283,19 +1283,14 @@ gdk_win32_keymap_get_scroll_lock_state (GdkKeymap *keymap)
 static gboolean
 gdk_win32_keymap_get_entries_for_keyval (GdkKeymap     *gdk_keymap,
                                          guint          keyval,
-                                         GdkKeymapKey **keys,
-                                         gint          *n_keys)
+                                         GArray        *retval)
 {
-  GArray *retval;
   GdkKeymap *default_keymap = gdk_display_get_keymap (gdk_display_get_default ());
+  guint len = retval->len;
 
   g_return_val_if_fail (gdk_keymap == NULL || GDK_IS_KEYMAP (gdk_keymap), FALSE);
-  g_return_val_if_fail (keys != NULL, FALSE);
-  g_return_val_if_fail (n_keys != NULL, FALSE);
   g_return_val_if_fail (keyval != 0, FALSE);
 
-  retval = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
-
   /* Accept only the default keymap */
   if (gdk_keymap == NULL || gdk_keymap == default_keymap)
     {
@@ -1344,7 +1339,7 @@ gdk_win32_keymap_get_entries_for_keyval (GdkKeymap     *gdk_keymap,
 
       g_print ("gdk_keymap_get_entries_for_keyval: %#.04x (%s):",
                keyval, gdk_keyval_name (keyval));
-      for (i = 0; i < retval->len; i++)
+      for (i = len; i < retval->len; i++)
         {
           GdkKeymapKey *entry = (GdkKeymapKey *) retval->data + i;
           g_print ("  %#.02x %d %d", entry->keycode, entry->group, entry->level);
@@ -1353,20 +1348,7 @@ gdk_win32_keymap_get_entries_for_keyval (GdkKeymap     *gdk_keymap,
     }
 #endif
 
-  if (retval->len > 0)
-    {
-      *keys = (GdkKeymapKey*) retval->data;
-      *n_keys = retval->len;
-    }
-  else
-    {
-      *keys = NULL;
-      *n_keys = 0;
-    }
-
-  g_array_free (retval, retval->len > 0 ? FALSE : TRUE);
-
-  return *n_keys > 0;
+  return len < retval->len;
 }
 
 static gboolean
diff --git a/gdk/x11/gdkkeys-x11.c b/gdk/x11/gdkkeys-x11.c
index f3c777390d..a322ff27c0 100644
--- a/gdk/x11/gdkkeys-x11.c
+++ b/gdk/x11/gdkkeys-x11.c
@@ -819,15 +819,12 @@ gdk_x11_keymap_get_modifier_state (GdkKeymap *keymap)
 }
 
 static gboolean
-gdk_x11_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
-                                       guint          keyval,
-                                       GdkKeymapKey **keys,
-                                       gint          *n_keys)
+gdk_x11_keymap_get_entries_for_keyval (GdkKeymap *keymap,
+                                       guint      keyval,
+                                       GArray    *retval)
 {
   GdkX11Keymap *keymap_x11 = GDK_X11_KEYMAP (keymap);
-  GArray *retval;
-
-  retval = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+  guint len = retval->len;
 
 #ifdef HAVE_XKB
   if (KEYMAP_USE_XKB (keymap))
@@ -870,8 +867,7 @@ gdk_x11_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
 
                   g_array_append_val (retval, key);
 
-                  g_assert (XkbKeySymEntry (xkb, keycode, level, group) ==
-                            keyval);
+                  g_assert (XkbKeySymEntry (xkb, keycode, level, group) == keyval);
                 }
 
               ++level;
@@ -923,20 +919,7 @@ gdk_x11_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
         }
     }
 
-  if (retval->len > 0)
-    {
-      *keys = (GdkKeymapKey*) retval->data;
-      *n_keys = retval->len;
-    }
-  else
-    {
-      *keys = NULL;
-      *n_keys = 0;
-    }
-
-  g_array_free (retval, retval->len > 0 ? FALSE : TRUE);
-
-  return *n_keys > 0;
+  return retval->len > len;
 }
 
 static gboolean