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

[Markus Armbruster <armbru@redhat.com>]

Alex Bennée <alex.bennee@linaro.org> writes:

> 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.
>
> Did you consider just using a straight array? What is the usual size of
> a QDict - how many entries do you expect to scale to?

I like the way you think :)

Let me hazard an educated guess.

QDict's intended purpose is "JSON AST for QMP".

Output and syntactically correct input satisfy the QAPI schema.  JSON
objects correspond to a complex type in the schema (struct or union).
The number of members in the schema limits the number of members in the
JSON object ("limits" because members can be optional).

BlockDeviceInfo has 32 members.  As far as I can tell, no type has more.

Exception 1: the 'any' type, currently used for QOM properties

Exception 2: the "'gen': false" schema backdoor, currenrly used for
             device_add arguments, so basically QOM properties again

I can't be bothered to go fishing for the QOM object with the most
properties.  Could exceed 32, but exceeding it by much would surprise
me.

For incorrect input, all bets are off.  We may hand-wave this away, but
only as long as input is trusted.

QDict is used for other purposes in places.  Can't say how many keys to
expect there.  Can say I wish it wasn't.

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