git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Jeff King <peff@peff.net>
To: Stefan Beller <sbeller@google.com>
Cc: Junio C Hamano <gitster@pobox.com>,
	"git@vger.kernel.org" <git@vger.kernel.org>,
	Duy Nguyen <pclouds@gmail.com>
Subject: Re: [RFC/WIP PATCH 11/11] Document protocol version 2
Date: Thu, 4 Jun 2015 09:18:52 -0400	[thread overview]
Message-ID: <20150604131852.GB12404@peff.net> (raw)
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:

> 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

  reply	other threads:[~2015-06-04 13:19 UTC|newest]

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-05-26 22:01 [RFC/WIP PATCH 00/11] Protocol version 2, again! Stefan Beller
2015-05-26 22:01 ` [RFC/WIP PATCH 01/11] upload-pack: make client capability parsing code a separate function Stefan Beller
2015-05-26 22:01 ` [RFC/WIP PATCH 02/11] upload-pack: only accept capabilities on the first "want" line Stefan Beller
2015-05-26 22:17   ` Junio C Hamano
2015-05-26 22:20     ` Stefan Beller
2015-05-26 22:01 ` [RFC/WIP PATCH 03/11] upload-pack: move capabilities out of send_ref Stefan Beller
2015-05-26 22:01 ` [RFC/WIP PATCH 04/11] upload-pack-2: Implement the version 2 of upload-pack Stefan Beller
2015-05-27  2:30   ` Eric Sunshine
2015-05-27  6:35   ` Jeff King
2015-05-27 17:30     ` Eric Sunshine
2015-05-27 20:14       ` Jeff King
2015-05-27 17:40     ` Stefan Beller
2015-05-27 20:34       ` Jeff King
2015-05-27 20:45         ` Stefan Beller
2015-05-27 21:46           ` Jeff King
2015-05-26 22:01 ` [RFC/WIP PATCH 05/11] transport: add infrastructure to support a protocol version number Stefan Beller
2015-05-27  6:39   ` Jeff King
2015-05-27 19:01     ` Stefan Beller
2015-05-27 20:17       ` Jeff King
2015-05-27 19:10     ` Junio C Hamano
2015-05-26 22:01 ` [RFC/WIP PATCH 06/11] remote.h: add get_remote_capabilities, request_capabilities Stefan Beller
2015-05-27  3:25   ` Eric Sunshine
2015-05-27  6:50     ` Jeff King
2015-05-27 17:19       ` Eric Sunshine
2015-05-27 20:09         ` Jeff King
2015-05-27  6:45   ` Jeff King
2015-05-29 19:39     ` Stefan Beller
2015-05-29 22:08       ` Jeff King
2015-05-26 22:01 ` [RFC/WIP PATCH 07/11] fetch-pack: use the configured transport protocol Stefan Beller
2015-05-26 22:19   ` Junio C Hamano
2015-05-26 22:23     ` Stefan Beller
2015-05-27  6:53   ` Jeff King
2015-05-26 22:01 ` [RFC/WIP PATCH 08/11] transport: connect_setup appends protocol version number Stefan Beller
2015-05-26 22:21   ` Junio C Hamano
2015-05-26 22:31     ` Stefan Beller
2015-05-27  5:09       ` Junio C Hamano
2015-05-27  6:56         ` Jeff King
2015-05-27  3:33   ` Eric Sunshine
2015-05-27  7:02   ` Jeff King
2015-05-26 22:01 ` [RFC/WIP PATCH 09/11] transport: get_refs_via_connect exchanges capabilities before refs Stefan Beller
2015-05-27  5:37   ` Eric Sunshine
2015-05-27  7:06   ` Jeff King
2015-05-26 22:01 ` [RFC/WIP PATCH 10/11] t5544: add a test case for the new protocol Stefan Beller
2015-05-27  5:34   ` Eric Sunshine
2015-05-27  7:12   ` Jeff King
2015-05-26 22:01 ` [RFC/WIP PATCH 11/11] Document protocol version 2 Stefan Beller
2015-05-29 20:35   ` Junio C Hamano
2015-05-29 21:36     ` Stefan Beller
2015-05-29 21:52       ` Junio C Hamano
2015-05-29 22:21         ` Jeff King
2015-06-01 23:14           ` Stefan Beller
2015-06-01 23:40             ` Stefan Beller
2015-06-04 13:18               ` Jeff King [this message]
2015-06-04 17:01                 ` Junio C Hamano
2015-06-02 17:06             ` Junio C Hamano
2015-05-27  6:18 ` [RFC/WIP PATCH 00/11] Protocol version 2, again! Jeff King
2015-05-27  7:08   ` Jeff King
2015-06-01 17:49     ` Stefan Beller
2015-06-02 10:10       ` Duy Nguyen
2015-06-04 13:09       ` Jeff King
2015-06-04 16:44         ` Stefan Beller

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20150604131852.GB12404@peff.net \
    --to=peff@peff.net \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=pclouds@gmail.com \
    --cc=sbeller@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).