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

[Daniel P . Berrangé]

On Wed, Jul 06, 2022 at 01:35:22PM +0200, Markus Armbruster wrote:
> Markus Armbruster <armbru@redhat.com> writes:
> 
> > 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.
> 
> Forgot to mention: see also
> 
>         Subject: Re: [PULL 14/15] qdev: Base object creation on QDict rather 
> than QemuOpts
>         Message-ID: <87wnctzdl9.fsf@pond.sub.org>
>         https://lists.nongnu.org/archive/html/qemu-devel/2022-07/msg00358.html

What alternative options do we have for addressing this scenario.

I can think of

  - Auto-create array elements, if seeing an element set before length.

    This is based on the theory that 'len-PROP' field is largely
    redundant. It is only needed if you want to create a sparse
    array, with empty elements /after/ the last one explicitly
    set, or if you want to get error reporting for an app setting
    element 3 after saying it wanted a 2 element list. IMHO the
    error reporting benefit is dubious, because the error scenario
    only exists because we made the app set this redundant 'len-PROP'
    attribute. Does anything actually need the 'sparse array'
    facility ?

  - Special case array properties

    Modify object_set_properties_from_qdict, so that it has a special
    case first iterating over any properties with 'len-' prefix in
    their name, then iterating over everything else.

    Assuming this 'len-' property is the only case where we genuinely
    have ordering dependancies between properties, this is quite a
    simple fix, and avoid imposes ordering requirements on either
    clients or QEMU in general.


  - Insertion order preserving QDict

    What you've done here, pushing the ordering problem off to be
    the caller's responsibility to get right. The caller could
    easily have the same problem though. For example, for CLI args
    these days, libvirt will populate a data structure based on
    QAPI, and then serialize that to CLI args. I don't know offhand
    if our code is insertion order preserving, or will hit this
    exact same problem. Luckily we don't support the 'rocker'
    object so havent hit this precise issue.


  - Any other options ?


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 :|