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

[Peter Maydell]

On Tue, 5 Jul 2022 at 10:54, Markus Armbruster <armbru@redhat.com> 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/.

Seems to fix the 'rocker' device regression, at least in that
it no longer gives an error message on startup.

The amount of patching you had to do to expected-output files
in 'tests' suggests we have quite a lot of test cases that
are currently implicitly reliant on the hash table traversal
order, which is not guaranteed to remain stable. Regardless of
what we do with this patch it would probably be a good idea
for whatever is outputting the text these tests are comparing
against to be made to use a stable output order (alphabetical??).

-- PMM