git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Clemens Buchacher <drizzd@aon.at>
To: Jeff King <peff@peff.net>
Cc: Ævar Arnfjörð Bjarmason <avarab@gmail.com>, Jonathan Nieder <jrnieder@gmail.com>, git@vger.kernel.org, Junio C Hamano <gitster@pobox.com>, Thomas Rast <trast@student.ethz.ch>
Subject: Re: [PATCH 0/4] Speed up git tag --contains
Date: Wed, 6 Jul 2011 21:06:21 +0200
Message-ID: <20110706190621.GA3937@toss> (raw)
In-Reply-To: <20110706065452.GB927@sigill.intra.peff.net>

On Wed, Jul 06, 2011 at 02:54:52AM -0400, Jeff King wrote:
>
> From what we've seen, it seems like skewing into the past is more
> common. It seems to come from importing old commits and using their
> timestamps as the commit timestamps. It would be nice to find a more
> accurate set (I _think_ with future skew like the second example above,
> the patch below will not give wrong answers; it will just be overly
> pessimal and traverse more commits than it needs to).

Yes, and that was indeed my only concern. Since we cannot tell with
certainty if we have skew into the past or into the future, it's
not wrong to always assume skew into the past. It just does not
always produce the shortest run of skewed commits, as you said. And
if skews into the future are rare, then that should not be an
issue.

But considering the complexity behind the timestamp based approach,
which you have demonstrated in your analysis, the generation number
concept looks very attractive to me.

It even has potential for the push/pull transport protocol.
(Unreliable) commit timestamps are currently used while searching
for common commits. And there is still the problem of searching
down the wrong branch, which can be especially bad for repos with
multiple disjoint histories. For example, we shouldn't send any
HAVEs for commits with generation numbers greater than the
generation number of the wanted ref. Or smaller than half that (in
which case downloading the complete pack would probably be faster).

Thomas, IIRC you were working on this. Do you think this could
help?

Clemens

  reply index

Thread overview: 28+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2011-06-11 19:04 Ævar Arnfjörð Bjarmason
2011-06-11 19:04 ` [PATCH 1/4] tag: speed up --contains calculation Ævar Arnfjörð Bjarmason
2011-06-11 19:04 ` [PATCH 2/4] limit "contains" traversals based on commit timestamp Ævar Arnfjörð Bjarmason
2011-06-11 19:04 ` [PATCH 3/4] default core.clockskew variable to one day Ævar Arnfjörð Bjarmason
2011-06-11 19:04 ` [PATCH 4/4] Why is "git tag --contains" so slow? Ævar Arnfjörð Bjarmason
2011-07-06  6:40 ` [PATCH 0/4] Speed up git tag --contains Jeff King
2011-07-06  6:54   ` Jeff King
2011-07-06 19:06     ` Clemens Buchacher [this message]
2011-07-06  6:56   ` Jonathan Nieder
2011-07-06  7:03     ` Jeff King
2011-07-06 14:26       ` generation numbers (was: [PATCH 0/4] Speed up git tag --contains) Jakub Narebski
2011-07-06 15:01         ` Ted Ts'o
2011-07-06 18:12           ` Jeff King
2011-07-06 18:46             ` Jakub Narebski
2011-07-07 18:59               ` Jeff King
2011-07-07 19:34                 ` generation numbers Junio C Hamano
2011-07-07 20:31                   ` Jakub Narebski
2011-07-07 20:52                     ` A Large Angry SCM
2011-07-08  0:29                       ` Junio C Hamano
2011-07-08 22:57                   ` Jeff King
2011-07-06 23:22             ` Junio C Hamano
2011-07-07 19:08               ` Jeff King
2011-07-07 20:10                 ` Jakub Narebski
2018-01-12 18:56   ` [PATCH 0/4] Speed up git tag --contains csilvers
2018-03-03  5:15     ` Jeff King
2018-03-08 23:05       ` csilvers
2018-03-12 13:45       ` Derrick Stolee
2018-03-12 23:59         ` Jeff King

Reply instructions:

You may reply publically 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=20110706190621.GA3937@toss \
    --to=drizzd@aon.at \
    --cc=avarab@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=jrnieder@gmail.com \
    --cc=peff@peff.net \
    --cc=trast@student.ethz.ch \
    /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

git@vger.kernel.org mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/
       or Tor2web: https://www.tor2web.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox