[PATCH 0/4] "merge-base" updates

[PATCH 0/4] "merge-base" updates

[Junio C Hamano]

This replaces the topmost commit from the earlier series that tried
to optimize N*(N-1) loop with N traversals.  With this, running the
following script in the kernel repository:

-- >8 --
#!/bin/sh

git rev-list --committer=torvalds@linux-foundation.org \
    --max-parents=2 --min-parents=2 --parents v3.5..v3.6-rc2 >RL

cmd='
	while read result parent1 parent2
	do
		$GIT merge-base $parent1 $parent2
	done <RL
'

GIT="rungit master" time sh -c "$cmd" >:stock
GIT=../git.git/git time sh -c "$cmd" >:optim
cmp :stock :optim
-- 8< --

shows a slight but measurable boost in the performance of
merge-base itself.

42.45user 3.79system 0:46.62elapsed 99%CPU (0avgtext+0avgdata 408176maxresident)k
0inputs+24outputs (0major+2708085minor)pagefaults 0swaps
39.99user 3.42system 0:43.27elapsed 100%CPU (0avgtext+0avgdata 408192maxresident)k
0inputs+24outputs (0major+2179604minor)pagefaults 0swaps

Junio C Hamano (4):
  merge_bases_many(): split out the logic to paint history
  merge-base: "--is-ancestor A B"
  in_merge_bases(): use paint_down_to_common()
  get_merge_bases_many(): walk from many tips in parallel

 builtin/merge-base.c |  21 ++++++++
 commit.c             | 143 +++++++++++++++++++++++++++++++++------------------
 2 files changed, 114 insertions(+), 50 deletions(-)

-- 
1.7.12.293.g6aeebca

[PATCH 1/4] merge_bases_many(): split out the logic to paint history

[Junio C Hamano]

Introduce a new helper function paint_down_to_common() that takes
the same parameters as merge_bases_many(), but without the first
optimization of not painting anything when "one" is one of the
"twos" (or vice versa), and the last clean-up of removing the common
ancestor that is known to be an ancestor of another common one.

This way, the caller of the new function could tell if "one" is
reachable from any of the "twos" by simply looking at the flag bits
of "one".  If (and only if) it is painted in PARENT2, it is
reachable from one of the "twos".
---
 commit.c | 47 ++++++++++++++++++++++++++++-------------------
 1 file changed, 28 insertions(+), 19 deletions(-)

diff --git a/commit.c b/commit.c
index 12e5396..0058fa5 100644
--- a/commit.c
+++ b/commit.c
@@ -581,28 +581,12 @@ static struct commit *interesting(struct commit_list *list)
 	return NULL;
 }
 
-static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
 {
 	struct commit_list *list = NULL;
 	struct commit_list *result = NULL;
 	int i;
 
-	for (i = 0; i < n; i++) {
-		if (one == twos[i])
-			/*
-			 * We do not mark this even with RESULT so we do not
-			 * have to clean it up.
-			 */
-			return commit_list_insert(one, &result);
-	}
-
-	if (parse_commit(one))
-		return NULL;
-	for (i = 0; i < n; i++) {
-		if (parse_commit(twos[i]))
-			return NULL;
-	}
-
 	one->object.flags |= PARENT1;
 	commit_list_insert_by_date(one, &list);
 	for (i = 0; i < n; i++) {
@@ -643,9 +627,34 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
 		}
 	}
 
-	/* Clean up the result to remove stale ones */
 	free_commit_list(list);
