Re: Git commit generation numbers

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Jul 15, 2011, 23:10 UTC
Message-ID: <CA+55aFzE-okH9gaEyuSFdorK-7v3odpsk65ZTqCMHFz80n65ug@mail.gmail.com>
In-Reply-To: <CA+55aFx0KyAZRsy7gZ3Z4woWC-uWcLu11gcUrR+9MJR5NOSkrA@mail.gmail.com>

On Fri, Jul 15, 2011 at 2:17 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote:

>
> For example, for the "git tag --contains" thing, what's the
> performance effect of just skipping tags that are much older than the
> commit we ask for?

Hmm.

Maybe there is something seriously wrong with this trivial patch, but it gave the right results for the test-cases I threw at it, and passes the tests.

Before:

   [torvalds@i5 linux]$ time git tag --contains v2.6.24 > correct

   real	0m7.548s
   user	0m7.344s
   sys	0m0.116s

After:

   [torvalds@i5 linux]$ time ~/git/git tag --contains v2.6.24 > date-cut-off

   real	0m0.161s
   user	0m0.140s
   sys	0m0.016s

and 'correct' and 'date-cut-off' both give the same answer.

The date-based "slop" thing is (at least *meant* to be - note the lack of any extensive testing) "at least five consecutive commits that have dates that are more than five days off".

Somebody should double-check my logic. Maybe I'm doing something stupid. Because that's a *big* difference.

                     Linus

 commit.c |   42 +++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 41 insertions(+), 1 deletions(-)

diff --git a/commit.c b/commit.c
index ac337c7d7dc1..0d33c33a6520 100644
--- a/commit.c
+++ b/commit.c
@@ -737,16 +737,56 @@ struct commit_list *get_merge_bases(struct commit *one, struct commit *two,
 	return get_merge_bases_many(one, 1, &two, cleanup);
 }
 
+#define VISITED (1 << 16)
+
+static int is_recursive_descendant(struct commit *commit, struct commit *target)
+{
+	int slop = 5;
+	parse_commit(target);
+	for (;;) {
+		struct commit_list *parents;
+		if (commit == target)
+			return 1;
+		if (commit->object.flags & VISITED)
+			return 0;
+		commit->object.flags |= VISITED;
+		parse_commit(commit);
+		if (commit->date + 5*24*60*60 < target->date) {
+			if (--slop <= 0)
+				return 0;
+		} else
+			slop = 5;
+		parents = commit->parents;
+		if (!parents)
+			return 0;
+		commit = parents->item;
+		parents = parents->next;
+		while (parents) {
+			if (is_recursive_descendant(parents->item, target))
+				return 1;
+			parents = parents->next;
+		}
+	}
+}
+
+static int is_descendant(struct commit *commit, struct commit *target)
+{
+	int ret = is_recursive_descendant(commit, target);
+	clear_commit_marks(commit, VISITED);
+	return ret;
+}
+
 int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
 {
 	if (!with_commit)
 		return 1;
+
 	while (with_commit) {
 		struct commit *other;
 
 		other = with_commit->item;
 		with_commit = with_commit->next;
-		if (in_merge_bases(other, &commit, 1))
+		if (is_descendant(commit, other))
 			return 1;
 	}
 	return 0;