[gnome-software] odrs: Use a single GArray for loaded ratings data

[Richard Hughes <rhughes src gnome org>]

commit 7b4284f8d87c1549b44bc8f76201ad96d9f8d280
Author: Philip Withnall <withnall endlessm com>
Date:   Mon Jun 1 15:31:36 2020 +0100

    odrs: Use a single GArray for loaded ratings data
    
    This saves more than 4000 allocations and around 1MB of heap memory.
    
    Previously, the ratings data was inserted into a hash table, allocating
    the key, value, and various internal allocations inside the hash table
    in GLib.
    
    With this change, ratings data is stored in one contiguous `GArray`
    allocation, which reduces fragmentation and means that only one strdup
    is needed per additional app in the ratings data.
    
    Conversely, the new approach means that lookups of ratings data (when
    refining apps) use a binary search of the array, rather than a hash
    table lookup. This will be a little slower, but should not be noticeably
    slower. (It’s hard to profile the exact effect, though.)
    
    This relies on `g_array_binary_search()`, which was released in GLib
    2.62. A copy is included here so gnome-software’s dependency doesn’t
    have to be bumped.
    
    Signed-off-by: Philip Withnall <withnall endlessm com>

 plugins/odrs/gs-plugin-odrs.c | 140 ++++++++++++++++++++++++++++++++++--------
 1 file changed, 113 insertions(+), 27 deletions(-)
---
diff --git a/plugins/odrs/gs-plugin-odrs.c b/plugins/odrs/gs-plugin-odrs.c
index c8dca5e0..bcc34613 100644
--- a/plugins/odrs/gs-plugin-odrs.c
+++ b/plugins/odrs/gs-plugin-odrs.c
@@ -19,15 +19,92 @@
  * Provides review data from the Open Desktop Ratings Serice.
  */
 
+#if !GLIB_CHECK_VERSION(2, 62, 0)
+typedef struct
+{
+  guint8 *data;
+  guint   len;
+  guint   alloc;
+  guint   elt_size;
+  guint   zero_terminated : 1;
+  guint   clear : 1;
+  gatomicrefcount ref_count;
+  GDestroyNotify clear_func;
+} GRealArray;
+
+gboolean
+g_array_binary_search (GArray        *array,
+                       gconstpointer  target,
+                       GCompareFunc   compare_func,
+                       guint         *out_match_index)
+{
+  gboolean result = FALSE;
+  GRealArray *_array = (GRealArray *) array;
+  guint left, middle, right;
+  gint val;
+
+  g_return_val_if_fail (_array != NULL, FALSE);
+  g_return_val_if_fail (compare_func != NULL, FALSE);
+
+  if (G_LIKELY(_array->len))
+    {
+      left = 0;
+      right = _array->len - 1;
+
+      while (left <= right)
+        {
+          middle = left + (right - left) / 2;
+
+          val = compare_func (_array->data + (_array->elt_size * middle), target);
+          if (val == 0)
+            {
+              result = TRUE;
+              break;
+            }
+          else if (val < 0)
+            left = middle + 1;
+          else if (/* val > 0 && */ middle > 0)
+            right = middle - 1;
+          else
+            break;  /* element not found */
+        }
+    }
+
+  if (result && out_match_index != NULL)
+    *out_match_index = middle;
+
+  return result;
+}
+#endif  /* glib < 2.62.0 */
+
 #define ODRS_REVIEW_CACHE_AGE_MAX              237000 /* 1 week */
 #define ODRS_REVIEW_NUMBER_RESULTS_MAX         20
 
+/* Element in priv->ratings, all allocated in one big block and sorted
+ * alphabetically to reduce the number of allocations and fragmentation. */
+typedef struct {
+       gchar *app_id;  /* (owned) */
+       guint32 n_star_ratings[6];
+} GsOdrsRating;
+
+static int
+rating_compare (const GsOdrsRating *a, const GsOdrsRating *b)
+{
+       return g_strcmp0 (a->app_id, b->app_id);
+}
+
+static void
+rating_clear (GsOdrsRating *rating)
+{
+       g_free (rating->app_id);
+}
+
 struct GsPluginData {
        GSettings               *settings;
        gchar                   *distro;
        gchar                   *user_hash;
        gchar                   *review_server;
-       GHashTable              *ratings;  /* (mutex ratings_mutex) (owned) (nullable) */
+       GArray                  *ratings;  /* (element-type GsOdrsRating) (mutex ratings_mutex) (owned) 
(nullable) */
        GMutex                   ratings_mutex;
        GsApp                   *cached_origin;
 };
@@ -84,24 +161,22 @@ gs_plugin_initialize (GsPlugin *plugin)
        gs_plugin_set_appstream_id (plugin, "org.gnome.Software.Plugin.Odrs");
 }
 
