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>
---
 qom/qom-hmp-cmds.c | 25 +++++++++++++------------
 1 file changed, 13 insertions(+), 12 deletions(-)

diff --git a/qom/qom-hmp-cmds.c b/qom/qom-hmp-cmds.c
index 4032c96089..8861a109d5 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)
-- 
2.26.2

* Markus Armbruster (armbru@redhat.com) wrote:
> 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.

Big Power systems can have thousands.

> 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>
> ---
>  qom/qom-hmp-cmds.c | 25 +++++++++++++------------
>  1 file changed, 13 insertions(+), 12 deletions(-)
> 
> diff --git a/qom/qom-hmp-cmds.c b/qom/qom-hmp-cmds.c
> index 4032c96089..8861a109d5 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);

So I think that's OK, so :

Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>

Can you just convince me that 'TRUE' in the array_free?

Dave

>  }
>  
>  void hmp_info_qom_tree(Monitor *mon, const QDict *dict)
> -- 
> 2.26.2
> 
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

"Dr. David Alan Gilbert" <dgilbert@redhat.com> writes:

> * Markus Armbruster (armbru@redhat.com) wrote:
>> 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.
>
> Big Power systems can have thousands.
>
>> 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>
>> ---
>>  qom/qom-hmp-cmds.c | 25 +++++++++++++------------
>>  1 file changed, 13 insertions(+), 12 deletions(-)
>> 
>> diff --git a/qom/qom-hmp-cmds.c b/qom/qom-hmp-cmds.c
>> index 4032c96089..8861a109d5 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);
>
> So I think that's OK, so :
>
> Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
>
> Can you just convince me that 'TRUE' in the array_free?

g_array_free(children, TRUE) frees both children and children->data.  It
returns null.  This is what we want here.

g_array_free(children, FALSE) frees only children, and returns
children->data.  Occasionally useful.

https://developer.gnome.org/glib/2.62/glib-Arrays.html#g-array-free

I definitely would have made this two separate functions.

Thanks!