Re: Slow down with: 'Make "info qom-tree" show children sorted'

[Markus Armbruster <armbru@redhat.com>]

David Gibson <dgibson@redhat.com> writes:

> On Tue, 07 Jul 2020 14:00:06 +0200
> Markus Armbruster <armbru@redhat.com> wrote:
>
>> Paolo Bonzini <pbonzini@redhat.com> writes:
>> 
>> > On 07/07/20 07:33, Markus Armbruster wrote:  
>> >> Philippe Mathieu-Daudé <philmd@redhat.com> writes:
>> >>   
>> >>> On 7/7/20 6:45 AM, Thomas Huth wrote:  
>> >>>> On 27/05/2020 10.47, Markus Armbruster wrote:  
>> >>>>> "info qom-tree" prints children in unstable order.  This is a pain
>> >>>>> when diffing output for different versions to find change.  Print it
>> >>>>> sorted.
>> >>>>>
>> >>>>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> >>>>> ---
>> >>>>>  qom/qom-hmp-cmds.c | 24 ++++++++++++++++--------
>> >>>>>  1 file changed, 16 insertions(+), 8 deletions(-)  
>> >>>>
>> >>>>  Hi Markus,
>> >>>>
>> >>>> this patch causes a slow down of the qtests which becomes quite massive
>> >>>> when e.g. using the ppc64 and thourough testing. When I'm running
>> >>>>
>> >>>> QTEST_QEMU_BINARY="ppc64-softmmu/qemu-system-ppc64" time \
>> >>>> ./tests/qtest/device-introspect-test -m slow | tail -n 10
>> >>>>
>> >>>> the test runs for ca. 6m40s here before the patch got applied, and for
>> >>>> mor than 20 minutes after the patch got applied!  
>> >> 
>> >> That's surprising.  
>> >
>> > It's a bit surprising indeed, but on the other hand using
>> > g_queue_insert_sorted results in a quadratic loop.  
>> 
>> The surprising part is that n turns out to be large enough for n^2 to
>> matter *that* much.
>
> Is this another consequence of the ludicrous number of QOM objects we
> create for LMB DRCs (one for every 256MiB of guest RAM)?  Avoiding that
> is on my list.

You're talking about machine pseries, I presume.  With
print_qom_composition() patched to print the number of children, I get

    $ echo -e 'info qom-tree\nq' | ../qemu/bld/ppc64-softmmu/qemu-system-ppc64 -S -display none -M pseries -accel qtest -monitor stdio | grep '###' | sort | uniq -c | sort -k 3n
        360 ### 0 children
          5 ### 1 children
          5 ### 2 children
          2 ### 3 children
          1 ### 4 children
          1 ### 15 children
          1 ### 16 children
          1 ### 18 children
          1 ### 37 children
          1 ### 266 children

The outlier is

        /device[5] (spapr-pci-host-bridge)

due to its 256 spapr-drc-pci children.

I found quite a few machines with similar outliers.  ARM machines nuri
and smdkc210 together take the cake: they each have a node with 513
children.

My stupid n^2 sort is unnoticable in normal, human usage even for n=513.

>                 Though avoiding a n^2 behaviour here is probably a good
> idea anyway.

Agreed.