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

[Markus Armbruster]

Peter Maydell <peter.maydell@linaro.org> writes:

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

Correct.

I expect to find a few more in tests not run by "make check".

>                                                  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??).

Traversal order before the patch depends on the (fixed) size of the hash
table and the has function for (string) keys.  Both have remained
unchanged since the initial commit (2009), which is why we've gotten
away with relying on it in tests.

Traversal order after the patch depends on insertion order.  I think
this is already an improvement for the tests: now the expected output
depends on what the test does, not on how qdict.c does its job.

If we think this still isn't good enough, we can investigate how to get
test output where the keys are in alphabetical order.