x11: cache X11 atoms

On every keymap notify event, the keymap should be refreshed, which
fetches the required X11 atoms. A big keymap might have a few hundred of
atoms.

A profile by a user has shown this *might* be slow when some intensive
amount of keymap activity is occurring. It might also be slow on a
remote X server.

While I'm not really sure this is the actual bottleneck, caching the
atoms is easy enough and only needs a couple kb of memory, so do that.

On the added bench-x11:

Before: retrieved 2500 keymaps from X in 11.233237s
After : retrieved 2500 keymaps from X in 1.592339s

Signed-off-by: Ran Benita <ran@unusedvar.com>

5 files changed, 171 insertions, 5 deletions

diff --git a/bench/x11.c b/bench/x11.c
new file mode 100644
index 0000000..2849385
--- /dev/null
+++ b/bench/x11.c
@@ -0,0 +1,108 @@
+/*
+ * Copyright © 2020 Ran Benita <ran@unusedvar.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+#include "config.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+#include <xcb/xkb.h>
+
+#include "xkbcommon/xkbcommon.h"
+#include "xkbcommon/xkbcommon-x11.h"
+
+#include "bench.h"
+
+#define BENCHMARK_ITERATIONS 2500
+
+int
+main(void)
+{
+    int ret;
+    xcb_connection_t *conn;
+    int32_t device_id;
+    struct xkb_context *ctx;
+    struct bench bench;
+    char *elapsed;
+
+    conn = xcb_connect(NULL, NULL);
+    if (!conn || xcb_connection_has_error(conn)) {
+        fprintf(stderr, "Couldn't connect to X server: error code %d\n",
+                conn ? xcb_connection_has_error(conn) : -1);
+        ret = -1;
+        goto err_out;
+    }
+
+    ret = xkb_x11_setup_xkb_extension(conn,
+                                      XKB_X11_MIN_MAJOR_XKB_VERSION,
+                                      XKB_X11_MIN_MINOR_XKB_VERSION,
+                                      XKB_X11_SETUP_XKB_EXTENSION_NO_FLAGS,
+                                      NULL, NULL, NULL, NULL);
+    if (!ret) {
+        fprintf(stderr, "Couldn't setup XKB extension\n");
+        goto err_conn;
+    }
+
+    device_id = xkb_x11_get_core_keyboard_device_id(conn);
+    if (device_id == -1) {
+        ret = -1;
+        fprintf(stderr, "Couldn't find core keyboard device\n");
+        goto err_conn;
+    }
+
+    ctx = xkb_context_new(XKB_CONTEXT_NO_FLAGS);
+    if (!ctx) {
+        ret = -1;
+        fprintf(stderr, "Couldn't create xkb context\n");
+        goto err_conn;
+    }
+
+    bench_start(&bench);
+    for (int i = 0; i < BENCHMARK_ITERATIONS; i++) {
+        struct xkb_keymap *keymap;
+        struct xkb_state *state;
+
+        keymap = xkb_x11_keymap_new_from_device(ctx, conn, device_id,
+                                                XKB_KEYMAP_COMPILE_NO_FLAGS);
+        assert(keymap);
+
+        state = xkb_x11_state_new_from_device(keymap, conn, device_id);
+        assert(state);
+
+        xkb_state_unref(state);
+        xkb_keymap_unref(keymap);
+    }
+    bench_stop(&bench);
+    ret = 0;
+
+    elapsed = bench_elapsed_str(&bench);
+    fprintf(stderr, "retrieved %d keymaps from X in %ss\n",
+            BENCHMARK_ITERATIONS, elapsed);
+    free(elapsed);
+
+    xkb_context_unref(ctx);
+err_conn:
+    xcb_disconnect(conn);
+err_out:
+    return ret == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
+}
diff --git a/meson.build b/meson.build
index f3b58e1..c815578 100644
--- a/meson.build
+++ b/meson.build
@@ -701,6 +701,13 @@ benchmark(
     executable('bench-compose', 'bench/compose.c', dependencies: test_dep),
     env: bench_env,
 )
+if get_option('enable-x11')
+  benchmark(
+      'x11',
+      executable('bench-x11', 'bench/x11.c', dependencies: x11_test_dep),
+      env: bench_env,
+  )
+endif
 
 
 # Documentation.
diff --git a/src/context.c b/src/context.c
index 4a6ac8e..71c2275 100644
--- a/src/context.c
+++ b/src/context.c
@@ -210,6 +210,7 @@ xkb_context_unref(struct xkb_context *ctx)
     if (!ctx || --ctx->refcnt > 0)
         return;
 
+    free(ctx->x11_atom_cache);
     xkb_context_include_path_clear(ctx);
     atom_table_free(ctx->atom_table);
     free(ctx);
@@ -323,6 +324,8 @@ xkb_context_new(enum xkb_context_flags flags)
         return NULL;
     }
 
+    ctx->x11_atom_cache = NULL;
+
     return ctx;
 }
 
diff --git a/src/context.h b/src/context.h
index ead2508..44367cc 100644
--- a/src/context.h
+++ b/src/context.h
@@ -45,6 +45,9 @@ struct xkb_context {
 
     struct atom_table *atom_table;
 
+    /* Used and allocated by xkbcommon-x11, free()d with the context. */
+    void *x11_atom_cache;
+
     /* Buffer for the *Text() functions. */
     char text_buffer[2048];
     size_t text_next;