-	list = result; result = NULL;
+	return result;
+}
+
+static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+{
+	struct commit_list *list = NULL;
+	struct commit_list *result = NULL;
+	int i;
+
+	for (i = 0; i < n; i++) {
+		if (one == twos[i])
+			/*
+			 * We do not mark this even with RESULT so we do not
+			 * have to clean it up.
+			 */
+			return commit_list_insert(one, &result);
+	}
+
+	if (parse_commit(one))
+		return NULL;
+	for (i = 0; i < n; i++) {
+		if (parse_commit(twos[i]))
+			return NULL;
+	}
+
+	list = paint_down_to_common(one, n, twos);
+
 	while (list) {
 		struct commit_list *next = list->next;
 		if (!(list->item->object.flags & STALE))
-- 
1.7.12.293.g6aeebca

[PATCH 2/4] merge-base: "--is-ancestor A B"

[Junio C Hamano]

In many scripted Porcelain commands, we find this idiom:

    if test "$(git rev-parse --verify A)" = "$(git merge-base A B)"
    then
    	... A is an ancestor of B ...
    fi

But you do not have to compute exact merge-base only to see if A is
an ancestor of B.  Give them a more direct way to use the underlying
machinery.
---
 builtin/merge-base.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/builtin/merge-base.c b/builtin/merge-base.c
index 4f30f1b..615aa04 100644
--- a/builtin/merge-base.c
+++ b/builtin/merge-base.c
@@ -70,6 +70,20 @@ static int handle_octopus(int count, const char **args, int reduce, int show_all
 	return 0;
 }
 
+static int show_is_ancestor(int argc, const char **argv)
+{
+	struct commit *one, *two;
+
+	if (argc != 2)
+		die("--is-ancestor takes exactly two commits");
+	one = get_commit_reference(argv[0]);
+	two = get_commit_reference(argv[1]);
+	if (in_merge_bases(one, two))
+		return 0;
+	else
+		return 1;
+}
+
 int cmd_merge_base(int argc, const char **argv, const char *prefix)
 {
 	struct commit **rev;
@@ -77,11 +91,14 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	int show_all = 0;
 	int octopus = 0;
 	int reduce = 0;
+	int is_ancestor = 0;
 
 	struct option options[] = {
 		OPT_BOOLEAN('a', "all", &show_all, "output all common ancestors"),
 		OPT_BOOLEAN(0, "octopus", &octopus, "find ancestors for a single n-way merge"),
 		OPT_BOOLEAN(0, "independent", &reduce, "list revs not reachable from others"),
+		OPT_BOOLEAN(0, "is-ancestor", &is_ancestor,
+			    "is the first one ancestor of the other?"),
 		OPT_END()
 	};
 
@@ -89,6 +106,10 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	argc = parse_options(argc, argv, prefix, options, merge_base_usage, 0);
 	if (!octopus && !reduce && argc < 2)
 		usage_with_options(merge_base_usage, options);
+	if (is_ancestor && (show_all | octopus | reduce))
+		die("--is-reachable cannot be used with other options");
+	if (is_ancestor)
+		return show_is_ancestor(argc, argv);
 	if (reduce && (show_all || octopus))
 		die("--independent cannot be used with other options");
 
-- 
1.7.12.293.g6aeebca

Re: [PATCH 2/4] merge-base: "--is-ancestor A B"

[Martin von Zweigbergk]

(Resending as plain text, sorry about duplicate, Junio.)

On Thu, Aug 30, 2012 at 4:13 PM, Junio C Hamano <gitster@pobox.com> wrote:
>
> In many scripted Porcelain commands, we find this idiom:
>
>     if test "$(git rev-parse --verify A)" = "$(git merge-base A B)"
>     then
>         ... A is an ancestor of B ...
>     fi
>
> But you do not have to compute exact merge-base only to see if A is
> an ancestor of B.  Give them a more direct way to use the underlying
> machinery.

Thanks! It has bugged me ever since I first saw that idiom that there
was no way that better shows the intent.

> +       if (argc != 2)
> +               die("--is-ancestor takes exactly two commits");

I think git merge-base shows the usage message regardless if argc < 2,
so this only happens when more than two arguments are given. Maybe
include --is-ancestor in the usage message?

> +       if (is_ancestor && (show_all | octopus | reduce))
> +               die("--is-reachable cannot be used with other options");

I suppose --is-reachable should be --is-ancestor.

Re: [PATCH 2/4] merge-base: "--is-ancestor A B"

[Junio C Hamano]

Martin von Zweigbergk <martinvonz@gmail.com> writes:

>> +       if (argc != 2)
>> +               die("--is-ancestor takes exactly two commits");
>
> I think git merge-base shows the usage message regardless if argc < 2,
> so this only happens when more than two arguments are given.

Yes, but it is a good discipline not to depend too much on what
other parts of the code may have done, when you do not have to.

> Maybe
> include --is-ancestor in the usage message?

I think "merge-base -h" will get this for free thanks to parseopt.

>> +       if (is_ancestor && (show_all | octopus | reduce))
>> +               die("--is-reachable cannot be used with other options");
>
> I suppose --is-reachable should be --is-ancestor.

Thanks, that was a renaming error.

I'll squash the fix in with documentation.

 Documentation/git-merge-base.txt | 28 ++++++++++++++++++++++++++++
 builtin/merge-base.c             |  6 +++---
 2 files changed, 31 insertions(+), 3 deletions(-)

diff --git i/Documentation/git-merge-base.txt w/Documentation/git-merge-base.txt
index b295bf8..87842e3 100644
--- i/Documentation/git-merge-base.txt
+++ w/Documentation/git-merge-base.txt
@@ -11,6 +11,7 @@ SYNOPSIS
 [verse]
 'git merge-base' [-a|--all] <commit> <commit>...
 'git merge-base' [-a|--all] --octopus <commit>...
+'git merge-base' --is-ancestor <commit> <commit>
 'git merge-base' --independent <commit>...
 
 DESCRIPTION
@@ -50,6 +51,12 @@ from linkgit:git-show-branch[1] when used with the `--merge-base` option.
 	from any other.  This mimics the behavior of 'git show-branch
 	--independent'.
 
+--is-ancestor::
+	Check if the first <commit> is an ancestor of the second <commit>,
+	and exit with status 0 if true, or with status 1 if not.
+	Errors are signaled by a non-zero status that is not 1.
+
+
 OPTIONS
 -------
 -a::
@@ -110,6 +117,27 @@ both '1' and '2' are merge-bases of A and B.  Neither one is better than
 the other (both are 'best' merge bases).  When the `--all` option is not given,
 it is unspecified which best one is output.
 
+A common idiom to check "fast-forward-ness" between two commits A
+and B is (or at least used to be) to compute the merge base between
+A and B, and check if it is the same as A, in which case, A is an
+ancestor of B.  You will see this idiom used often in older scripts.
+
+	A=$(git rev-parse --verify A)
+	if test "$A" = "$(git merge-base A B)"
+	then
+		... A is an ancestor of B ...
+	fi
+
+In modern git, you can say this in a more direct way:
+
+	if git merge-base --is-ancestor A B
+	then
+		... A is an ancestor of B ...
+	fi
+
+instead.
+
+
 See also
 --------
 linkgit:git-rev-list[1],
diff --git i/builtin/merge-base.c w/builtin/merge-base.c
index 615aa04..447ab7c 100644
--- i/builtin/merge-base.c
+++ w/builtin/merge-base.c
@@ -70,7 +70,7 @@ static int handle_octopus(int count, const char **args, int reduce, int show_all
 	return 0;
 }
 
-static int show_is_ancestor(int argc, const char **argv)
+static int handle_is_ancestor(int argc, const char **argv)
 {
 	struct commit *one, *two;
 
@@ -107,9 +107,9 @@ int cmd_merge_base(int argc, const char **argv, const char *prefix)
 	if (!octopus && !reduce && argc < 2)
 		usage_with_options(merge_base_usage, options);
 	if (is_ancestor && (show_all | octopus | reduce))
-		die("--is-reachable cannot be used with other options");
+		die("--is-ancestor cannot be used with other options");
 	if (is_ancestor)
-		return show_is_ancestor(argc, argv);
+		return handle_is_ancestor(argc, argv);
 	if (reduce && (show_all || octopus))
 		die("--independent cannot be used with other options");
 

Re: [PATCH 2/4] merge-base: "--is-ancestor A B"

[Martin von Zweigbergk]

On Fri, Aug 31, 2012 at 10:25 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Martin von Zweigbergk <martinvonz@gmail.com> writes:
>
>>> +       if (argc != 2)
>>> +               die("--is-ancestor takes exactly two commits");
>>
>> I think git merge-base shows the usage message regardless if argc < 2,
>> so this only happens when more than two arguments are given.
>
> Yes, but it is a good discipline not to depend too much on what
> other parts of the code may have done, when you do not have to.

Yes, I definitely agree. It was more that when I saw this line and
then tried it out, I was a little surprised that it didn't tell med
"--is-ancestor takes exactly two commits" when I gave it only one. But
since few users read the code before running the command, it will
probably not be too surprising :-)

>> Maybe
>> include --is-ancestor in the usage message?
>
> I think "merge-base -h" will get this for free thanks to parseopt.

It seems not, or maybe I'm using the wrong terminology; I meant to
include it in the first part of the below.

usage: git merge-base [-a|--all] <commit> <commit>...
   or: git merge-base [-a|--all] --octopus <commit>...
   or: git merge-base --independent <commit>...

    -a, --all             output all common ancestors
    --octopus             find ancestors for a single n-way merge
    --independent         list revs not reachable from others
    --is-ancestor         is the first one ancestor of the other?


>  'git merge-base' [-a|--all] --octopus <commit>...
> +'git merge-base' --is-ancestor <commit> <commit>
>  'git merge-base' --independent <commit>...

Ah, I guess this is what I was looking for. The remainder of the patch
looks good too. Thanks.

Re: [PATCH 2/4] merge-base: "--is-ancestor A B"

[Junio C Hamano]

Martin von Zweigbergk <martinvonz@gmail.com> writes:

> On Fri, Aug 31, 2012 at 10:25 AM, Junio C Hamano <gitster@pobox.com> wrote:
> ...
>> I think "merge-base -h" will get this for free thanks to parseopt.
>
> It seems not, or maybe I'm using the wrong terminology; I meant to
> include it in the first part of the below.
>
> usage: git merge-base [-a|--all] <commit> <commit>...
>    or: git merge-base [-a|--all] --octopus <commit>...
>    or: git merge-base --independent <commit>...
>
>     -a, --all             output all common ancestors
>     --octopus             find ancestors for a single n-way merge
>     --independent         list revs not reachable from others
>     --is-ancestor         is the first one ancestor of the other?

Ahh.

As most of the modern parse-optified ones just say "git cmd <args>"
or something like that, I wasn't paying attention to the upper part.

Will amend again.  Thanks.

[PATCH 3/4] in_merge_bases(): use paint_down_to_common()

[Junio C Hamano]

With paint_down_to_common(), we can tell if "commit" is reachable
from "reference" by simply looking at its object flag, instead of
iterating over the merge bases.
---
 commit.c | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)

diff --git a/commit.c b/commit.c
index 0058fa5..d39a9e9 100644
--- a/commit.c
+++ b/commit.c
@@ -786,20 +786,17 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
  */
 int in_merge_bases(struct commit *commit, struct commit *reference)
 {
-	struct commit_list *bases, *b;
+	struct commit_list *bases;
 	int ret = 0;
 
-	bases = merge_bases_many(commit, 1, &reference);
+	if (parse_commit(commit) || parse_commit(reference))
+		return ret;
+
+	bases = paint_down_to_common(commit, 1, &reference);
+	if (commit->object.flags & PARENT2)
+		ret = 1;
 	clear_commit_marks(commit, all_flags);
 	clear_commit_marks(reference, all_flags);
-
-	for (b = bases; b; b = b->next) {
-		if (!hashcmp(commit->object.sha1, b->item->object.sha1)) {
-			ret = 1;
-			break;
-		}
-	}
-
 	free_commit_list(bases);
 	return ret;
 }
-- 
1.7.12.293.g6aeebca

[PATCH 4/4] get_merge_bases_many(): walk from many tips in parallel

[Junio C Hamano]

The get_merge_bases_many() function reduces the result returned by
the merge_bases_many() function, which is a set of possible merge
bases, by excluding commits that can be reached from other commits.
We used to do N*(N-1) traversals for this, but we can check if one
commit reaches which other (N-1) commits by a single traversal, and
repeat it for all the candidates to find the answer.

Introduce remove_redundant() helper function to do this painting; we
should be able to use it to reimplement reduce_heads() as well.
---
 commit.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 58 insertions(+), 21 deletions(-)

diff --git a/commit.c b/commit.c
index d39a9e9..2ff5061 100644
--- a/commit.c
+++ b/commit.c
@@ -692,6 +692,60 @@ struct commit_list *get_octopus_merge_bases(struct commit_list *in)
 	return ret;
 }
 
+static int remove_redundant(struct commit **array, int cnt)
+{
+	/*
+	 * Some commit in the array may be an ancestor of
+	 * another commit.  Move such commit to the end of
+	 * the array, and return the number of commits that
+	 * are independent from each other.
+	 */
+	struct commit **work;
+	unsigned char *redundant;
+	int *filled_index;
+	int i, j, filled;
+
+	work = xcalloc(cnt, sizeof(*work));
+	redundant = xcalloc(cnt, 1);
+	filled_index = xmalloc(sizeof(*filled_index) * (cnt - 1));
+
+	for (i = 0; i < cnt; i++) {
+		struct commit_list *common;
+
+		if (redundant[i])
+			continue;
+		for (j = filled = 0; j < cnt; j++) {
+			if (i == j || redundant[j])
+				continue;
+			filled_index[filled] = j;
+			work[filled++] = array[j];
+		}
+		common = paint_down_to_common(array[i], filled, work);
+		if (array[i]->object.flags & PARENT2)
+			redundant[i] = 1;
+		for (j = 0; j < filled; j++)
+			if (work[j]->object.flags & PARENT1)
+				redundant[filled_index[j]] = 1;
+		clear_commit_marks(array[i], all_flags);
+		for (j = 0; j < filled; j++)
+			clear_commit_marks(work[j], all_flags);
+		free_commit_list(common);
+	}
+
+	/* Now collect the result */
+	memcpy(work, array, sizeof(*array) * cnt);
+	for (i = filled = 0; i < cnt; i++)
+		if (!redundant[i])
+			array[filled++] = work[i];
+	for (j = filled, i = 0; i < cnt; i++)
+		if (redundant[i])
+			array[j++] = work[i];
+	free(work);
+	free(redundant);
+	free(filled_index);
+	return filled;
+}
+
 struct commit_list *get_merge_bases_many(struct commit *one,
 					 int n,
 					 struct commit **twos,
@@ -700,7 +754,7 @@ struct commit_list *get_merge_bases_many(struct commit *one,
 	struct commit_list *list;
 	struct commit **rslt;
 	struct commit_list *result;
-	int cnt, i, j;
+	int cnt, i;
 
 	result = merge_bases_many(one, n, twos);
 	for (i = 0; i < n; i++) {
@@ -731,28 +785,11 @@ struct commit_list *get_merge_bases_many(struct commit *one,
 	clear_commit_marks(one, all_flags);
 	for (i = 0; i < n; i++)
 		clear_commit_marks(twos[i], all_flags);
-	for (i = 0; i < cnt - 1; i++) {
-		for (j = i+1; j < cnt; j++) {
-			if (!rslt[i] || !rslt[j])
-				continue;
-			result = merge_bases_many(rslt[i], 1, &rslt[j]);
-			clear_commit_marks(rslt[i], all_flags);
-			clear_commit_marks(rslt[j], all_flags);
-			for (list = result; list; list = list->next) {
-				if (rslt[i] == list->item)
-					rslt[i] = NULL;
-				if (rslt[j] == list->item)
-					rslt[j] = NULL;
-			}
-		}
-	}
 
-	/* Surviving ones in rslt[] are the independent results */
+	cnt = remove_redundant(rslt, cnt);
 	result = NULL;
-	for (i = 0; i < cnt; i++) {
-		if (rslt[i])
-			commit_list_insert_by_date(rslt[i], &result);
-	}
+	for (i = 0; i < cnt; i++)
+		commit_list_insert_by_date(rslt[i], &result);
 	free(rslt);
 	return result;
 }
-- 
1.7.12.293.g6aeebca