On Mon, Jun 01, 2015 at 04:40:54PM -0700, Stefan Beller wrote:
> Thinking about this further, maybe it is a good idea to restrict the
> capabilities advertising to alphabetical order?
This seems like an unnecessary restriction. The main impetus seems to
be:
> So how does parse_capability scale w.r.t the number of capabilities?
> If parse_capability is just a linear search then it is O(n) and with n
> capabilities the client faces an O(n^2) computation which is bad. So
> if we were to require alphabetic capabilities, you could internally
> keep track and the whole operation is O(n). I just wonder if this is
> premature optimization or some thought we need to think of.
but that is an implementation problem, not a protocol problem. The
parsing side can easily use something better than O(n) lookups (e.g., a
binary search). I think we can live with O(n lg n) to parse the whole
list. A true in-order merge would be O(n), but the difference is
probably negligible here, because...
> Now if we assume the number of capabilities grows over time a lot
> (someone may "abuse" it for a cool feature, similar to the refs
> currently. Nobody thought about having so many refs in advance)
I think if it grows without bound, we are doing it wrong. We should
generally only be adding capabilities that require a single short tag in
the list (server supports "foo", client asks for "foo"). I'd find it
acceptable to add ones that repeat, as long as we are very sure that the
repetition is going to be small, or scales with the size of the config
(e.g., servers says "here is a mirror you can seed from; here is another
mirror you can seed from").
We should definitely _not_ add anything that scales with the repository
size. For instance, the "symref" field only shows the "HEAD" now. That's
OK, as it's constant size. We do not show _all_ symrefs right now
because of pkt-line length limitations. With v2, we could in theory
start doing so (one per pkt-line). But that does not make it a good
idea. The right way to implement that is:
1. the server says "I can tell you about symrefs"
2. client says "OK, I understand how to parse your symref data"
3. for each ref in the advertisement, tack on "\0symref=..." (or
whatever).
The capability portion of the conversation remains constant-sized, and
the O(# of refs) portion is part of the ref advertisement, which is
inherently of that magnitude.
-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html