qom: Make info qom-tree sort children more efficiently

Commit e8c9e65816 "qom: Make "info qom-tree" show children sorted"
sorts children the simple, stupid, quadratic way.  I thought the
number of children would be small enough for this not to matter.  I
was wrong: there are outliers with several hundred children, e.g ARM
machines nuri and smdkc210 each have a node with 513 children.

While n^2 sorting isn't noticeable in normal, human usage even for
n=513, it can be quite noticeable in certain automated tests.  In
particular, the sort made device-introspect-test even slower.  Commit
3e7b80f84d "tests: improve performance of device-introspect-test" just
fixed that by cutting back its excessive use of "info qom-tree".
Sorting more efficiently makes sense regardless, so do it.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Message-Id: <20200714160202.3121879-6-armbru@redhat.com>
Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>

1 files changed, 13 insertions, 12 deletions

diff --git a/qom/qom-hmp-cmds.c b/qom/qom-hmp-cmds.c
index 4032c96..8861a10 100644
--- a/qom/qom-hmp-cmds.c
+++ b/qom/qom-hmp-cmds.c
@@ -94,25 +94,23 @@ typedef struct QOMCompositionState {
 
 static void print_qom_composition(Monitor *mon, Object *obj, int indent);
 
-static int qom_composition_compare(const void *a, const void *b, void *ignore)
+static int qom_composition_compare(const void *a, const void *b)
 {
-    return g_strcmp0(object_get_canonical_path_component(a),
-                     object_get_canonical_path_component(b));
+    return g_strcmp0(object_get_canonical_path_component(*(Object **)a),
+                     object_get_canonical_path_component(*(Object **)b));
 }
 
 static int insert_qom_composition_child(Object *obj, void *opaque)
 {
-    GQueue *children = opaque;
-
-    g_queue_insert_sorted(children, obj, qom_composition_compare, NULL);
+    g_array_append_val(opaque, obj);
     return 0;
 }
 
 static void print_qom_composition(Monitor *mon, Object *obj, int indent)
 {
+    GArray *children = g_array_new(false, false, sizeof(Object *));
     const char *name;
-    GQueue children;
-    Object *child;
+    int i;
 
     if (obj == object_get_root()) {
         name = "";
@@ -122,11 +120,14 @@ static void print_qom_composition(Monitor *mon, Object *obj, int indent)
     monitor_printf(mon, "%*s/%s (%s)\n", indent, "", name,
                    object_get_typename(obj));
 
-    g_queue_init(&children);
-    object_child_foreach(obj, insert_qom_composition_child, &children);
-    while ((child = g_queue_pop_head(&children))) {
-        print_qom_composition(mon, child, indent + 2);
+    object_child_foreach(obj, insert_qom_composition_child, children);
+    g_array_sort(children, qom_composition_compare);
+
+    for (i = 0; i < children->len; i++) {
+        print_qom_composition(mon, g_array_index(children, Object *, i),
+                              indent + 2);
     }
+    g_array_free(children, TRUE);
 }
 
 void hmp_info_qom_tree(Monitor *mon, const QDict *dict)