Re: [RFC/WIP PATCH 11/11] Document protocol version 2

From: Jeff King <peff@peff.net>
Date: Jun 4, 2015, 13:18 UTC
Message-ID: <20150604131852.GB12404@peff.net>
In-Reply-To: <CAGZ79kYD--dZ_V=_X_Eo31KYTKXt2njuf56XqRRdaTJeLhDjaQ@mail.gmail.com>

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:

Show 6 quoted lines

> 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