Re: [Qemu-devel] [PATCH v8 04/17] qapi-introspect: Guarantee particular sorting

[Eric Blake]

On 10/30/2015 05:20 AM, Markus Armbruster wrote:
> For now, only high-level review.
> 
> The main cost of sorting is interface complexity: we need to specify
> which things are sorted, and what the sorting order is (see your TODO
> below).  Once we've done so, we can't go back.
> 
> There's also implementation complexity, but your patch shows it's low
> enough to be ignored.
> 
> Cost needs be justified by benefits.  Let's have a look at the benefits.
> 

> My qmp-introspect.c has 48 SchemaInfoEnum, ranging from one to 125
> members.  Histogram:
> 
>  #enums with this #members

>       1 27
>       1 43
>       1 125
> 
> Mean is less than eight.  Median is *three*.

Binary searches have more overhead on small lists; you don't get the
benefits of the better algorithm until you overcome the initial hit of
more expensive lookups (bsearch() has to use a callback function, which
is intrinsically slower than doing direct comparison; the speedups are
only present if the search set is large enough that you are able to skip
enough comparisons to overcome the higher cost of the extra
indirection).  So leaving enums unsorted is unlikely to slow clients
down (clients will have to do a linear search, but not the end of the
world since we have few large lists, and even among those, the size is
unlikely to grow much further).

> 
> Sorting these member arrays in the client won't have a noticeable
> performance impact.  Heck, I suspect even using linear search wouldn't!
> Therefore, we can't really claim client performance as a benefit.

So I'm inclined to agree with your conclusion.


>>                     Additionally, QMP clients need not know which
>> C value is associated with an enum name, so sorting is an
>> effective way to hide that non-ABI aspect of qapi.
> 
> Sorting indeed hides the implementation detail of how enumerations are
> encoded in the server.  However, I can't see what would tempt clients
> into relying on it.  I can see for type names, and that's why we hide
> them (commit 1a9a507).

You have a point - even if a client figures out what integer value an
enum name maps to, it doesn't really help, because the client never
sends the integer over the wire.

> 
> One more potential benefit: when the schema changes in a way that
> affects only order in introspection, sorting can hide the changes from
> clients.  Can't think of a practical use of it, though.

Because we send names, not numbers, over the wire, we can insert a new
enum member in slot 0.  Clients blindly doing strcmp(enum[0], "magic")
will get thrown off if "magic" moves to a different position - but this
is true whether or not we sort.  So the only working clients are those
that check every enum position, not just enum[0].  So I agree - broken
clients are broken whether or not we sort, and working clients don't
miss anything whether or not we sort.


> My qmp-introspect.c has 48 SchemaInfoObject, ranging from zero to 27
> members.  Histogram:
> 
>   #objs with this #members

>       1 15
>       1 16
>       1 27

Even less than the largest enum (and large structs are already unwieldy,
compared to making trees of substructs, so we're less likely to make
them too much bigger).

> Since we visit stuff in a defined order, qmp-introspect.c's order is
> stable.  The order just isn't particularly useful for clients, let alone
> specified.
> 
>> Document these conventions, so that clients will know what can
>> and cannot be relied on.
>>
>> Signed-off-by: Eric Blake <address@hidden>
>>
>> ---
>> TODO: should the documentation mention that the sorting is done
>> in the C locale?
> 
> I'd assume C locale because we're sorting plain ASCII strings.  But
> spelling it out can't hurt.
> 
>>                  Is there anything required to ensure that python
>> sorts sanely (ie. that the choice of locale while building
>> doesn't cause inadvertent sorting differences such as turning on
>> case-insensitivity)?
> 
> Good question.

And my biggest worry.

>> +++ b/docs/qapi-code-gen.txt
>> @@ -516,6 +516,13 @@ query-qmp-schema.  QGA currently doesn't support 
>> introspection.
>>
>>  query-qmp-schema returns a JSON array of SchemaInfo objects.  These
>>  objects together describe the wire ABI, as defined in the QAPI schema.
>> +There is no specified order to the SchemaInfo objects returned; a
>> +client must search for a particular name and meta-type throughout the
>> +entire array to learn more about that name.  For now, the name for
>> +each SchemaInfo is unique thanks to qapi naming conventions; however
>> +this may be changed in the future (such as allowing a command and an
>> +event with the same name), so it is important that the client check
>> +for the desired meta-type.
> 
> I feel separate name spaces aren't necessary and would be confusing, and
> I'd be prepared to cast "single entity name space" in stone now.

Sounds fair to me.

> This all boils down to whether the increase in interface specification
> complexity is justified by the benefits.  The cost is small, but I'm
> having a hard time seeing the benefits, to be honest.
> 
> Am I missing something?

No, I think you gave a fair review. I put this patch out there for
discussion and to see how hard it would be; but I'm not strongly tied to
it (if I have to pick only one patch out of 3/17 and 4/17, I'd rather
see 3/17 go in).  So now that we've looked at the benefits (or rather,
that they aren't very strong), I'm okay with the idea of making my v9
spin of this series use an alternative patch that _just_ documents the
"single entity name space" and the fact that clients cannot rely on any
ordering (we don't sort - we may be deterministic, but we make no
guarantees on what that order is, and we are free to change the order in
the future).

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature