From: Jeff King <peff@peff.net>
To: Junio C Hamano <gitster@pobox.com>
Cc: git@vger.kernel.org, "Jakub Narebski" <jnareb@gmail.com>,
"Ted Ts'o" <tytso@mit.edu>,
"Jonathan Nieder" <jrnieder@gmail.com>,
"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
"Clemens Buchacher" <drizzd@aon.at>,
"Shawn O. Pearce" <spearce@spearce.org>,
"Linus Torvalds" <torvalds@linux-foundation.org>
Subject: Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation
Date: Fri, 15 Jul 2011 17:14:41 -0400 [thread overview]
Message-ID: <20110715211441.GB1943@sigill.intra.peff.net> (raw)
In-Reply-To: <7vzkkfz261.fsf@alter.siamese.dyndns.org>
On Fri, Jul 15, 2011 at 02:04:06PM -0700, Junio C Hamano wrote:
> Jeff King <peff@peff.net> writes:
>
> >> So how about marking commits (using the metainfo-cache facility) that
> >> has an ancestor (not necessarily its direct parent) that records a
> >> younger timestamp (e.g. 1 is such a commit, as its ancestors include
> >> things like 2 and 4)? There should be relatively small number of them,
> >> and still_interesting() logic can be told to dig through such commits
> >> even if everybody is uninteresting in the active list.
> > ...
> >> * As to "tag --contains", when timestamp based heuristics breaks down is
> >> when a tagged commit incorrectly records way young timestamp or the
> >> "want" commit records way old timetsamp. I haven't thought things
> >> through, but the same metainfo-cache may be useful to detect which
> >> commit to dig through ignoring the cutoff heuristics.
> >
> > It can also break down if intermediate commits are wrong, because we
> > have to traverse backwards, and we may erroneously cutoff early.
> >
> > For example:
> >
> > A--B--C
> >
> > timestamp(A) = 2
> > timestamp(B) = 1 # skewed!
> > timestamp(C) = 3
> >
> > If tag=C and want=A, then we traverse backwards from C. We can't stop
> > immediately because we know that 2 < 3. But we go back to B, and see
> > that 2 > 1, and assume that A cannot possibly be an ancestor of B.
>
> I envisioned that the metainfo-cache to help rev-list I mentioned earlier
> would mark B having an ancestor A that has a timestamp younger than it, so
> I think we can certainly notice that we have to "dig through" B.
Right. I thought you were talking about the case where we did not have
such a cache. But given your response, did you mean:
If we have such a cache, then the only thing left to worry about is
when we specifically ask about a commit (either a tag or a "want"
commit) that is skewed.
That I agree with.
-Peff
next prev parent reply other threads:[~2011-07-15 21:14 UTC|newest]
Thread overview: 57+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-07-13 6:47 [RFC/PATCHv2 0/6] generation numbers for faster traversals Jeff King
2011-07-13 6:57 ` [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers Jeff King
2011-07-13 17:52 ` Jonathan Nieder
2011-07-13 20:08 ` Jeff King
2011-07-14 17:34 ` Jeff King
2011-07-14 17:51 ` [PATCH 1/3] implement generic key/value map Jeff King
2011-07-14 18:52 ` Bert Wesarg
2011-07-14 18:54 ` Bert Wesarg
2011-07-14 18:55 ` Jeff King
2011-07-14 19:07 ` Bert Wesarg
2011-07-14 19:14 ` Jeff King
2011-07-14 19:18 ` Bert Wesarg
2011-07-14 17:52 ` [PATCH 2/3] fast-export: use object to uint32 map instead of "decorate" Jeff King
2011-07-15 9:40 ` Sverre Rabbelier
2011-07-15 20:00 ` Jeff King
2011-07-14 17:53 ` [PATCH 3/3] decorate: use "map" for the underlying implementation Jeff King
2011-07-14 21:06 ` [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers Junio C Hamano
2011-08-04 22:43 ` [RFC/PATCH 0/5] macro-based key/value maps Jeff King
2011-08-04 22:45 ` [PATCH 1/5] implement generic key/value map Jeff King
2011-08-04 22:46 ` [PATCH 2/5] fast-export: use object to uint32 map instead of "decorate" Jeff King
2011-08-04 22:46 ` [PATCH 3/5] decorate: use "map" for the underlying implementation Jeff King
2011-08-04 22:46 ` [PATCH 4/5] map: implement persistent maps Jeff King
2011-08-04 22:46 ` [PATCH 5/5] implement metadata cache subsystem Jeff King
2011-08-04 22:48 ` [RFC/PATCH 0/2] patch-id caching Jeff King
2011-08-04 22:49 ` [PATCH 1/2] cherry: read default config Jeff King
2011-08-04 22:49 ` [PATCH 2/2] cache patch ids on disk Jeff King
2011-08-04 22:52 ` Jeff King
2011-08-05 11:03 ` [RFC/PATCH 0/5] macro-based key/value maps Jeff King
2011-08-05 15:31 ` René Scharfe
2011-08-06 6:30 ` Jeff King
2011-07-13 7:04 ` [RFC/PATCHv2 2/6] add metadata-cache infrastructure Jeff King
2011-07-13 8:18 ` Bert Wesarg
2011-07-13 8:31 ` Jeff King
2011-07-13 8:45 ` Bert Wesarg
2011-07-13 19:18 ` Jeff King
2011-07-13 19:40 ` Junio C Hamano
2011-07-13 19:33 ` Junio C Hamano
2011-07-13 20:25 ` Jeff King
2011-07-13 7:05 ` [RFC/PATCHv2 3/6] commit: add commit_generation function Jeff King
2011-07-13 14:26 ` Eric Sunshine
2011-07-13 7:05 ` [RFC/PATCHv2 4/6] pretty: support %G to show the generation number of a commit Jeff King
2011-07-13 7:06 ` [RFC/PATCHv2 5/6] check commit generation cache validity against grafts Jeff King
2011-07-13 14:26 ` Eric Sunshine
2011-07-13 19:35 ` Jeff King
2011-07-13 7:06 ` [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation Jeff King
2011-07-13 7:23 ` Jeff King
2011-07-13 20:33 ` Junio C Hamano
2011-07-13 20:58 ` Jeff King
2011-07-13 21:12 ` Junio C Hamano
2011-07-13 21:18 ` Jeff King
2011-07-15 18:22 ` Junio C Hamano
2011-07-15 20:40 ` Jeff King
2011-07-15 21:04 ` Junio C Hamano
2011-07-15 21:14 ` Jeff King [this message]
2011-07-15 21:01 ` Generation numbers and replacement objects Jakub Narebski
2011-07-15 21:10 ` Jeff King
2011-07-16 21:10 ` Jakub Narebski
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=20110715211441.GB1943@sigill.intra.peff.net \
--to=peff@peff.net \
--cc=avarab@gmail.com \
--cc=drizzd@aon.at \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=jnareb@gmail.com \
--cc=jrnieder@gmail.com \
--cc=spearce@spearce.org \
--cc=torvalds@linux-foundation.org \
--cc=tytso@mit.edu \
/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).