git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
To: Jeff King <peff@peff.net>
Cc: Jeff Hostetler <git@jeffhostetler.com>,
	Ben Peart <peartben@gmail.com>,
	git@vger.kernel.org, gitster@pobox.com,
	Jeff Hostetler <jeffhost@microsoft.com>
Subject: Re: [PATCH v4 0/4] Add --no-ahead-behind to status
Date: Tue, 9 Jan 2018 14:15:47 +0100 (STD)	[thread overview]
Message-ID: <nycvar.QRO.7.76.6.1801091407480.37@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz> (raw)
In-Reply-To: <20180109072044.GD32257@sigill.intra.peff.net>

Hi Peff,

On Tue, 9 Jan 2018, Jeff King wrote:

> On Mon, Jan 08, 2018 at 03:04:20PM -0500, Jeff Hostetler wrote:
> 
> > > I was thinking about something similar to the logic we use today
> > > about whether to start reporting progress on other long commands.
> > > That would mean you could still get the ahead/behind values if you
> > > aren't that far behind but would only get "different" if that
> > > calculation gets too expensive (which implies the actual value isn't
> > > going to be all that helpful anyway).
> > 
> > After a off-line conversation with the others I'm going to look into
> > a version that is limited to n commits rather than be completely on or
> > off.  I think if you are for example less than 100 a/b then those numbers
> > have value; if you are past n, then they have much less value.
> > 
> > I'd rather do it by a fixed limit than by time to ensure that output
> > is predictable on graph shape and not on system load.
> 
> I like this direction a lot. I had hoped we could say "100+ commits
> ahead",

How about "100+ commits apart" instead?

> but I don't think we can do so accurately without generation numbers.

Even with generation numbers, it is not possible to say whether two given
commits reflect diverging branches or have an ancestor-descendant
relationship (or in graph speak: whether they are comparable).

It could potentially make it possible to cut off the commit traversal, but
I do not even see how that would be possible.

The only thing you could say for sure is that two different commits with
the same generation number are for sure "uncomparable", i.e. reflect
diverging branches.

> E.g., the case I mentioned at the bottom of this mail:
> 
>   https://public-inbox.org/git/20171224143318.GC23648@sigill.intra.peff.net/
> 
> I haven't thought too hard on it, but I suspect with generation numbers
> you could bound it and at least say "100+ ahead" or "100+ behind".

If you have walked 100 commits and still have not found a merge base,
there is no telling whether one start point is the ancestor of the other.
All you can say is that there are more than 100 commits in the
"difference".

You would not even be able to say that the *shortest* path between those
two start points is longer than 100 commits, you can construct
pathological DAGs pretty easily.

Even if you had generation numbers, and one commit's generation number
was, say, 17, and the other one's was 17,171, you could not necessarily
assume that the 17 one is the ancestor of the 17,171 one, all you can say
that it is not possible the other way round.

> But I don't think you can approximate both ahead and behind together
> without finding the actual merge base.
> 
> But even still, finding small answers quickly and accurately and punting
> to "really far, I didn't bother to compute it" on the big ones would be
> an improvement over always punting.

Indeed. The longer I think about it, the more I like the "100+ commits
apart" idea.

Ciao,
Dscho

  reply	other threads:[~2018-01-09 13:16 UTC|newest]

Thread overview: 16+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-01-08 15:48 Jeff Hostetler
2018-01-08 15:48 ` [PATCH v4 1/4] stat_tracking_info: return +1 when branches not equal Jeff Hostetler
2018-01-08 15:48 ` [PATCH v4 2/4] status: add --[no-]ahead-behind to status and commit for V2 format Jeff Hostetler
2018-01-08 15:48 ` [PATCH v4 3/4] status: update short status to respect --no-ahead-behind Jeff Hostetler
2018-01-08 15:48 ` [PATCH v4 4/4] status: support --no-ahead-behind in long format Jeff Hostetler
2018-01-08 19:49 ` [PATCH v4 0/4] Add --no-ahead-behind to status Ben Peart
2018-01-08 20:04   ` Jeff Hostetler
2018-01-09  7:20     ` Jeff King
2018-01-09 13:15       ` Johannes Schindelin [this message]
2018-01-09 14:29         ` Derrick Stolee
2018-01-09 14:56           ` Jeff Hostetler
2018-01-09 16:48           ` Johannes Schindelin
2018-01-10  7:47           ` Jeff King
2018-01-10 20:22             ` Junio C Hamano
2018-01-11  9:39               ` Jeff King
2018-01-10  7:41         ` Jeff King

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=nycvar.QRO.7.76.6.1801091407480.37@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz \
    --to=johannes.schindelin@gmx.de \
    --cc=git@jeffhostetler.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=jeffhost@microsoft.com \
    --cc=peartben@gmail.com \
    --cc=peff@peff.net \
    --subject='Re: [PATCH v4 0/4] Add --no-ahead-behind to status' \
    /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

Code repositories for project(s) associated with this 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).