Re: [RFC PATCH] qobject: Rewrite implementation of QDict for in-order traversal

[Daniel P . Berrangé]

On Tue, Jul 05, 2022 at 11:54:21AM +0200, Markus Armbruster wrote:
> QDict is implemented as a simple hash table of fixed size.  Observe:
> 
> * Slow for large n.  Not sure this matters.
> 
> * A QDict with n entries takes 4120 + n * 32 bytes on my box.  Wastes
>   space for small n, which is a common case.
> 
> * Order of traversal depends on the hash function and on insertion
>   order, because it iterates first over buckets, then collision
>   chains.
> 
> * Special code ensures qdict_size() takes constant time.
> 
> Replace the hash table by a linked list.  Observe:
> 
> * Even slower for large n.  Might be bad enough to matter.
> 
> * A QDict with n entries takes 32 + n * 24 bytes.
> 
> * Traversal is in insertion order.
> 
> * qdict_size() is linear in the number of entries.
> 
> This is an experiment.  Do not commit to master as is.
> 
> The change of traversal order affects expected test output.  I updated
> only the tests covered by "make check" so far.  I expect some more to
> hide under tests/qemu-iotests/.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  include/qapi/qmp/qdict.h              |  15 +-
>  qobject/qdict.c                       | 104 +--
>  tests/unit/check-qdict.c              |   2 +-
>  tests/unit/check-qobject.c            |   2 +-
>  tests/qemu-iotests/043.out            |  22 +-
>  tests/qemu-iotests/060.out            |  16 +-
>  tests/qemu-iotests/061.out            |  52 +-
>  tests/qemu-iotests/071.out            |   4 +-
>  tests/qemu-iotests/099.out            |   4 +-
>  tests/qemu-iotests/108.out            |  14 +-
>  tests/qemu-iotests/117.out            |   2 +-
>  tests/qemu-iotests/120.out            |   2 +-
>  tests/qemu-iotests/127.out            |  20 +-
>  tests/qemu-iotests/140.out            |   4 +-
>  tests/qemu-iotests/141.out            |  76 +--
>  tests/qemu-iotests/143.out            |   2 +-
>  tests/qemu-iotests/156.out            |  20 +-
>  tests/qemu-iotests/161.out            |  28 +-
>  tests/qemu-iotests/176.out            |  16 +-
>  tests/qemu-iotests/184.out            | 170 ++---
>  tests/qemu-iotests/186.out            |  82 +--
>  tests/qemu-iotests/190.out            |   4 +-
>  tests/qemu-iotests/191.out            | 868 +++++++++++++-------------
>  tests/qemu-iotests/195.out            |   4 +-
>  tests/qemu-iotests/229.out            |  14 +-
>  tests/qemu-iotests/244.out            |  12 +-
>  tests/qemu-iotests/249.out            |  18 +-
>  tests/qemu-iotests/tests/qsd-jobs.out |   8 +-
>  28 files changed, 776 insertions(+), 809 deletions(-)


> diff --git a/tests/qemu-iotests/061.out b/tests/qemu-iotests/061.out
> index 139fc68177..6a05d67378 100644
> --- a/tests/qemu-iotests/061.out
> +++ b/tests/qemu-iotests/061.out

>  === Testing version downgrade with external data file ===
> @@ -525,13 +525,13 @@ virtual size: 64 MiB (67108864 bytes)
>  cluster_size: 65536
>  Format specific information:
>      compat: 1.1
> -    compression type: COMPRESSION_TYPE
> -    lazy refcounts: false
> -    refcount bits: 16
>      data file: TEST_DIR/t.IMGFMT.data
>      data file raw: false
> -    corrupt: false
>      extended l2: false
> +    lazy refcounts: false
> +    corrupt: false
> +    refcount bits: 16
> +    compression type: COMPRESSION_TYPE
>  No errors were found on the image.

For this qemu-immg info output, I'd suggest that both the original
and new output orderings are undesirable.

Given it is human targetted, it would be better if this was emitted
in alphabetical order. This ought to be addressed in a separate
stanadlone patch though, since its unrelated to the QDict ordering,
just a pre-existing flaw.


With regards,
Daniel
-- 
|: https://berrange.com      -o-    https://www.flickr.com/photos/dberrange :|
|: https://libvirt.org         -o-            https://fstop138.berrange.com :|
|: https://entangle-photo.org    -o-    https://www.instagram.com/dberrange :|