Re: [Qemu-devel] [PATCH v10 12/30] qapi-introspect: Document lack of sorting

[Markus Armbruster]

Eric Blake <address@hidden> writes:

> qapi-code-gen.txt already claims that types, commands, and
> events share a common namespace; set this in stone by further
> documenting that our introspection output will never have
> collisions with the same name tied to more than one meta-type.
>
> Our largest QMP enum currently has 125 values, our largest
> object type has 27 members, and the mean for each is less than
> 10.  These sizes are small enough that the per-element overhead
> of O(log n) binary searching probably outweighs the speed
> possible with direct O(n) linear searching (a better algorithm
> with more overhead will only beat a leaner naive algorithm only
> as you scale to larger input sizes).
>
> Arguably, the overall SchemaInfo array could be sorted by name;
> there, we currently have 531 entities, large enough for a binary
> search to be faster than linear.  However, remember that we have
> mutually-recursive types, which means there is no topological
> ordering that will allow clients to learn all information about
> that type in a single linear pass; thus clients will want to do
> random access over the data, and they will probably read the
> introspection output into a hashtable for O(1) lookup rather
> than O(log n) binary searching, at which point, pre-sorting our
> introspection output doesn't help the client.
>
> It doesn't help that sorting can be subjective if you introduce
> locales into the mix (I'm not experienced enough with Python
> to know for sure, but at least it looks like it defaults to
> sorting in the C locale even when run under a different locale).
> And while our current introspection output is deterministic
> (because we visit entities in a sorted order), we may want
> to change that order in the future (such as using OrderedDict
> to stick to .json declaration order).
>
> For these reasons, we simply document that clients should not
> rely on any particular order of items in introspection output.
> And since it is now a documented part of the contract, we have
> the freedom to later rearrange output if needed, without
> worrying about breaking well-written clients that were already
> aware that they had to do linear searches.

Well, any kind of search that doesn't rely on sorting.  Suggest to drop
the "that were already..." clause.  Happy to do that on commit.