* [RFC/PATCH 1/4] tag: speed up --contains calculation
2010-07-05 12:27 ` Jeff King
@ 2010-07-05 12:33 ` Jeff King
2010-10-13 22:07 ` Jonathan Nieder
` (2 more replies)
2010-07-05 12:34 ` [RFC/PATCH 2/4] limit "contains" traversals based on commit timestamp Jeff King
` (4 subsequent siblings)
5 siblings, 3 replies; 46+ messages in thread
From: Jeff King @ 2010-07-05 12:33 UTC (permalink / raw)
To: tytso; +Cc: Avery Pennarun, git
When we want to know if commit A contains commit B (or any
one of a set of commits, B through Z), we generally
calculate the merge bases and see if B is a merge base of A
(or for a set, if any of the commits B through Z have that
property).
When we are going to check a series of commits A1 through An
to see whether each contains B (e.g., because we are
deciding which tags to show with "git tag --contains"), we
do a series of merge base calculations. This can be very
expensive, as we repeat a lot of traversal work.
Instead, let's leverage the fact that we are going to use
the same --contains list for each tag, and mark areas of the
commit graph is definitely containing those commits, or
definitely not containing those commits. Later tags can then
stop traversing as soon as they see a previously calculated
answer.
This sped up "git tag --contains HEAD~200" in the linux-2.6
repository from:
real 0m15.417s
user 0m15.197s
sys 0m0.220s
to:
real 0m5.329s
user 0m5.144s
sys 0m0.184s
Signed-off-by: Jeff King <peff@peff.net>
---
Note that this is a depth first search, whereas we generally traverse in
a more breadth-first way. So it can actually make things slightly slower
than the current merge-base code, if:
1. You don't have any merge base calculations that involve going very
far back in history.
2. We depth-first down the wrong side of a merge.
However, in the usual cases, I think it will perform much better.
Comparing an old tag with a recent commit means we have to look at a lot
of the commit graph, anyway.
If anybody has a clever idea for making it breadth-first, I would be
happy to hear it.
Other caveats:
1. This can probably be a one-liner change to use in "git branch
--contains", as well. I didn't measure it, as that already tends to
be reasonably fast.
2. It uses commit marks, which means it doesn't behave well with other
traversals. I have no idea if I should be using alternate marks or
not.
3. We never clear the marks, or check them against the "want" list. So
we just assume that repeated calls to contains will have the same
"want" list.
builtin/tag.c | 2 +-
commit.c | 42 ++++++++++++++++++++++++++++++++++++++++++
commit.h | 2 ++
3 files changed, 45 insertions(+), 1 deletions(-)
diff --git a/builtin/tag.c b/builtin/tag.c
index d311491..c200e1e 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -49,7 +49,7 @@ static int show_reference(const char *refname, const unsigned char *sha1,
commit = lookup_commit_reference_gently(sha1, 1);
if (!commit)
return 0;
- if (!is_descendant_of(commit, filter->with_commit))
+ if (!contains(commit, filter->with_commit))
return 0;
}
diff --git a/commit.c b/commit.c
index e9b0750..20354c6 100644
--- a/commit.c
+++ b/commit.c
@@ -845,3 +845,45 @@ int commit_tree(const char *msg, unsigned char *tree,
strbuf_release(&buffer);
return result;
}
+
+static int in_commit_list(const struct commit_list *want, struct commit *c)
+{
+ for (; want; want = want->next)
+ if (!hashcmp(want->item->object.sha1, c->object.sha1))
+ return 1;
+ return 0;
+}
+
+static int contains_recurse(struct commit *candidate,
+ const struct commit_list *want)
+{
+ struct commit_list *p;
+
+ /* was it previously marked as containing a want commit? */
+ if (candidate->object.flags & TMP_MARK)
+ return 1;
+ /* or marked as not possibly containing a want commit? */
+ if (candidate->object.flags & UNINTERESTING)
+ return 0;
+ /* or are we it? */
+ if (in_commit_list(want, candidate))
+ return 1;
+
+ if (parse_commit(candidate) < 0)
+ return 0;
+
+ /* Otherwise recurse and mark ourselves for future traversals. */
+ for (p = candidate->parents; p; p = p->next) {
+ if (contains_recurse(p->item, want)) {
+ candidate->object.flags |= TMP_MARK;
+ return 1;
+ }
+ }
+ candidate->object.flags |= UNINTERESTING;
+ return 0;
+}
+
+int contains(struct commit *candidate, const struct commit_list *want)
+{
+ return contains_recurse(candidate, want);
+}
diff --git a/commit.h b/commit.h
index eb2b8ac..1a7299e 100644
--- a/commit.h
+++ b/commit.h
@@ -153,6 +153,8 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,
int is_descendant_of(struct commit *, struct commit_list *);
int in_merge_bases(struct commit *, struct commit **, int);
+int contains(struct commit *, const struct commit_list *);
+
extern int interactive_add(int argc, const char **argv, const char *prefix);
extern int run_add_interactive(const char *revision, const char *patch_mode,
const char **pathspec);
--
1.7.2.rc1.209.g2a36c
^ permalink raw reply related [flat|nested] 46+ messages in thread* Re: [RFC/PATCH 1/4] tag: speed up --contains calculation
2010-07-05 12:33 ` [RFC/PATCH 1/4] tag: speed up --contains calculation Jeff King
@ 2010-10-13 22:07 ` Jonathan Nieder
2010-10-13 22:56 ` Clemens Buchacher
2011-02-23 15:51 ` Ævar Arnfjörð Bjarmason
2 siblings, 0 replies; 46+ messages in thread
From: Jonathan Nieder @ 2010-10-13 22:07 UTC (permalink / raw)
To: Jeff King; +Cc: tytso, Avery Pennarun, git, Junio C Hamano
Hi,
Jeff King wrote:
> When we want to know if commit A contains commit B (or any
> one of a set of commits, B through Z),
Let's revive this old thread. Sorry for the long silence (the last
time this topic was visited was a couple months ago [1] afaict).
> Instead, let's leverage the fact that we are going to use
> the same --contains list for each tag, and mark areas of the
> commit graph is definitely containing those commits, or
> definitely not containing those commits. Later tags can then
> stop traversing as soon as they see a previously calculated
> answer.
Makes sense. And the resulting timings are exciting.
> ---
> Note that this is a depth first search, whereas we generally traverse in
> a more breadth-first way. So it can actually make things slightly slower
> than the current merge-base code, if:
>
> 1. You don't have any merge base calculations that involve going very
> far back in history.
>
> 2. We depth-first down the wrong side of a merge.
>
> However, in the usual cases, I think it will perform much better.
Nit: Wouldn't this (or a summary of it) belong in the log message, too,
to avoid headscratching when a person tries to bisect a performance
regression down the line?
> 1. This can probably be a one-liner change to use in "git branch
> --contains", as well. I didn't measure it, as that already tends to
> be reasonably fast.
These days "branch -r --contains" has been _sloow_ for me. So once
this is tuned, that wouldn't be a bad idea, methinks.
> 2. It uses commit marks, which means it doesn't behave well with other
> traversals. I have no idea if I should be using alternate marks or
> not.
This is what Junio was referring to with "the use of TMP_MARK smelled
somewhat bad to me", right?
> 3. We never clear the marks, or check them against the "want" list.
This too, I suppose.
> So
> we just assume that repeated calls to contains will have the same
> "want" list.
As long as this is advertised, I think it is fine. If someone needs
to use --contains for multiple purposes in a builtin, that can be
dealt with then (maybe with a separate function to reset the marks).
Maybe it would make sense to keep this static in builtin/tag.c for
now, and defer cleaning up the interface to a separate patch.
> --- a/commit.c
> +++ b/commit.c
Now the meat of the patch. git has a few algorithms for checking if
one commit is an ancestor of another.
is_descendant_of::
1. find merge bases. This is breadth-first search in
date order, but it walks through all ancestors as far
as I can tell.
2. make them independent (seems pointless...).
3. check if ancestor is one of them.
get_revision after setting UNINTERESTING (i.e., rev-list -1 ^tag cmit)::
1. find interesting and uninteresting commits. This is
breadth-first search in date order.
2. when the first interesting commit is found, emit it
and stop.
Neither is optimized to check a batch of commits to find which contain
the commit of interest.
join_revs of show-branch::
1. color the tag and cmit.
2. let colors propagate back to all their ancestors, stopping
propagation along a given path when a commit has all colors.
This is breadth-first traversal in date order.
3. for each commit with all colors, propagate that knowledge
to all parents we've encountered before.
4. check what colors cmit has.
limit_to_ancestry::
1. compute rev-list ^cmit tag in the usual way.
2. reverse the revision list.
3. color cmit with TMP_MARK and let that color permeate
up the backwards revision list.
4. repeat! until no progress is made.
4. check what color tag has.
None of these seem to tolerate timestamp skew. :(
Am I understanding correctly?
If so, just making is_descendant_of less stupid (e.g., not traversing
all history) would presumably help a lot. Another approach would be
to try the show-branch tactic repeatedly with small enough batches of
tags to fit in the flag bitfield. Yet another approach would be to
take the limit_to_ancestry one, but if the revision list is not
topologically sorted, it could be slow.
Hopefully your approach will be even better...
> @@ -845,3 +845,45 @@ int commit_tree(const char *msg, unsigned char *tree,
[...]
> +static int contains_recurse(struct commit *candidate,
> + const struct commit_list *want)
> +{
> + struct commit_list *p;
> +
> + /* was it previously marked as containing a want commit? */
> + if (candidate->object.flags & TMP_MARK)
> + return 1;
> + /* or marked as not possibly containing a want commit? */
> + if (candidate->object.flags & UNINTERESTING)
> + return 0;
> + /* or are we it? */
> + if (in_commit_list(want, candidate))
> + return 1;
> +
> + if (parse_commit(candidate) < 0)
> + return 0;
> +
> + /* Otherwise recurse and mark ourselves for future traversals. */
> + for (p = candidate->parents; p; p = p->next) {
> + if (contains_recurse(p->item, want)) {
> + candidate->object.flags |= TMP_MARK;
> + return 1;
> + }
> + }
> + candidate->object.flags |= UNINTERESTING;
Nice. We cache the "is wanted" result using TMP_MARK and
UNINTERESTING. It cannot be slower than is_descendant_of if I
understood correctly because the latter is a little crazy.
Possible unprincipled approach:
1. Mark the wanted commits with TMP_MARK.
2. Perform a breadth-first, date-order search starting at
candidate to find a commit with TMP_MARK.
a. If not found, mark the commits involved as UNINTERESTING
b. If found, let the TMP_MARK permeate up using the
limit_to_ancestry algorithm.
3. Repeat with each other candidate.
4. (If needed) walk starting at each candidate to clear the
temporary flags.
I am not sure if that would be any faster, though. What do you think?
[...]
> +int contains(struct commit *, const struct commit_list *);
Thanks for a pleasant read.
[1] http://thread.gmane.org/gmane.comp.version-control.git/152607/focus=152701
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: [RFC/PATCH 1/4] tag: speed up --contains calculation
2010-07-05 12:33 ` [RFC/PATCH 1/4] tag: speed up --contains calculation Jeff King
2010-10-13 22:07 ` Jonathan Nieder
@ 2010-10-13 22:56 ` Clemens Buchacher
2011-02-23 15:51 ` Ævar Arnfjörð Bjarmason
2 siblings, 0 replies; 46+ messages in thread
From: Clemens Buchacher @ 2010-10-13 22:56 UTC (permalink / raw)
To: Jeff King; +Cc: tytso, Avery Pennarun, git
[-- Attachment #1: Type: text/plain, Size: 591 bytes --]
On Mon, Jul 05, 2010 at 08:33:36AM -0400, Jeff King wrote:
>
> This sped up "git tag --contains HEAD~200" in the linux-2.6
> repository from:
>
> real 0m15.417s
> user 0m15.197s
> sys 0m0.220s
FWIW, in the staging tree they have a new tag for almost every day.
My linux repo currently has 677 tags. This same command would
probably take hours. I have not had the patience yet to let it
finish.
With your patch I get this.
$ time git tag --contains HEAD~200
v2.6.36-rc3
v2.6.36-rc4
v2.6.36-rc5
real 0m8.047s
user 0m7.755s
sys 0m0.268s
Clemens
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: [RFC/PATCH 1/4] tag: speed up --contains calculation
2010-07-05 12:33 ` [RFC/PATCH 1/4] tag: speed up --contains calculation Jeff King
2010-10-13 22:07 ` Jonathan Nieder
2010-10-13 22:56 ` Clemens Buchacher
@ 2011-02-23 15:51 ` Ævar Arnfjörð Bjarmason
2011-02-23 16:39 ` Jeff King
2 siblings, 1 reply; 46+ messages in thread
From: Ævar Arnfjörð Bjarmason @ 2011-02-23 15:51 UTC (permalink / raw)
To: Jeff King; +Cc: tytso, Avery Pennarun, git, Junio C Hamano
On Mon, Jul 5, 2010 at 14:33, Jeff King <peff@peff.net> wrote:
> When we want to know if commit A contains commit B (or any
> one of a set of commits, B through Z), we generally
> calculate the merge bases and see if B is a merge base of A
> (or for a set, if any of the commits B through Z have that
> property).
On a work repo with around 10k tags after and before this patch:
$ time ~/g/git/git tag --contains HEAD~200 | wc -l
113
real 0m0.421s
user 0m0.380s
sys 0m0.042s
$ time git tag --contains HEAD~200 | wc -l
113
real 2m18.861s
user 2m18.750s
sys 0m0.092s
I'd love to have this merged downwards from pu. It's the single
biggest usability improvement in my Git workflow for as long as I can
remember.
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: [RFC/PATCH 1/4] tag: speed up --contains calculation
2011-02-23 15:51 ` Ævar Arnfjörð Bjarmason
@ 2011-02-23 16:39 ` Jeff King
0 siblings, 0 replies; 46+ messages in thread
From: Jeff King @ 2011-02-23 16:39 UTC (permalink / raw)
To: Ævar Arnfjörð Bjarmason
Cc: tytso, Avery Pennarun, git, Junio C Hamano
On Wed, Feb 23, 2011 at 04:51:02PM +0100, Ævar Arnfjörð Bjarmason wrote:
> On Mon, Jul 5, 2010 at 14:33, Jeff King <peff@peff.net> wrote:
> > When we want to know if commit A contains commit B (or any
> > one of a set of commits, B through Z), we generally
> > calculate the merge bases and see if B is a merge base of A
> > (or for a set, if any of the commits B through Z have that
> > property).
>
> On a work repo with around 10k tags after and before this patch:
> [...much speed improvement...]
> I'd love to have this merged downwards from pu. It's the single
> biggest usability improvement in my Git workflow for as long as I can
> remember.
Yeah, I have been meaning to revisit the topic. I got sidetracked by
looking at clock skew issues, and there was some debate over whether the
strict depth-first traversal was the best way to do it (although if you
trust the commit timestamps, I think you stop going down dead-ends
pretty quickly in practice; and I think we do implicitly trust the
commit timestamps in the regular merge base traversals). If we can do a
multi-headed merge base, that would be better, but I'll have to think on
it.
I'll try to take a look this week and see what I can come up with.
-Peff
^ permalink raw reply [flat|nested] 46+ messages in thread
* [RFC/PATCH 2/4] limit "contains" traversals based on commit timestamp
2010-07-05 12:27 ` Jeff King
2010-07-05 12:33 ` [RFC/PATCH 1/4] tag: speed up --contains calculation Jeff King
@ 2010-07-05 12:34 ` Jeff King
2010-10-13 23:21 ` Jonathan Nieder
2010-07-05 12:35 ` [RFC/PATCH 3/4] default core.clockskew variable to one day Jeff King
` (3 subsequent siblings)
5 siblings, 1 reply; 46+ messages in thread
From: Jeff King @ 2010-07-05 12:34 UTC (permalink / raw)
To: tytso; +Cc: Avery Pennarun, git
When looking for commits that contain other commits (e.g.,
via "git tag --contains"), we can end up traversing useless
portions of the graph. For example, if I am looking for a
tag that contains a commit made last week, there is not much
point in traversing portions of the history graph made five
years ago.
This optimization can provide massive speedups. For example,
doing "git tag --contains HEAD~200" in the linux-2.6
repository goes from:
real 0m5.302s
user 0m5.116s
sys 0m0.184s
to:
real 0m0.030s
user 0m0.020s
sys 0m0.008s
The downside is that we will no longer find some answers in
the face of extreme clock skew, as we will stop the
traversal early when seeing commits skewed too far into the
past.
Name-rev already implements a similar optimization, using a
"slop" of one day to allow for a certain amount of clock
skew in commit timestamps. This patch introduces a
"core.clockskew" variable, which allows specifying the
allowable amount of clock skew in seconds. For safety, it
defaults to "none", causing a full traversal (i.e., no
change in behavior from previous versions).
Signed-off-by: Jeff King <peff@peff.net>
---
cache.h | 1 +
commit.c | 27 ++++++++++++++++++++++++---
config.c | 8 ++++++++
3 files changed, 33 insertions(+), 3 deletions(-)
diff --git a/cache.h b/cache.h
index c9fa3df..2dfb636 100644
--- a/cache.h
+++ b/cache.h
@@ -551,6 +551,7 @@ extern int read_replace_refs;
extern int fsync_object_files;
extern int core_preload_index;
extern int core_apply_sparse_checkout;
+extern int core_clock_skew;
enum safe_crlf {
SAFE_CRLF_FALSE = 0,
diff --git a/commit.c b/commit.c
index 20354c6..c849b50 100644
--- a/commit.c
+++ b/commit.c
@@ -7,6 +7,7 @@
#include "revision.h"
#include "notes.h"
+int core_clock_skew = -1;
int save_commit_buffer = 1;
const char *commit_type = "commit";
@@ -855,7 +856,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
}
static int contains_recurse(struct commit *candidate,
- const struct commit_list *want)
+ const struct commit_list *want,
+ unsigned long cutoff)
{
struct commit_list *p;
@@ -872,9 +874,13 @@ static int contains_recurse(struct commit *candidate,
if (parse_commit(candidate) < 0)
return 0;
+ /* stop searching if we go too far back in time */
+ if (candidate->date < cutoff)
+ return 0;
+
/* Otherwise recurse and mark ourselves for future traversals. */
for (p = candidate->parents; p; p = p->next) {
- if (contains_recurse(p->item, want)) {
+ if (contains_recurse(p->item, want, cutoff)) {
candidate->object.flags |= TMP_MARK;
return 1;
}
@@ -885,5 +891,20 @@ static int contains_recurse(struct commit *candidate,
int contains(struct commit *candidate, const struct commit_list *want)
{
- return contains_recurse(candidate, want);
+ unsigned long cutoff = 0;
+
+ if (core_clock_skew >= 0) {
+ const struct commit_list *c;
+ unsigned long min_date = ULONG_MAX;
+ for (c = want; c; c = c->next) {
+ if (parse_commit(c->item) < 0)
+ continue;
+ if (c->item->date < min_date)
+ min_date = c->item->date;
+ }
+ if (min_date > core_clock_skew)
+ cutoff = min_date - core_clock_skew;
+ }
+
+ return contains_recurse(candidate, want, cutoff);
}
diff --git a/config.c b/config.c
index cdcf583..7a18bc9 100644
--- a/config.c
+++ b/config.c
@@ -595,6 +595,14 @@ static int git_default_core_config(const char *var, const char *value)
return 0;
}
+ if (!strcmp(var, "core.clockskew")) {
+ if (!value || !strcmp(value, "none"))
+ core_clock_skew = -1;
+ else
+ core_clock_skew = git_config_int(var, value);
+ return 0;
+ }
+
/* Add other config variables here and to Documentation/config.txt. */
return 0;
}
--
1.7.2.rc1.209.g2a36c
^ permalink raw reply related [flat|nested] 46+ messages in thread* Re: [RFC/PATCH 2/4] limit "contains" traversals based on commit timestamp
2010-07-05 12:34 ` [RFC/PATCH 2/4] limit "contains" traversals based on commit timestamp Jeff King
@ 2010-10-13 23:21 ` Jonathan Nieder
0 siblings, 0 replies; 46+ messages in thread
From: Jonathan Nieder @ 2010-10-13 23:21 UTC (permalink / raw)
To: Jeff King; +Cc: tytso, Avery Pennarun, git, Junio C Hamano
Jeff King wrote:
> Name-rev already implements a similar optimization, using a
> "slop" of one day to allow for a certain amount of clock
> skew in commit timestamps. This patch introduces a
> "core.clockskew" variable, which allows specifying the
> allowable amount of clock skew in seconds. For safety, it
> defaults to "none", causing a full traversal (i.e., no
> change in behavior from previous versions).
Tests?
Actually just a short example script to try would be helpful,
if anyone has one handy (yes, I am terribly lazy). Such a script
would be useful for figuring out which commands ought to be
updated to respect core_clock_skew. rev-list is one.
> --- a/commit.c
> +++ b/commit.c
[...]
> @@ -872,9 +874,13 @@ static int contains_recurse(struct commit *candidate,
> if (parse_commit(candidate) < 0)
> return 0;
>
> + /* stop searching if we go too far back in time */
> + if (candidate->date < cutoff)
> + return 0;
> +
Nice idea.
> @@ -885,5 +891,20 @@ static int contains_recurse(struct commit *candidate,
>
> int contains(struct commit *candidate, const struct commit_list *want)
> {
> - return contains_recurse(candidate, want);
> + unsigned long cutoff = 0;
> +
> + if (core_clock_skew >= 0) {
> + const struct commit_list *c;
> + unsigned long min_date = ULONG_MAX;
> + for (c = want; c; c = c->next) {
> + if (parse_commit(c->item) < 0)
> + continue;
Why ignore these errors? Will they be noticed later?
The rest of the patch looks good to me. I am not thrilled with
making the user figure out an acceptable "[core] clockskew" value
(and am not sure it makes much sense as a tunable setting), but
it is better than the status quo, so...
^ permalink raw reply [flat|nested] 46+ messages in thread
* [RFC/PATCH 3/4] default core.clockskew variable to one day
2010-07-05 12:27 ` Jeff King
2010-07-05 12:33 ` [RFC/PATCH 1/4] tag: speed up --contains calculation Jeff King
2010-07-05 12:34 ` [RFC/PATCH 2/4] limit "contains" traversals based on commit timestamp Jeff King
@ 2010-07-05 12:35 ` Jeff King
2010-07-05 12:36 ` [RFC/PATCH 4/4] name-rev: respect core.clockskew Jeff King
` (2 subsequent siblings)
5 siblings, 0 replies; 46+ messages in thread
From: Jeff King @ 2010-07-05 12:35 UTC (permalink / raw)
To: tytso; +Cc: Avery Pennarun, git
This is the slop value used by name-rev, so presumably is a
reasonable default.
Signed-off-by: Jeff King <peff@peff.net>
---
Actually, I think auto-detecting the skew in a repo during "gc" might be
an even better default. See:
http://article.gmane.org/gmane.comp.version-control.git/150260
earlier in this thread for some numbers and discussion.
commit.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/commit.c b/commit.c
index c849b50..4cbe756 100644
--- a/commit.c
+++ b/commit.c
@@ -7,7 +7,7 @@
#include "revision.h"
#include "notes.h"
-int core_clock_skew = -1;
+int core_clock_skew = 86400;
int save_commit_buffer = 1;
const char *commit_type = "commit";
--
1.7.2.rc1.209.g2a36c
^ permalink raw reply related [flat|nested] 46+ messages in thread* [RFC/PATCH 4/4] name-rev: respect core.clockskew
2010-07-05 12:27 ` Jeff King
` (2 preceding siblings ...)
2010-07-05 12:35 ` [RFC/PATCH 3/4] default core.clockskew variable to one day Jeff King
@ 2010-07-05 12:36 ` Jeff King
2010-07-05 12:39 ` Why is "git tag --contains" so slow? Jeff King
2010-07-05 14:10 ` tytso
5 siblings, 0 replies; 46+ messages in thread
From: Jeff King @ 2010-07-05 12:36 UTC (permalink / raw)
To: tytso; +Cc: Avery Pennarun, git
Before core.clockskew existed, we were just hard-coded to
86400 seconds. This allows users to tweak the value as
appropriate.
Signed-off-by: Jeff King <peff@peff.net>
---
I think it makes sense to adapt this to core.clockskew. Especially if
our default stays at 86400, then there is no change in behavior. But
even if it does change, I think having it tweakable (and especially if
we automatically calculate per-repo skew) makes sense.
builtin/name-rev.c | 8 ++++----
1 files changed, 4 insertions(+), 4 deletions(-)
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 06a38ac..5c6d712 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -5,8 +5,6 @@
#include "refs.h"
#include "parse-options.h"
-#define CUTOFF_DATE_SLOP 86400 /* one day */
-
typedef struct rev_name {
const char *tip_name;
int generation;
@@ -270,8 +268,10 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
add_object_array((struct object *)commit, *argv, &revs);
}
- if (cutoff)
- cutoff = cutoff - CUTOFF_DATE_SLOP;
+ if (cutoff && core_clock_skew >= 0)
+ cutoff = cutoff - core_clock_skew;
+ else
+ cutoff = 0;
for_each_ref(name_ref, &data);
if (transform_stdin) {
--
1.7.2.rc1.209.g2a36c
^ permalink raw reply related [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-07-05 12:27 ` Jeff King
` (3 preceding siblings ...)
2010-07-05 12:36 ` [RFC/PATCH 4/4] name-rev: respect core.clockskew Jeff King
@ 2010-07-05 12:39 ` Jeff King
2010-10-14 18:59 ` Jonathan Nieder
2010-07-05 14:10 ` tytso
5 siblings, 1 reply; 46+ messages in thread
From: Jeff King @ 2010-07-05 12:39 UTC (permalink / raw)
To: tytso; +Cc: Avery Pennarun, git
On Mon, Jul 05, 2010 at 08:27:23AM -0400, Jeff King wrote:
> As you probably guessed from the specificity of the number, I wrote a
> short program to actually traverse and find the worst skew. It takes
> about 5 seconds to run (unsurprisingly, since it is doing the same full
> traversal that we end up doing in the above numbers). So we could
> "autoskew" by setting up the configuration on clone, and then
> periodically updating it as part of "git gc".
This patch doesn't implement auto-detection of skew, but is the program
I used to calculate, and would provide the basis for such
auto-detection. It would be interesting to see average skew numbers for
popular repositories. You can run it as "git skew --all".
diff --git a/.gitignore b/.gitignore
index 14e2b6b..90aff17 100644
--- a/.gitignore
+++ b/.gitignore
@@ -132,6 +132,7 @@
/git-show-branch
/git-show-index
/git-show-ref
+/git-skew
/git-stage
/git-stash
/git-status
diff --git a/Makefile b/Makefile
index 9aca8a1..e673bdf 100644
--- a/Makefile
+++ b/Makefile
@@ -725,6 +725,7 @@ BUILTIN_OBJS += builtin/send-pack.o
BUILTIN_OBJS += builtin/shortlog.o
BUILTIN_OBJS += builtin/show-branch.o
BUILTIN_OBJS += builtin/show-ref.o
+BUILTIN_OBJS += builtin/skew.o
BUILTIN_OBJS += builtin/stripspace.o
BUILTIN_OBJS += builtin/symbolic-ref.o
BUILTIN_OBJS += builtin/tag.o
diff --git a/builtin.h b/builtin.h
index ed6ee26..5f5dc0a 100644
--- a/builtin.h
+++ b/builtin.h
@@ -141,5 +141,6 @@ extern int cmd_verify_pack(int argc, const char **argv, const char *prefix);
extern int cmd_show_ref(int argc, const char **argv, const char *prefix);
extern int cmd_pack_refs(int argc, const char **argv, const char *prefix);
extern int cmd_replace(int argc, const char **argv, const char *prefix);
+extern int cmd_skew(int argc, const char **argv, const char *prefix);
#endif
diff --git a/builtin/skew.c b/builtin/skew.c
new file mode 100644
index 0000000..1046f5f
--- /dev/null
+++ b/builtin/skew.c
@@ -0,0 +1,50 @@
+#include "cache.h"
+#include "commit.h"
+#include "diff.h"
+#include "revision.h"
+
+unsigned long worst_skew = 0;
+
+static void check_skew_recurse(struct commit *c, unsigned long when)
+{
+ struct commit_list *p;
+
+ if (c->object.flags & SEEN)
+ return;
+ c->object.flags |= SEEN;
+
+ if (parse_commit(c) < 0)
+ return;
+
+ if (c->date > when) {
+ unsigned long skew = c->date - when;
+ if (skew > worst_skew)
+ worst_skew = skew;
+ }
+
+ for (p = c->parents; p; p = p->next)
+ check_skew_recurse(p->item, c->date < when ? c->date : when);
+}
+
+static void check_skew(struct commit *c)
+{
+ check_skew_recurse(c, time(NULL));
+}
+
+int cmd_skew(int argc, const char **argv, const char *prefix) {
+ struct rev_info revs;
+ int i;
+
+ git_config(git_default_config, NULL);
+ init_revisions(&revs, prefix);
+ argc = setup_revisions(argc, argv, &revs, NULL);
+
+ for (i = 0; i < revs.pending.nr; i++) {
+ struct object *o = revs.pending.objects[i].item;
+ if (o->type == OBJ_COMMIT)
+ check_skew((struct commit *)o);
+ }
+
+ printf("%lu\n", worst_skew);
+ return 0;
+}
diff --git a/git.c b/git.c
index 265fa09..8a77fe3 100644
--- a/git.c
+++ b/git.c
@@ -399,6 +399,7 @@ static void handle_internal_command(int argc, const char **argv)
{ "verify-pack", cmd_verify_pack },
{ "show-ref", cmd_show_ref, RUN_SETUP },
{ "pack-refs", cmd_pack_refs, RUN_SETUP },
+ { "skew", cmd_skew, RUN_SETUP },
};
int i;
static const char ext[] = STRIP_EXTENSION;
^ permalink raw reply related [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-07-05 12:39 ` Why is "git tag --contains" so slow? Jeff King
@ 2010-10-14 18:59 ` Jonathan Nieder
2010-10-16 14:32 ` Clemens Buchacher
0 siblings, 1 reply; 46+ messages in thread
From: Jonathan Nieder @ 2010-10-14 18:59 UTC (permalink / raw)
To: Jeff King; +Cc: tytso, Avery Pennarun, git
Jeff King wrote:
> This patch doesn't implement auto-detection of skew, but is the program
> I used to calculate, and would provide the basis for such
> auto-detection. It would be interesting to see average skew numbers for
> popular repositories. You can run it as "git skew --all".
Fun. The story this tells me is that most repositories would benefit
more from special-casing a few commits than from a "[core] clockskew"
setting.
Caveat: the repos mentioned below are not canonical at all. They are
just some repos I happened to have around, some tracking multiple upstreams.
project # skewed maximum skew notes
------- -------- ------------ -----
gtk+ 13 13 hrs worst example seems to be tz related
systemd 3 1 hr all three come from a single 65min
jump. Same committer before+after.
dpkg 2 76 days automatic import from manually
written changelog
glibc 2 31 months (tag) commits imported to wrong
branches by "git cvsimport", I think
git 4 7 minutes all four come from a single merge
commit, parents have same committer
as the merge. probably clock drift
corrected with something like ntp.
guilt 22 96 minutes from the known (fixed) bug, I assume
linux-2.6 1226 99 days probably the old guilt bug (e.g., in
ext4, blackfin trees)
sed 0
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-10-14 18:59 ` Jonathan Nieder
@ 2010-10-16 14:32 ` Clemens Buchacher
2010-10-27 17:11 ` Jeff King
0 siblings, 1 reply; 46+ messages in thread
From: Clemens Buchacher @ 2010-10-16 14:32 UTC (permalink / raw)
To: Jonathan Nieder; +Cc: Jeff King, tytso, Avery Pennarun, git
[-- Attachment #1: Type: text/plain, Size: 681 bytes --]
On Thu, Oct 14, 2010 at 01:59:45PM -0500, Jonathan Nieder wrote:
>
> project # skewed maximum skew notes
> ------- -------- ------------ -----
> gtk+ 13 13 hrs worst example seems to be tz related
It really is kind of fun.
wine 1 14 days
mesa 4930 150 days
xf86-video-ati 13 ~2.5 hrs
xf86-video-intel 26 8 hrs
xf86-video-nouveau 12 10 hrs
fluxbox 0 0
metacity 0 0
openbox 8 4 hrs
giggle 2 21 min
glibc 2 931 days
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-10-16 14:32 ` Clemens Buchacher
@ 2010-10-27 17:11 ` Jeff King
2010-10-28 8:07 ` Clemens Buchacher
0 siblings, 1 reply; 46+ messages in thread
From: Jeff King @ 2010-10-27 17:11 UTC (permalink / raw)
To: Clemens Buchacher; +Cc: Jonathan Nieder, tytso, Avery Pennarun, git
On Sat, Oct 16, 2010 at 04:32:26PM +0200, Clemens Buchacher wrote:
> On Thu, Oct 14, 2010 at 01:59:45PM -0500, Jonathan Nieder wrote:
> >
> > project # skewed maximum skew notes
> > ------- -------- ------------ -----
> > gtk+ 13 13 hrs worst example seems to be tz related
>
> It really is kind of fun.
>
> wine 1 14 days
Thanks both of you for the extra data points. If you don't mind, would
you consider running my updated git-skew below on your test cases (or
tweaking your skew detectors, since you both seem to be getting a '#
skewed' column that mine didn't output). Specifically, I am interested
in long runs of skewed commits, since one potential solution would be to
just accept a fixed number of slop commits (rather than accepting
commits within a certain slop time).
For the kernel the longest run looks to be about 80 commits. This should
yield much better performance than handling the worst skew by time
(which was 100 days, during which many more than 80 commits are usually
used).
Patch below. NB: thinking on this more, I think my program's results are
slightly inaccurate. There are corner skew cases we can miss by the use
of marking commits SEEN (i.e., skew you would see if you got to a commit
by another path). However, the problem gets intractably large if you
don't mark commits (you end up traversing every possible path through
the graph).
---
.gitignore | 1 +
Makefile | 1 +
builtin.h | 1 +
builtin/skew.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
git.c | 1 +
5 files changed, 66 insertions(+), 0 deletions(-)
create mode 100644 builtin/skew.c
diff --git a/.gitignore b/.gitignore
index 20560b8..d696c78 100644
--- a/.gitignore
+++ b/.gitignore
@@ -132,6 +132,7 @@
/git-show-branch
/git-show-index
/git-show-ref
+/git-skew
/git-stage
/git-stash
/git-status
diff --git a/Makefile b/Makefile
index 1f1ce04..25f94b0 100644
--- a/Makefile
+++ b/Makefile
@@ -739,6 +739,7 @@ BUILTIN_OBJS += builtin/send-pack.o
BUILTIN_OBJS += builtin/shortlog.o
BUILTIN_OBJS += builtin/show-branch.o
BUILTIN_OBJS += builtin/show-ref.o
+BUILTIN_OBJS += builtin/skew.o
BUILTIN_OBJS += builtin/stripspace.o
BUILTIN_OBJS += builtin/symbolic-ref.o
BUILTIN_OBJS += builtin/tag.o
diff --git a/builtin.h b/builtin.h
index f2a25a0..e01ac4c 100644
--- a/builtin.h
+++ b/builtin.h
@@ -140,5 +140,6 @@ extern int cmd_verify_pack(int argc, const char **argv, const char *prefix);
extern int cmd_show_ref(int argc, const char **argv, const char *prefix);
extern int cmd_pack_refs(int argc, const char **argv, const char *prefix);
extern int cmd_replace(int argc, const char **argv, const char *prefix);
+extern int cmd_skew(int argc, const char **argv, const char *prefix);
#endif
diff --git a/builtin/skew.c b/builtin/skew.c
new file mode 100644
index 0000000..169a9f4
--- /dev/null
+++ b/builtin/skew.c
@@ -0,0 +1,62 @@
+#include "cache.h"
+#include "commit.h"
+#include "diff.h"
+#include "revision.h"
+
+unsigned long worst_skew = 0;
+unsigned char worst_skew_sha1[20];
+unsigned long worst_run = 0;
+unsigned char worst_run_sha1[20];
+
+static void check_skew_recurse(struct commit *c, unsigned long when, int counter)
+{
+ struct commit_list *p;
+
+ if (c->object.flags & SEEN)
+ return;
+ c->object.flags |= SEEN;
+
+ if (parse_commit(c) < 0)
+ return;
+
+ if (c->date > when) {
+ unsigned long skew = c->date - when;
+ if (skew > worst_skew) {
+ worst_skew = skew;
+ hashcpy(worst_skew_sha1, c->object.sha1);
+ }
+ if (++counter > worst_run) {
+ worst_run = counter;
+ hashcpy(worst_run_sha1, c->object.sha1);
+ }
+ }
+ else
+ counter = 0;
+
+ for (p = c->parents; p; p = p->next)
+ check_skew_recurse(p->item, c->date < when ? c->date : when, counter);
+}
+
+static void check_skew(struct commit *c)
+{
+ check_skew_recurse(c, time(NULL), 0);
+}
+
+int cmd_skew(int argc, const char **argv, const char *prefix) {
+ struct rev_info revs;
+ int i;
+
+ git_config(git_default_config, NULL);
+ init_revisions(&revs, prefix);
+ argc = setup_revisions(argc, argv, &revs, NULL);
+
+ for (i = 0; i < revs.pending.nr; i++) {
+ struct object *o = revs.pending.objects[i].item;
+ if (o->type == OBJ_COMMIT)
+ check_skew((struct commit *)o);
+ }
+
+ printf("worst skew: %lu (%s)\n", worst_skew, sha1_to_hex(worst_skew_sha1));
+ printf("longest run: %lu (%s)\n", worst_run, sha1_to_hex(worst_run_sha1));
+ return 0;
+}
diff --git a/git.c b/git.c
index 0409ac9..1041858 100644
--- a/git.c
+++ b/git.c
@@ -405,6 +405,7 @@ static void handle_internal_command(int argc, const char **argv)
{ "verify-pack", cmd_verify_pack },
{ "show-ref", cmd_show_ref, RUN_SETUP },
{ "pack-refs", cmd_pack_refs, RUN_SETUP },
+ { "skew", cmd_skew, RUN_SETUP },
};
int i;
static const char ext[] = STRIP_EXTENSION;
--
1.7.3.2.216.g61ab7.dirty
^ permalink raw reply related [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-10-27 17:11 ` Jeff King
@ 2010-10-28 8:07 ` Clemens Buchacher
0 siblings, 0 replies; 46+ messages in thread
From: Clemens Buchacher @ 2010-10-28 8:07 UTC (permalink / raw)
To: Jeff King; +Cc: Jonathan Nieder, tytso, Avery Pennarun, git
[-- Attachment #1: Type: text/plain, Size: 2206 bytes --]
Hi Jeff,
On Wed, Oct 27, 2010 at 10:11:45AM -0700, Jeff King wrote:
>
> Thanks both of you for the extra data points. If you don't mind, would
> you consider running my updated git-skew below on your test cases (or
> tweaking your skew detectors, since you both seem to be getting a '#
> skewed' column that mine didn't output).
I think this works well for small skews and for positive skews,
i.e., if the date goes back to the future. But if the date goes
into the past, that time is used as the new reference, and all
subsequently traversed commits are considered skewed. So for
example, if I add the following commit to git.git's current master,
the longest run becomes 1092 commits.
$ GIT_COMMITTER_DATE=$(date -d "now-1 year") git commit --allow-empty -m add-skew
To solve this, we could keep track of a window of the last n
commits traversed and take as a new time reference the largest date
within that window which is smaller than the previous reference.
That way we would fail to detect skew only if all of the commits in
that window are skewed into the past or into the future.
This particular scenario does not seem to occur in any of the repos
I tested, except maybe for the mesa repo. But manual inspection
shows that that repo has very long runs of skewed commits anyways.
linux 99 days 80
wine 1 14 days 1
mesa 4930 150 days 1520
xf86-video-ati 13 ~2.5 hrs 4
xf86-video-intel 26 8 hrs 4
xf86-video-nouveau 12 10 hrs 9
fluxbox 0 0 0
metacity 0 0 0
openbox 8 4 hrs 4
giggle 2 21 min 2
glibc 2 931 days 1
Clemens
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-05 12:27 ` Jeff King
` (4 preceding siblings ...)
2010-07-05 12:39 ` Why is "git tag --contains" so slow? Jeff King
@ 2010-07-05 14:10 ` tytso
2010-07-06 11:58 ` Jeff King
5 siblings, 1 reply; 46+ messages in thread
From: tytso @ 2010-07-05 14:10 UTC (permalink / raw)
To: Jeff King; +Cc: Avery Pennarun, git
On Mon, Jul 05, 2010 at 08:27:23AM -0400, Jeff King wrote:
> As you probably guessed from the specificity of the number, I wrote a
> short program to actually traverse and find the worst skew. It takes
> about 5 seconds to run (unsurprisingly, since it is doing the same full
> traversal that we end up doing in the above numbers). So we could
> "autoskew" by setting up the configuration on clone, and then
> periodically updating it as part of "git gc".
>
> That is perhaps over-engineering (and would add a few seconds to a
> clone), but I like that it would Just Work without the user doing
> anything.
As time progresses, the clock skew breakage should be less likely to
be hit by a typical developer, right? That is, unless you are
specifically referencing one of the commits which were skewed, two
years from now, the chances of someone (who isn't doing code
archeology) of getting hit by a problem should be small, right? This
seems to be definitely the case with "git tag --contains"; would it be
true for git name-rev and the other places that depend on (roughly)
increasing commit times?
If so, I could imagine the automagic scheme choosing a default that
only finds the worst skew in the past N months. This would speed up
things up for users who are using repositories that have skews in the
distant past, at the cost of introducing potentially confusuing edge
cases for people doing code archeology.
I'm not sure this is a good tradeoff, but given in practice how rarely
most developers go back in time more than say, 12-24 months, maybe
it's worth doing. What do you think?
- Ted
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-07-05 14:10 ` tytso
@ 2010-07-06 11:58 ` Jeff King
2010-07-06 15:31 ` Will Palmer
0 siblings, 1 reply; 46+ messages in thread
From: Jeff King @ 2010-07-06 11:58 UTC (permalink / raw)
To: tytso; +Cc: Avery Pennarun, git
On Mon, Jul 05, 2010 at 10:10:12AM -0400, tytso@mit.edu wrote:
> As time progresses, the clock skew breakage should be less likely to
> be hit by a typical developer, right? That is, unless you are
> specifically referencing one of the commits which were skewed, two
> years from now, the chances of someone (who isn't doing code
> archeology) of getting hit by a problem should be small, right? This
It's not about directly referencing skewed commits. It's about
traversing history that contains skewed commits. So if I have a history
like:
A -- B -- C -- D
and "B" is skewed, then I will generally give up on finding "A" when
searching backwards from "C" or "D", or their descendants. So as time
moves forward, you will continue to have your old tags pointing to "C"
or "D", but also tags pointing to their descendants. Doing "git tag
--contains A" will continue to be inaccurate, since it will continue to
look for "A" from "C" and "D", but also from newer tags, all of which
involve traversing the skewed "B".
What I think is true is that people will be less likely to look at "A"
as time goes on, as code it introduced presumably becomes less relevant
(either bugs are shaken out, or it gets replaced, or whatever). And
obviously looking at "C" from "D", the skew in "B" will be irrelevant.
So I think typical developers become less likely to hit the issue as
time goes on, but software archaeologists will hit it forever.
> If so, I could imagine the automagic scheme choosing a default that
> only finds the worst skew in the past N months. This would speed up
> things up for users who are using repositories that have skews in the
> distant past, at the cost of introducing potentially confusuing edge
> cases for people doing code archeology.
How do you decide, when looking for commits that have bogus timestamps,
which ones happened in the past N months? Certainly you can do some
statistical analysis to pick out anomalous ones. And you could perhaps
favor future skewing over past skewing, since that skew doesn't tend to
impact traversal cutoffs (and large past skewing seems to be more
common). But that is getting kind of complex.
> I'm not sure this is a good tradeoff, but given in practice how rarely
> most developers go back in time more than say, 12-24 months, maybe
> it's worth doing. What do you think?
I'm not sure. I am tempted to just default it to 86400 and go no
further. People who care about archaeology can turn off traversal
cutoffs if they like, and as the skewed history ages, people get less
likely to look at it. We could also pick half a year or some high number
as the default allowable. The performance increase is still quite
noticeable there, and it covers the only large skew we know about. I'd
be curious to see if other projects have skew, and how much.
-Peff
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-06 11:58 ` Jeff King
@ 2010-07-06 15:31 ` Will Palmer
2010-07-06 16:53 ` tytso
` (2 more replies)
0 siblings, 3 replies; 46+ messages in thread
From: Will Palmer @ 2010-07-06 15:31 UTC (permalink / raw)
To: Jeff King; +Cc: tytso, Avery Pennarun, git
On Tue, 2010-07-06 at 07:58 -0400, Jeff King wrote:
> On Mon, Jul 05, 2010 at 10:10:12AM -0400, tytso@mit.edu wrote:
> > I'm not sure this is a good tradeoff, but given in practice how rarely
> > most developers go back in time more than say, 12-24 months, maybe
> > it's worth doing. What do you think?
>
> I'm not sure. I am tempted to just default it to 86400 and go no
> further. People who care about archaeology can turn off traversal
> cutoffs if they like, and as the skewed history ages, people get less
> likely to look at it. We could also pick half a year or some high number
> as the default allowable. The performance increase is still quite
> noticeable there, and it covers the only large skew we know about. I'd
> be curious to see if other projects have skew, and how much.
>
> -Peff
Is it wrong to expect that git perform poorly in the edge-cases (hugely
skewed timestamps), but that it perform /correctly/ in all cases?
Clearly, marking already-traversed histories was the right thing to do,
and if I read correctly, made a good improvement on its own. But you
seem to have crossed a line at some point between "optimization" and
"potentially giving the wrong answer because it's faster"
Or am I just misunderstanding here?
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-07-06 15:31 ` Will Palmer
@ 2010-07-06 16:53 ` tytso
2010-07-08 11:28 ` Jeff King
2010-07-07 17:45 ` Jeff King
2010-07-07 17:50 ` Jeff King
2 siblings, 1 reply; 46+ messages in thread
From: tytso @ 2010-07-06 16:53 UTC (permalink / raw)
To: Will Palmer; +Cc: Jeff King, Avery Pennarun, git
On Tue, Jul 06, 2010 at 04:31:43PM +0100, Will Palmer wrote:
> Is it wrong to expect that git perform poorly in the edge-cases (hugely
> skewed timestamps), but that it perform /correctly/ in all cases?
>
> Clearly, marking already-traversed histories was the right thing to do,
> and if I read correctly, made a good improvement on its own. But you
> seem to have crossed a line at some point between "optimization" and
> "potentially giving the wrong answer because it's faster"
When "it's faster" is between 100-1000 times faster, I think we have
to look at things a bit more closely. That's the difference between a
command being usable and not usable.
We would be much better off if our tools enforced the fact that
committer times were always increasing. If from the beginning, we had
introduced checks so that "git commit" refused to create new commits
where the committer time was before its parent commit(s), and
git-receive-pack refused to accept packs that contained
non-monotonically increasing commits or commits that occurred in the
future according to its system clock, then these optimizations would
be completely valid.
But we didn't, and we do have skew in some repositories. So the
question is what to do going forward? One solution might be to
enforce this moving forward, and to have varying levels of strictness
in enforcing this constraint. So for completely new repositories,
this becomes a non-brainer. For older repositories, Jeff's idea of
having a tunable parameter so that results are correct given a maximum
clock skew --- which can be determined --- will allow us to have
correctness _and_ performance.
- Ted
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-06 16:53 ` tytso
@ 2010-07-08 11:28 ` Jeff King
2010-07-08 13:21 ` Will Palmer
0 siblings, 1 reply; 46+ messages in thread
From: Jeff King @ 2010-07-08 11:28 UTC (permalink / raw)
To: tytso; +Cc: Will Palmer, Avery Pennarun, git
On Tue, Jul 06, 2010 at 12:53:36PM -0400, tytso@mit.edu wrote:
> We would be much better off if our tools enforced the fact that
> committer times were always increasing. If from the beginning, we had
> introduced checks so that "git commit" refused to create new commits
> where the committer time was before its parent commit(s), and
> git-receive-pack refused to accept packs that contained
> non-monotonically increasing commits or commits that occurred in the
> future according to its system clock, then these optimizations would
> be completely valid.
>
> But we didn't, and we do have skew in some repositories. So the
> question is what to do going forward? One solution might be to
> enforce this moving forward, and to have varying levels of strictness
> in enforcing this constraint. So for completely new repositories,
Whatever we do with the optimization, I do agree with your suggestion at
least for "git commit" to avoid making such commits. Rejecting them
during fetchs and pushes would be a nice, too, but should probably just
be a warning at first, in case you have to pull from somebody with an
older git. You would also have to consider whether some small skew is
acceptable during a pull. Something like a 5-second skew is not a big
deal. If you had thousands of such skews in a row, yes, it would be bad,
but that is not likely to happen (and I can't think of some way to
maliciously create such a history that would not otherwise be
unusable).
> this becomes a non-brainer. For older repositories, Jeff's idea of
> having a tunable parameter so that results are correct given a maximum
> clock skew --- which can be determined --- will allow us to have
> correctness _and_ performance.
Yeah. I think the real question is what the default for that parameter
should be: pessimistic but always correct, optimistic but possibly
incorrect in the face of skew, or auto-tuned per-repository.
-Peff
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 11:28 ` Jeff King
@ 2010-07-08 13:21 ` Will Palmer
2010-07-08 13:54 ` tytso
0 siblings, 1 reply; 46+ messages in thread
From: Will Palmer @ 2010-07-08 13:21 UTC (permalink / raw)
To: Jeff King; +Cc: tytso, Avery Pennarun, git
On Thu, 2010-07-08 at 07:28 -0400, Jeff King wrote:
> On Tue, Jul 06, 2010 at 12:53:36PM -0400, tytso@mit.edu wrote:
> Whatever we do with the optimization, I do agree with your suggestion at
> least for "git commit" to avoid making such commits. Rejecting them
> during fetchs and pushes would be a nice, too, but should probably just
> be a warning at first, in case you have to pull from somebody with an
> older git...[snip]
> Yeah. I think the real question is what the default for that parameter
> should be: pessimistic but always correct, optimistic but possibly
> incorrect in the face of skew, or auto-tuned per-repository.
> -Peff
I think these two go hand-in-hand, and would resolve most of my issues
with it. Auto-tune, starting pessimistically, but then using something
more-optimized after something like gc has detected that it's okay. On
pull from an older repository (which I see as happening very frequently,
I add remotes much more often than I do a straight "clone"), a warning
and an auto-tune to something which would account for the newly-fetched
bad data.
My only other objection is more wishy-washy and/or lazy: currently a
"commit" doesn't need to know anything at all about what it references
in order to be considered a valid object, but saying "the time of commit
needs to be equal to or greater than the parent commit" means that a
tool.. and by "tool" I mean "wretched abuse of cat-file and sed", which
is sometimes just faster to throw-together than filter-branch ..needs to
be more aware of what it's doing. Yes, it's a horrible abuse, but I was
always under the impression that low-level abuse of the system is
something which git supports, by virtue of having such a simple model.
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 13:21 ` Will Palmer
@ 2010-07-08 13:54 ` tytso
0 siblings, 0 replies; 46+ messages in thread
From: tytso @ 2010-07-08 13:54 UTC (permalink / raw)
To: Will Palmer; +Cc: Jeff King, Avery Pennarun, git
On Thu, Jul 08, 2010 at 02:21:35PM +0100, Will Palmer wrote:
> I think these two go hand-in-hand, and would resolve most of my issues
> with it. Auto-tune, starting pessimistically, but then using something
> more-optimized after something like gc has detected that it's okay. On
> pull from an older repository (which I see as happening very frequently,
> I add remotes much more often than I do a straight "clone"), a warning
> and an auto-tune to something which would account for the newly-fetched
> bad data.
Well, keep in mind that we've been using a one-day "maximum clock skew
or you start getting incorrect results" for quite a while. We just
haven't necessarily publicized this fact or added enforcement to "git
commit" and git-receive-pack. And I've been introducing clock skews
of about 3 months (roughly equal to the time between Linux stable
releases) into the Linux kernel repository for some 1-2 years (because
I just didn't know about the clock skew dependency and there was no
enforcement of the same), and the number of times people have noticed,
or at least complained, has been relatively small. So like it or not,
the default of "one day clock skew or you get incorrect results" is
the status quo.
Your idea of being utterly pessimistic until the next "git gc" is
interesting, since it doesn't slow down the "git clone step".
Unfortunately, it also means that commands like "git name-rev" will be
several hundred times slower than they currently are (which probably
makes them unusable) until the first "git gc" --- this is the fact
that we've been depending on the clock skew being less than one day
for quite some time already; again, it _is_ the status quo.
And, "git gc" takes quite a bit longer than scanning for the maximum
skew after doing a "git clone". Given that "git clone" generally
takes a good long time anyway, adding 1-3 seconds after a clone seems
to be the better way to go. I think the biggest issue with it is the
complexity concern which Jeff has raised.
Given that, it would seem to me that (a) auto-tuning when cloning, (b)
defaulting to one-day and then auto-tuning on "git gc", or (c)
defaulting to one-day and not auto-tuning at all (the status quo) seem
to be the three most reasonable, listed in order of my preference.
As far as enforcement is concerned, we have choices of (a) add
warnings, which later become hard errors if the skew is greater than
some configurable window, (b) scan for skews during commits and
receive-packs, and update the auto-tune based on the skews found, or
(c) do nothing (the status quo). (b) is the most user friendly, but
it adds more complexity, which is why I think (a) edges it out as a
better choice, but fortunately, I'm not the one who's paid the big
bucks to make these sorts of decisions. :-)
> My only other objection is more wishy-washy and/or lazy: currently a
> "commit" doesn't need to know anything at all about what it references
> in order to be considered a valid object, but saying "the time of commit
> needs to be equal to or greater than the parent commit" means that a
> tool.. and by "tool" I mean "wretched abuse of cat-file and sed", which
> is sometimes just faster to throw-together than filter-branch ..needs to
> be more aware of what it's doing. Yes, it's a horrible abuse, but I was
> always under the impression that low-level abuse of the system is
> something which git supports, by virtue of having such a simple model.
I don't know that it's that much more difficult. See the patch I
proposed for "guilt"; it was a ten line patch, and if you were willing
to be even more "quick and wretched", I could have made it a 3 or 4
line patch.
- Ted
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-06 15:31 ` Will Palmer
2010-07-06 16:53 ` tytso
@ 2010-07-07 17:45 ` Jeff King
2010-07-08 10:29 ` Theodore Tso
2010-07-07 17:50 ` Jeff King
2 siblings, 1 reply; 46+ messages in thread
From: Jeff King @ 2010-07-07 17:45 UTC (permalink / raw)
To: Will Palmer; +Cc: tytso, Avery Pennarun, git
On Tue, Jul 06, 2010 at 04:31:43PM +0100, Will Palmer wrote:
> Is it wrong to expect that git perform poorly in the edge-cases (hugely
> skewed timestamps), but that it perform /correctly/ in all cases?
When you put it that way, yes, I think the ideal behavior is that we are
always correct, fast in the common case, and slow for edge cases.
But there are some fuzzy areas here:
1. Is clock skew more than a day (or some number of seconds, whatever
it may be) an edge case, or is it simply breakage in the repo? In
an ideal world, it would simply be an edge case that causes
slowdown. But git already implements traversal-cutoff based on
date, at least in "git name-rev", so this is not a new issue. I
know we also look at the date for some other traversals (in fact, I
see lots of other cutoffs that don't even seem to have the one-day
slop). But I haven't looked closely enough to see just what will
break with a huge skew.
2. Not implementing traversal-cutoff based on date doesn't slow just
edge cases. It slows _all_ cases, by a factor of a hundred, on the
off chance that you might have an edge case.
By pre-calculating the per-repo max skew during clone and gc, you
can turn it into your "always correct, slower for edge cases". But:
a. It makes clone and gc a bit slower, even for non-edge cases.
b. It is not _always_ correct, as you have a lag period between
when skew is introduced into your repo (either by commit or by
fetch) and when you gc it. But it's closer.
And of course it's just complex, and I tend to shy away from
complexity when I can. The question to me comes back to (1) above.
Is massive clock skew a breakage that should produce a few
incorrect results, or is it something we should always handle?
-Peff
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-07-07 17:45 ` Jeff King
@ 2010-07-08 10:29 ` Theodore Tso
2010-07-08 11:12 ` Jakub Narebski
` (3 more replies)
0 siblings, 4 replies; 46+ messages in thread
From: Theodore Tso @ 2010-07-08 10:29 UTC (permalink / raw)
To: Jeff King; +Cc: Will Palmer, Avery Pennarun, git
On Jul 7, 2010, at 1:45 PM, Jeff King wrote:
> And of course it's just complex, and I tend to shy away from
> complexity when I can. The question to me comes back to (1) above.
> Is massive clock skew a breakage that should produce a few
> incorrect results, or is it something we should always handle?
Going back to the question that kicked off this thread, I wonder if there
is some way that cacheing could be used to speed up the all cases,
or at lest the edge cases, without imposing as much latency as tracking
the max skew? i.e., some thing like gitk's gitk.cache file. For bonus
points, it could be a cache file that is used by both gitk and git tag
--contains, git branch --contains, and git name-rev.
Does that sound like reasonable idea?
--Ted
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-07-08 10:29 ` Theodore Tso
@ 2010-07-08 11:12 ` Jakub Narebski
2010-07-08 19:29 ` Nicolas Pitre
2010-07-08 11:31 ` Jeff King
` (2 subsequent siblings)
3 siblings, 1 reply; 46+ messages in thread
From: Jakub Narebski @ 2010-07-08 11:12 UTC (permalink / raw)
To: Theodore Tso; +Cc: Jeff King, Will Palmer, Avery Pennarun, git
Theodore Tso <tytso@MIT.EDU> writes:
> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:
>
> > And of course it's just complex, and I tend to shy away from
> > complexity when I can. The question to me comes back to (1) above.
> > Is massive clock skew a breakage that should produce a few
> > incorrect results, or is it something we should always handle?
>
> Going back to the question that kicked off this thread, I wonder if there
> is some way that cacheing could be used to speed up the all cases,
> or at lest the edge cases, without imposing as much latency as tracking
> the max skew? i.e., some thing like gitk's gitk.cache file. For bonus
> points, it could be a cache file that is used by both gitk and git tag
> --contains, git branch --contains, and git name-rev.
>
> Does that sound like reasonable idea?
By the way, what had happened to the rev-cache project from GSoC 2009?
--
Jakub Narebski
Poland
ShadeHawk on #git
^ permalink raw reply [flat|nested] 46+ messages in thread* Re: Why is "git tag --contains" so slow?
2010-07-08 11:12 ` Jakub Narebski
@ 2010-07-08 19:29 ` Nicolas Pitre
2010-07-08 19:39 ` Avery Pennarun
0 siblings, 1 reply; 46+ messages in thread
From: Nicolas Pitre @ 2010-07-08 19:29 UTC (permalink / raw)
To: Jakub Narebski; +Cc: Theodore Tso, Jeff King, Will Palmer, Avery Pennarun, git
On Thu, 8 Jul 2010, Jakub Narebski wrote:
> Theodore Tso <tytso@MIT.EDU> writes:
> > On Jul 7, 2010, at 1:45 PM, Jeff King wrote:
> >
> > > And of course it's just complex, and I tend to shy away from
> > > complexity when I can. The question to me comes back to (1) above.
> > > Is massive clock skew a breakage that should produce a few
> > > incorrect results, or is it something we should always handle?
> >
> > Going back to the question that kicked off this thread, I wonder if there
> > is some way that cacheing could be used to speed up the all cases,
> > or at lest the edge cases, without imposing as much latency as tracking
> > the max skew? i.e., some thing like gitk's gitk.cache file. For bonus
> > points, it could be a cache file that is used by both gitk and git tag
> > --contains, git branch --contains, and git name-rev.
> >
> > Does that sound like reasonable idea?
>
> By the way, what had happened to the rev-cache project from GSoC 2009?
I think the person who worked on it did so in good faith, and that the
result is well done.
But I personally cannot convince myself this is fundamentally the right
solution to the issue. Maintaining another data structure to work
around defficiencies in the primary data structure doesn't sound right
to me.
I might be looking at this from my own perspective as one of the few
people who hacked extensively on the Git pack format from the very
beginning. But I do see a way for the pack format to encode commit and
tree objects so that walking them would be a simple lookup in the pack
index file where both the SHA1 and offset in the pack for each parent
can be immediately retrieved. Same for tree references. No deflating
required, no binary search, just simple dereferences. And the pack size
would even shrink as a side effect.
Nicolas
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 19:29 ` Nicolas Pitre
@ 2010-07-08 19:39 ` Avery Pennarun
2010-07-08 20:13 ` Nicolas Pitre
0 siblings, 1 reply; 46+ messages in thread
From: Avery Pennarun @ 2010-07-08 19:39 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Jakub Narebski, Theodore Tso, Jeff King, Will Palmer, git
On Thu, Jul 8, 2010 at 3:29 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
> On Thu, 8 Jul 2010, Jakub Narebski wrote:
>> By the way, what had happened to the rev-cache project from GSoC 2009?
>
> I think the person who worked on it did so in good faith, and that the
> result is well done.
>
> But I personally cannot convince myself this is fundamentally the right
> solution to the issue. Maintaining another data structure to work
> around defficiencies in the primary data structure doesn't sound right
> to me.
>
> I might be looking at this from my own perspective as one of the few
> people who hacked extensively on the Git pack format from the very
> beginning. But I do see a way for the pack format to encode commit and
> tree objects so that walking them would be a simple lookup in the pack
> index file where both the SHA1 and offset in the pack for each parent
> can be immediately retrieved. Same for tree references. No deflating
> required, no binary search, just simple dereferences. And the pack size
> would even shrink as a side effect.
One trick that bup uses is an additional file that sits alongside the
pack and acts as an index. In bup's case, this is to work around
deficiencies in the .idx file format when using ridiculously huge
numbers of objects (hundreds of millions) across a large number of
packfiles. But the same concept could apply here: instead of doing
something like rev-cache, you could just construct the "efficient"
part of the packv4 format (which I gather is entirely related to
commit messages), and store it alongside each pack.
This would allow people to incrementally modify git to use the new,
efficient commit object storage, without breaking backward
compatibility with earlier versions of git. (Just as bup can index
huge numbers of packed objects but still stores them in the plain git
pack format.)
Just a thought. Thinking of it this way might make it easier to get
over the inertia of an entirely new packfile format.
Have fun,
Avery
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 19:39 ` Avery Pennarun
@ 2010-07-08 20:13 ` Nicolas Pitre
2010-07-08 21:20 ` Jakub Narebski
0 siblings, 1 reply; 46+ messages in thread
From: Nicolas Pitre @ 2010-07-08 20:13 UTC (permalink / raw)
To: Avery Pennarun; +Cc: Jakub Narebski, Theodore Tso, Jeff King, Will Palmer, git
[-- Attachment #1: Type: TEXT/PLAIN, Size: 2425 bytes --]
On Thu, 8 Jul 2010, Avery Pennarun wrote:
> On Thu, Jul 8, 2010 at 3:29 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
> > I might be looking at this from my own perspective as one of the few
> > people who hacked extensively on the Git pack format from the very
> > beginning. But I do see a way for the pack format to encode commit and
> > tree objects so that walking them would be a simple lookup in the pack
> > index file where both the SHA1 and offset in the pack for each parent
> > can be immediately retrieved. Same for tree references. No deflating
> > required, no binary search, just simple dereferences. And the pack size
> > would even shrink as a side effect.
>
> One trick that bup uses is an additional file that sits alongside the
> pack and acts as an index. In bup's case, this is to work around
> deficiencies in the .idx file format when using ridiculously huge
> numbers of objects (hundreds of millions) across a large number of
> packfiles. But the same concept could apply here: instead of doing
> something like rev-cache, you could just construct the "efficient"
> part of the packv4 format (which I gather is entirely related to
> commit messages), and store it alongside each pack.
No. I want the essential information in an efficient encoding _inside_
the pack, actually replacing the existing encoding. One of the goal is
also to reduce repository size, not to grow it.
> This would allow people to incrementally modify git to use the new,
> efficient commit object storage, without breaking backward
> compatibility with earlier versions of git. (Just as bup can index
> huge numbers of packed objects but still stores them in the plain git
> pack format.)
Initially, what I'm aiming for is for pack-objects to produce the new
format, for index-pack to grok it, and for sha1_file:unpack_entry() to
simply regenerate the canonical object format whenever a pack v4 object
is encountered. Also pack-objects would be able to revert the object
encoding to the current format on the fly when it is serving a fetch
request to a client which is not pack v4 aware, just like we do now with
the ofs-delta capability.
Once that stage is reached, I'll submit the lot and hope that other
people will help incrementally converting part of Git to benefit from
native access to the pack v4 data. The tree object walk code would be
the first obvious candidate. And so on.
Nicolas
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 20:13 ` Nicolas Pitre
@ 2010-07-08 21:20 ` Jakub Narebski
2010-07-08 21:30 ` Sverre Rabbelier
2010-07-08 23:15 ` Nicolas Pitre
0 siblings, 2 replies; 46+ messages in thread
From: Jakub Narebski @ 2010-07-08 21:20 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Avery Pennarun, Theodore Tso, Jeff King, Will Palmer, git
Dnia czwartek 8. lipca 2010 22:13, Nicolas Pitre napisał:
> On Thu, 8 Jul 2010, Avery Pennarun wrote:
> > On Thu, Jul 8, 2010 at 3:29 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
> > > I might be looking at this from my own perspective as one of the few
> > > people who hacked extensively on the Git pack format from the very
> > > beginning. But I do see a way for the pack format to encode commit and
> > > tree objects so that walking them would be a simple lookup in the pack
> > > index file where both the SHA1 and offset in the pack for each parent
> > > can be immediately retrieved. Same for tree references. No deflating
> > > required, no binary search, just simple dereferences. And the pack size
> > > would even shrink as a side effect.
> >
> > One trick that bup uses is an additional file that sits alongside the
> > pack and acts as an index. In bup's case, this is to work around
> > deficiencies in the .idx file format when using ridiculously huge
> > numbers of objects (hundreds of millions) across a large number of
> > packfiles. But the same concept could apply here: instead of doing
> > something like rev-cache, you could just construct the "efficient"
> > part of the packv4 format (which I gather is entirely related to
> > commit messages), and store it alongside each pack.
>
> No. I want the essential information in an efficient encoding _inside_
> the pack, actually replacing the existing encoding. One of the goal is
> also to reduce repository size, not to grow it.
That's a good idea.
> > This would allow people to incrementally modify git to use the new,
> > efficient commit object storage, without breaking backward
> > compatibility with earlier versions of git. (Just as bup can index
> > huge numbers of packed objects but still stores them in the plain git
> > pack format.)
>
> Initially, what I'm aiming for is for pack-objects to produce the new
> format, for index-pack to grok it, and for sha1_file:unpack_entry() to
> simply regenerate the canonical object format whenever a pack v4 object
> is encountered. Also pack-objects would be able to revert the object
> encoding to the current format on the fly when it is serving a fetch
> request to a client which is not pack v4 aware, just like we do now with
> the ofs-delta capability.
>
> Once that stage is reached, I'll submit the lot and hope that other
> people will help incrementally converting part of Git to benefit from
> native access to the pack v4 data. The tree object walk code would be
> the first obvious candidate. And so on.
If I remember correctly with pack v4 some operations like getting size
of tree object needs encoding to current format, so they are slower than
they should be (and perhaps a bit slower than current implementation).
But that should be I think rare (well, unless one streams to
'git cat-file --batch / --batch-check').
Would pack v4 need index v4?
By the way, rev-cache project was started mainly to make "counting
objects" part of clone / fetch faster. Would pack v4 offer the same
without rev-cache?
--
Jakub Narebski
Poland
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 21:20 ` Jakub Narebski
@ 2010-07-08 21:30 ` Sverre Rabbelier
2010-07-08 23:10 ` Nicolas Pitre
2010-07-08 23:15 ` Nicolas Pitre
1 sibling, 1 reply; 46+ messages in thread
From: Sverre Rabbelier @ 2010-07-08 21:30 UTC (permalink / raw)
To: Nicolas Pitre
Cc: Jakub Narebski, Avery Pennarun, Theodore Tso, Jeff King,
Will Palmer, git
Heya,
2010/7/8 Jakub Narebski <jnareb@gmail.com>:
> By the way, rev-cache project was started mainly to make "counting
> objects" part of clone / fetch faster. Would pack v4 offer the same
> without rev-cache?
Speaking of pack v4 features...
I remember from GitTogether08 that one hope was that the metadata
would be in a different file, such that it could be retrieved
separately (allowing shallow clones to create and push new commits).
Is this not something that is part of the design goals for packv4?
--
Cheers,
Sverre Rabbelier
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 21:30 ` Sverre Rabbelier
@ 2010-07-08 23:10 ` Nicolas Pitre
0 siblings, 0 replies; 46+ messages in thread
From: Nicolas Pitre @ 2010-07-08 23:10 UTC (permalink / raw)
To: Sverre Rabbelier
Cc: Jakub Narebski, Avery Pennarun, Theodore Tso, Jeff King,
Will Palmer, git
[-- Attachment #1: Type: TEXT/PLAIN, Size: 674 bytes --]
On Thu, 8 Jul 2010, Sverre Rabbelier wrote:
> Heya,
>
> 2010/7/8 Jakub Narebski <jnareb@gmail.com>:
> > By the way, rev-cache project was started mainly to make "counting
> > objects" part of clone / fetch faster. Would pack v4 offer the same
> > without rev-cache?
>
> Speaking of pack v4 features...
>
> I remember from GitTogether08 that one hope was that the metadata
> would be in a different file, such that it could be retrieved
> separately (allowing shallow clones to create and push new commits).
> Is this not something that is part of the design goals for packv4?
No. And I don't see why a pack format change would need to be involved
either.
Nicolas
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 21:20 ` Jakub Narebski
2010-07-08 21:30 ` Sverre Rabbelier
@ 2010-07-08 23:15 ` Nicolas Pitre
1 sibling, 0 replies; 46+ messages in thread
From: Nicolas Pitre @ 2010-07-08 23:15 UTC (permalink / raw)
To: Jakub Narebski; +Cc: Avery Pennarun, Theodore Tso, Jeff King, Will Palmer, git
On Thu, 8 Jul 2010, Jakub Narebski wrote:
> If I remember correctly with pack v4 some operations like getting size
> of tree object needs encoding to current format, so they are slower than
> they should be (and perhaps a bit slower than current implementation).
> But that should be I think rare (well, unless one streams to
> 'git cat-file --batch / --batch-check').
I didn't write the code to recreate canonical object format yet, but I
suspect that the pack v4 object encoding will have to carry the size for
the canonical version.
> Would pack v4 need index v4?
So far, no.
> By the way, rev-cache project was started mainly to make "counting
> objects" part of clone / fetch faster. Would pack v4 offer the same
> without rev-cache?
That's indeed the main goal.
Nicolas
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 10:29 ` Theodore Tso
2010-07-08 11:12 ` Jakub Narebski
@ 2010-07-08 11:31 ` Jeff King
2010-07-08 14:35 ` Johan Herland
2010-07-08 19:06 ` Nicolas Pitre
3 siblings, 0 replies; 46+ messages in thread
From: Jeff King @ 2010-07-08 11:31 UTC (permalink / raw)
To: Theodore Tso; +Cc: Nick Edelen, Will Palmer, Avery Pennarun, git
On Thu, Jul 08, 2010 at 06:29:04AM -0400, Theodore Tso wrote:
> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:
>
> > And of course it's just complex, and I tend to shy away from
> > complexity when I can. The question to me comes back to (1) above.
> > Is massive clock skew a breakage that should produce a few
> > incorrect results, or is it something we should always handle?
>
> Going back to the question that kicked off this thread, I wonder if there
> is some way that cacheing could be used to speed up the all cases,
> or at lest the edge cases, without imposing as much latency as tracking
> the max skew? i.e., some thing like gitk's gitk.cache file. For bonus
> points, it could be a cache file that is used by both gitk and git tag
> --contains, git branch --contains, and git name-rev.
>
> Does that sound like reasonable idea?
It sounds reasonable to me. It just needs somebody to design and
implement it. :)
I don't know anything about how gitk.cache works. Caching tag refs is
not that hard, because the refs tend not to change. Doing arbitrary "X
contains Y" caching is much harder, and I think you would have to build
it on Nick's rev-cache work. Maybe he (cc'd) has some ideas.
-Peff
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 10:29 ` Theodore Tso
2010-07-08 11:12 ` Jakub Narebski
2010-07-08 11:31 ` Jeff King
@ 2010-07-08 14:35 ` Johan Herland
2010-07-08 19:06 ` Nicolas Pitre
3 siblings, 0 replies; 46+ messages in thread
From: Johan Herland @ 2010-07-08 14:35 UTC (permalink / raw)
To: Theodore Tso; +Cc: git, Jeff King, Will Palmer, Avery Pennarun
[-- Attachment #1: Type: text/plain, Size: 1638 bytes --]
On Thursday 08 July 2010, Theodore Tso wrote:
> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:
> > And of course it's just complex, and I tend to shy away from
> > complexity when I can. The question to me comes back to (1)
> > above. Is massive clock skew a breakage that should produce a few
> > incorrect results, or is it something we should always handle?
>
> Going back to the question that kicked off this thread, I wonder if
> there is some way that cacheing could be used to speed up the all
> cases, or at lest the edge cases, without imposing as much latency as
> tracking the max skew? i.e., some thing like gitk's gitk.cache
> file. For bonus points, it could be a cache file that is used by
> both gitk and git tag --contains, git branch --contains, and git
> name-rev.
>
> Does that sound like reasonable idea?
Here's a quick-and-dirty POC which builds a mapping from commits to
their children and stores it using git notes [1], and then uses that to
implement 'git tag --contains <commit>' by traversing _forwards_ from
<commit> and printing all tags we encounter along the way [2].
[1]: The attached "build_childnotes.py" script builds this mapping.
Invoke as follows:
git log --all --format="%H,%P" |
./build_childnotes.py |
git fast-import
[2]: The attached "git_tag_contains.py" script traverses the notes
printing out tags along the way. Invoke it as follows:
git_tag_contains.py <commit>
The second script is way too slow, and really needs to use "git
cat-file --batch" to not fork a process for every commit in history...
...Johan
--
Johan Herland, <johan@herland.net>
www.herland.net
[-- Attachment #2: build_childnotes.py --]
[-- Type: application/x-python, Size: 551 bytes --]
[-- Attachment #3: git_tag_contains.py --]
[-- Type: application/x-python, Size: 836 bytes --]
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-08 10:29 ` Theodore Tso
` (2 preceding siblings ...)
2010-07-08 14:35 ` Johan Herland
@ 2010-07-08 19:06 ` Nicolas Pitre
3 siblings, 0 replies; 46+ messages in thread
From: Nicolas Pitre @ 2010-07-08 19:06 UTC (permalink / raw)
To: Theodore Tso; +Cc: Jeff King, Will Palmer, Avery Pennarun, git
On Thu, 8 Jul 2010, Theodore Tso wrote:
>
> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:
>
> > And of course it's just complex, and I tend to shy away from
> > complexity when I can. The question to me comes back to (1) above.
> > Is massive clock skew a breakage that should produce a few
> > incorrect results, or is it something we should always handle?
>
> Going back to the question that kicked off this thread, I wonder if there
> is some way that cacheing could be used to speed up the all cases,
> or at lest the edge cases, without imposing as much latency as tracking
> the max skew? i.e., some thing like gitk's gitk.cache file. For bonus
> points, it could be a cache file that is used by both gitk and git tag
> --contains, git branch --contains, and git name-rev.
>
> Does that sound like reasonable idea?
I don't think any caching would be as good as fixing the fundamental
issue.
Git is fast, sure. But it could be way faster yet in its graph
traversal. And my pack v4 format is meant to overcome all those
obstacles that Git currently has to work through in order to walk its
commit graph. Once one realize that most of the commit object headers
are SHA1 reference which need no be compressed with zlib as it is done
now, and that the author and committer info can be factored out in a
dictionary table, and that even those SHA1 references can be substituted
with an index value into the pack index file (a bit like the OFS variant
of the delta object), meaning that even the object lookup could be
bypassed, then it would be possible to make graph traversal a magnitude
cheaper in terms of computing cycles and memory touched.
The pack format v4 has been brewing in my head for... well... years now.
And that is good because I've improved on the original v4 design even
more since then. And I even found some time to write more code lately.
I have the new object encoding code almost working for trees and
commits. My Git hacking time is still limited so this is progressing
slowly though.
Just to say that I don't think any kind of caching might be necessary in
the end, as it is possible to encode object data in a pack in a way that
ought to be about as fast to access as a separate cache would. So if
someone is pondering about working on a cache layer, then I'd have one
alternate suggestion or two for that person. ;-)
Nicolas
^ permalink raw reply [flat|nested] 46+ messages in thread
* Re: Why is "git tag --contains" so slow?
2010-07-06 15:31 ` Will Palmer
2010-07-06 16:53 ` tytso
2010-07-07 17:45 ` Jeff King
@ 2010-07-07 17:50 ` Jeff King
2 siblings, 0 replies; 46+ messages in thread
From: Jeff King @ 2010-07-07 17:50 UTC (permalink / raw)
To: Will Palmer; +Cc: tytso, Avery Pennarun, git
On Tue, Jul 06, 2010 at 04:31:43PM +0100, Will Palmer wrote:
> Clearly, marking already-traversed histories was the right thing to do,
> and if I read correctly, made a good improvement on its own. But you
> seem to have crossed a line at some point between "optimization" and
> "potentially giving the wrong answer because it's faster"
As a side-note to what I said in my other email, the sinful thing here
is not this optimization (my patch 2/4). It's _defaulting_ the
optimization to on (my patch 3/4). With just 2/4, it's something that a
user can enable to get better speed if they feel confident there is no
large skew in their repo.
-Peff
^ permalink raw reply [flat|nested] 46+ messages in thread