diff --git a/src/x11/util.c b/src/x11/util.c
index 3959a5a..660d885 100644
--- a/src/x11/util.c
+++ b/src/x11/util.c
@@ -155,6 +155,20 @@ get_atom_name(xcb_connection_t *conn, xcb_atom_t atom, char **out)
     return true;
 }
 
+struct x11_atom_cache {
+    /*
+     * Invalidate the cache based on the XCB connection.
+     * X11 atoms are actually not per connection or client, but per X server
+     * session. But better be safe just in case we survive an X server restart.
+     */
+    xcb_connection_t *conn;
+    struct {
+        xcb_atom_t from;
+        xkb_atom_t to;
+    } cache[256];
+    size_t len;
+};
+
 bool
 adopt_atoms(struct xkb_context *ctx, xcb_connection_t *conn,
             const xcb_atom_t *from, xkb_atom_t *to, const size_t count)
@@ -163,24 +177,49 @@ adopt_atoms(struct xkb_context *ctx, xcb_connection_t *conn,
     xcb_get_atom_name_cookie_t cookies[SIZE];
     const size_t num_batches = ROUNDUP(count, SIZE) / SIZE;
 
+    if (!ctx->x11_atom_cache) {
+        ctx->x11_atom_cache = calloc(1, sizeof(struct x11_atom_cache));
+    }
+    /* Can be NULL in case the malloc failed. */
+    struct x11_atom_cache *cache = ctx->x11_atom_cache;
+    if (cache && cache->conn != conn) {
+        cache->conn = conn;
+        cache->len = 0;
+    }
+
+    memset(to, 0, count * sizeof(*to));
+
     /* Send and collect the atoms in batches of reasonable SIZE. */
     for (size_t batch = 0; batch < num_batches; batch++) {
         const size_t start = batch * SIZE;
         const size_t stop = MIN((batch + 1) * SIZE, count);
 
         /* Send. */
-        for (size_t i = start; i < stop; i++)
-            if (from[i] != XCB_ATOM_NONE)
+        for (size_t i = start; i < stop; i++) {
+            bool cache_hit = false;
+            if (cache) {
+                for (size_t c = 0; c < cache->len; c++) {
+                    if (cache->cache[c].from == from[i]) {
+                        to[i] = cache->cache[c].to;
+                        cache_hit = true;
+                        break;
+                    }
+                }
+            }
+            if (!cache_hit && from[i] != XCB_ATOM_NONE)
                 cookies[i % SIZE] = xcb_get_atom_name(conn, from[i]);
+        }
 
         /* Collect. */
         for (size_t i = start; i < stop; i++) {
             xcb_get_atom_name_reply_t *reply;
 
-            if (from[i] == XCB_ATOM_NONE) {
-                to[i] = XKB_ATOM_NONE;
+            if (from[i] == XCB_ATOM_NONE)
+                continue;
+
+            /* Was filled from cache. */
+            if (to[i] != 0)
                 continue;
-            }
 
             reply = xcb_get_atom_name_reply(conn, cookies[i % SIZE], NULL);
             if (!reply)
@@ -194,6 +233,12 @@ adopt_atoms(struct xkb_context *ctx, xcb_connection_t *conn,
             if (to[i] == XKB_ATOM_NONE)
                 goto err_discard;
 
+            if (cache && cache->len < ARRAY_SIZE(cache->cache)) {
+                size_t idx = cache->len++;
+                cache->cache[idx].from = from[i];
+                cache->cache[idx].to = to[i];
+            }
+
             continue;
 
             /*