On Fri, Jul 15, 2011 at 2:17 PM, Linus Torvalds
<torvalds@xxxxxxxxxxxxxxxxxxxx> 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;