-static GArray *
-gs_plugin_odrs_load_ratings_for_app (JsonObject *json_app)
+static gboolean
+gs_plugin_odrs_load_ratings_for_app (JsonObject *json_app, const gchar *app_id, GsOdrsRating *rating_out)
 {
-       GArray *ratings;
-       guint64 tmp;
        guint i;
        const gchar *names[] = { "star0", "star1", "star2", "star3",
                                 "star4", "star5", NULL };
 
-       ratings = g_array_sized_new (FALSE, TRUE, sizeof(guint32), 6);
        for (i = 0; names[i] != NULL; i++) {
                if (!json_object_has_member (json_app, names[i]))
-                       continue;
-               tmp = (guint64) json_object_get_int_member (json_app, names[i]);
-               g_array_append_val (ratings, tmp);
+                       return FALSE;
+               rating_out->n_star_ratings[i] = (guint64) json_object_get_int_member (json_app, names[i]);
        }
 
-       return ratings;
+       rating_out->app_id = g_strdup (app_id);
+
+       return TRUE;
 }
 
 static gboolean
@@ -112,12 +187,9 @@ gs_plugin_odrs_load_ratings (GsPlugin *plugin, const gchar *fn, GError **error)
        JsonObject *json_item;
        g_autoptr(GList) apps = NULL;
        g_autoptr(JsonParser) json_parser = NULL;
-       g_autoptr(GHashTable) new_ratings = NULL;
+       g_autoptr(GArray) new_ratings = NULL;
        g_autoptr(GMutexLocker) locker = NULL;
 
-       new_ratings = g_hash_table_new_full (g_str_hash, g_str_equal,
-                                            g_free, (GDestroyNotify) g_array_unref);
-
        /* parse the data and find the success */
        json_parser = json_parser_new ();
        if (!json_parser_load_from_file (json_parser, fn, error)) {
@@ -140,24 +212,31 @@ gs_plugin_odrs_load_ratings (GsPlugin *plugin, const gchar *fn, GError **error)
                return FALSE;
        }
 
-       /* parse each app */
        json_item = json_node_get_object (json_root);
+
+       new_ratings = g_array_sized_new (FALSE,  /* don’t zero-terminate */
+                                        FALSE,  /* don’t clear */
+                                        sizeof (GsOdrsRating),
+                                        json_object_get_size (json_item));
+       g_array_set_clear_func (new_ratings, (GDestroyNotify) rating_clear);
+
+       /* parse each app */
        apps = json_object_get_members (json_item);
        for (GList *l = apps; l != NULL; l = l->next) {
                const gchar *app_id = (const gchar *) l->data;
                JsonObject *json_app = json_object_get_object_member (json_item, app_id);
-               g_autoptr(GArray) ratings = NULL;;
-               ratings = gs_plugin_odrs_load_ratings_for_app (json_app);
-               if (ratings->len == 6) {
-                       g_hash_table_insert (new_ratings,
-                                            g_strdup (app_id),
-                                            g_array_ref (ratings));
-               }
+               GsOdrsRating rating;
+
+               if (gs_plugin_odrs_load_ratings_for_app (json_app, app_id, &rating))
+                       g_array_append_val (new_ratings, rating);
        }
 
+       /* Allow for binary searches later. */
+       g_array_sort (new_ratings, (GCompareFunc) rating_compare);
+
        /* Update the shared state */
        locker = g_mutex_locker_new (&priv->ratings_mutex);
-       g_clear_pointer (&priv->ratings, g_hash_table_unref);
+       g_clear_pointer (&priv->ratings, g_array_unref);
        priv->ratings = g_steal_pointer (&new_ratings);
 
        return TRUE;
@@ -225,7 +304,7 @@ gs_plugin_destroy (GsPlugin *plugin)
        g_free (priv->user_hash);
        g_free (priv->distro);
        g_free (priv->review_server);
-       g_clear_pointer (&priv->ratings, g_hash_table_unref);
+       g_clear_pointer (&priv->ratings, g_array_unref);
        g_object_unref (priv->settings);
        g_object_unref (priv->cached_origin);
        g_mutex_clear (&priv->ratings_mutex);
@@ -532,12 +611,19 @@ gs_plugin_odrs_refine_ratings (GsPlugin *plugin,
 
        for (guint i = 0; i < reviewable_ids->len; i++) {
                const gchar *id = g_ptr_array_index (reviewable_ids, i);
-               GArray *ratings_tmp = g_hash_table_lookup (priv->ratings, id);
-               if (ratings_tmp == NULL)
+               const GsOdrsRating search_rating = { id, { 0, }};
+               guint found_index;
+               const GsOdrsRating *found_rating;
+
+               if (!g_array_binary_search (priv->ratings, &search_rating,
+                                           (GCompareFunc) rating_compare, &found_index))
                        continue;
+
+               found_rating = &g_array_index (priv->ratings, GsOdrsRating, found_index);
+
                /* copy into accumulator array */
                for (guint j = 0; j < 6; j++)
-                       ratings_raw[j] += g_array_index (ratings_tmp, guint32, j);
+                       ratings_raw[j] += found_rating->n_star_ratings[j];
                cnt++;
        }
        if (cnt == 0)