On Wed, Jul 06, 2022 at 01:35:22PM +0200, Markus Armbruster wrote:
> Markus Armbruster <arm...@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....@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 :|
