git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 0/4] Speed up git tag --contains

From
Jeff King <peff@peff.net>
Date
Jul 6, 2011, 06:54 UTC
Message-ID
<20110706065452.GB927@sigill.intra.peff.net>
In-Reply-To
<20110706064012.GA927@sigill.intra.peff.net>
On Wed, Jul 06, 2011 at 02:40:12AM -0400, Jeff King wrote:
Show 5 quoted lines
> As it is now, I don't think so. Tweaking core.clockskew is slow, as
> shown above. And it's not something people should have to do manually. I
> have a version, which I'll post in a minute, which actually fills in a
> notes tree with the sha1 of commits with bogus timestamps. And then
> that tree can be consulted accurately and automatically.

Here's that patch. I think I did this after our discussion at GitTogether 2010, and haven't looked at it since. So beware.

Clemens mentioned elsewhere that my skew-detection programs only find skew in one direction. And I think that may be a problem here. We are basically finding commits which have a timestamp in the past from their most recent parent. So that means in a history like this:

  A---B---C--D--E--F
  timestamp(A) = 1
  timestamp(B) = 2
  timestamp(C) = 1
  timestamp(D) = 4
  timestamp(E) = 5

We will see that commit C is bogus, since it is in the past from its parent. But if a commit skews to the future:

  timestamp(A) = 1
  timestamp(B) = 2
  timestamp(C) = 6
  timestamp(D) = 4
  timestamp(E) = 5
then everything _after_ it will look bogus (D and E, in this case).
>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).

---
 .gitignore     |    1 +
 Makefile       |    1 +
 builtin.h      |    1 +
 builtin/skew.c |   56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 commit.c       |   20 +++++++++++++++++---
 git.c          |    1 +
 6 files changed, 77 insertions(+), 3 deletions(-)
 create mode 100644 builtin/skew.c
diff --git a/.gitignore b/.gitignore
index acffdfa..503ef8b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -137,6 +137,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 f8c72e1..f6ecc27 100644
--- a/Makefile
+++ b/Makefile
@@ -765,6 +765,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 0e9da90..0be47ca 100644
--- a/builtin.h
+++ b/builtin.h
@@ -143,5 +143,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..796b02a
--- /dev/null
+++ b/builtin/skew.c
@@ -0,0 +1,56 @@
+#include "cache.h"
+#include "commit.h"
+#include "diff.h"
+#include "revision.h"
+#include "notes-cache.h"
+
+struct notes_cache bogus_timestamps;
+
+static unsigned long check_skew(struct commit *c)
+{
+	struct commit_list *p;
+	unsigned long most_recent;
+
+	if (c->util)
+		return (unsigned long)c->util;
+
+	if (parse_commit(c) < 0)
+		die("unable to parse commit: %s", sha1_to_hex(c->object.sha1));
+
+	most_recent = 0;
+	for (p = c->parents; p; p = p->next) {
+		unsigned long timestamp = check_skew(p->item);
+		if (timestamp > most_recent)
+			most_recent = timestamp;
+	}
+
+	if (c->date + 86400 < most_recent)
+		notes_cache_put(&bogus_timestamps, c->object.sha1, "", 0);
+	else
+		most_recent = c->date;
+
+	c->util = (void *)most_recent;
+	return most_recent;
+}
+
+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);
+
+	notes_cache_init(&bogus_timestamps, "traversal-cutoff-ignore", "v1");
+
+	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);
+	}
+
+	if (notes_cache_write(&bogus_timestamps) < 0)
+		die_errno("unable to write notes tree");
+
+	return 0;
+}
diff --git a/commit.c b/commit.c
index 6647609..1bec48b 100644
--- a/commit.c
+++ b/commit.c
@@ -5,7 +5,7 @@
 #include "utf8.h"
 #include "diff.h"
 #include "revision.h"
-#include "notes.h"
+#include "notes-cache.h"
 
 int core_clock_skew = 86400;
 int save_commit_buffer = 1;
@@ -888,6 +888,19 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
 	return 0;
 }
 
+static int has_bogus_timestamp(unsigned char sha1[20])
+{
+	static int initialized;
+	static struct notes_cache bogus;
+
+	if (!initialized) {
+		notes_cache_init(&bogus, "traversal-cutoff-ignore", "v1");
+		initialized = 1;
+	}
+
+	return get_note(&bogus.tree, sha1) != NULL;
+}
+
 static int contains_recurse(struct commit *candidate,
 			    const struct commit_list *want,
 			    unsigned long cutoff)
@@ -908,8 +921,9 @@ static int contains_recurse(struct commit *candidate,
 		return 0;
 
 	/* stop searching if we go too far back in time */
-	if (candidate->date < cutoff)
-		return 0;
+	if (candidate->date < cutoff &&
+	    !has_bogus_timestamp(candidate->object.sha1))
+			return 0;
 
 	/* Otherwise recurse and mark ourselves for future traversals. */
 	for (p = candidate->parents; p; p = p->next) {
diff --git a/git.c b/git.c
index 8828c18..7adeba7 100644
--- a/git.c
+++ b/git.c
@@ -408,6 +408,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "show", cmd_show, RUN_SETUP },
 		{ "show-branch", cmd_show_branch, RUN_SETUP },
 		{ "show-ref", cmd_show_ref, RUN_SETUP },
+		{ "skew", cmd_skew, RUN_SETUP },
 		{ "stage", cmd_add, RUN_SETUP | NEED_WORK_TREE },
 		{ "status", cmd_status, RUN_SETUP | NEED_WORK_TREE },
 		{ "stripspace", cmd_stripspace },

-- 
1.7.6.20.g45f3f.dirty
Previous: Jeff KingNext: Clemens Buchacher
Message 7 of 28 in “Speed up git tag --contains”
  1. 0/4 Speed up git tag --containsÆvar Arnfjörð Bjarmason, Jun 11, 2011
  2. 1/4 tag: speed up --contains calculationÆvar Arnfjörð Bjarmason, Jun 11, 2011
  3. 2/4 limit "contains" traversals based on commit timestampÆvar Arnfjörð Bjarmason, Jun 11, 2011
  4. 3/4 default core.clockskew variable to one dayÆvar Arnfjörð Bjarmason, Jun 11, 2011
  5. 4/4 Why is "git tag --contains" so slow?Ævar Arnfjörð Bjarmason, Jun 11, 2011
  6. Jeff KingJul 6, 2011
  7. Jeff KingJul 6, 2011
  8. Clemens BuchacherJul 6, 2011
  9. Jonathan NiederJul 6, 2011
  10. Jeff KingJul 6, 2011
  11. Jakub NarebskiJul 6, 2011
  12. Ted Ts'oJul 6, 2011
  13. Jeff KingJul 6, 2011
  14. Jakub NarebskiJul 6, 2011
  15. Jeff KingJul 7, 2011
  16. Junio C HamanoJul 7, 2011
  17. Jakub NarebskiJul 7, 2011
  18. A Large Angry SCMJul 7, 2011
  19. Junio C HamanoJul 8, 2011
  20. Jeff KingJul 8, 2011
  21. Junio C HamanoJul 6, 2011
  22. Jeff KingJul 7, 2011
  23. Jakub NarebskiJul 7, 2011
  24. csilversJan 12, 2018
  25. Jeff KingMar 3, 2018
  26. csilversMar 8, 2018
  27. Derrick StoleeMar 12, 2018
  28. Jeff KingMar 12, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.