[PATCH] read-tree --aggressive

From: Junio C Hamano <junkio@cox.net>
Date: Feb 4, 2006, 07:31 UTC
Message-ID: <7v8xsr60n2.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <20060131213314.GA32131@ebar091.ebar.dtu.dk>

"Peter Eriksen" <s022018@student.dtu.dk> writes:

Show 7 quoted lines

> In connection with Ian Molton's question about merge have I played a
> little with 'git merge' on the kernel sources.  What I find is that a
> merge can take quite some time, but I'm not sure where that time exactly
> goes to.  Here are the times I got:
>
> Recursive (default):  4m22.282s
> Resolve (-s resolve): 3m23.548s

In your sample script, you do not disable the post-merge diff, which is typically one of the most expensive part in the whole merge, and I am wondering how fast a machine you are using to get 4 minutes. The post-merge diff is generated by piping the output of 'diff-tree -M' to 'apply --stat --summary', and that step alone takes about 12 minutes wallclock time on my box X-<.

Since my box is not as fast as yours, I've eliminated the post-merge diff step and tried your final merge step like this:

	$ time git merge --no-summary -s resolve \
            'Merging happily' HEAD v2.6.15 >/dev/null

and got this:

        real	2m15.737s
        user	1m43.320s
        sys	0m26.690s

With the attached patch, the most expensive part, which is the repeated invocation of git-merge-one-file to remove many deleted paths, is eliminated. The result is this.

        real	0m20.311s
        user	0m15.780s
        sys	0m4.150s

This patch would not help recursive strategy, though. Calling read-tree with --aggressive flag essentially disables the benefit we would expect to get from it -- rename detection.

-- >8 -- A new flag --aggressive resolves what we traditionally resolved with external git-merge-one-file inside index while read-tree 3-way merge works.

git-merge-octopus and git-merge-resolve use this flag before running git-merge-index with git-merge-one-file.

Signed-off-by: Junio C Hamano <junkio@cox.net>

---

 git-merge-octopus.sh |    2 +-
 git-merge-resolve.sh |    2 +-
 read-tree.c          |   32 ++++++++++++++++++++++++++++++++
 3 files changed, 34 insertions(+), 2 deletions(-)

2a4bb6bc618bdad6529d9ffe361bc8b7dd28a56c

diff --git a/git-merge-octopus.sh b/git-merge-octopus.sh
index eb74f96..eb3f473 100755
--- a/git-merge-octopus.sh
+++ b/git-merge-octopus.sh
@@ -90,7 +90,7 @@ do
 	NON_FF_MERGE=1
 
 	echo "Trying simple merge with $SHA1"
-	git-read-tree -u -m $common $MRT $SHA1 || exit 2
+	git-read-tree -u -m --aggressive  $common $MRT $SHA1 || exit 2
 	next=$(git-write-tree 2>/dev/null)
 	if test $? -ne 0
 	then
diff --git a/git-merge-resolve.sh b/git-merge-resolve.sh
index 966e81f..0a8ef21 100755
--- a/git-merge-resolve.sh
+++ b/git-merge-resolve.sh
@@ -38,7 +38,7 @@ then
 fi
 
 git-update-index --refresh 2>/dev/null
-git-read-tree -u -m $bases $head $remotes || exit 2
+git-read-tree -u -m --aggressive $bases $head $remotes || exit 2
 echo "Trying simple merge."
 if result_tree=$(git-write-tree  2>/dev/null)
 then
diff --git a/read-tree.c b/read-tree.c
index a46c6fe..5580f15 100644
--- a/read-tree.c
+++ b/read-tree.c
@@ -15,6 +15,7 @@ static int update = 0;
 static int index_only = 0;
 static int nontrivial_merge = 0;
 static int trivial_merges_only = 0;
+static int aggressive = 0;
 
 static int head_idx = -1;
 static int merge_size = 0;
@@ -424,11 +425,14 @@ static int threeway_merge(struct cache_e
 	int df_conflict_remote = 0;
 
 	int any_anc_missing = 0;
+	int no_anc_exists = 1;
 	int i;
 
 	for (i = 1; i < head_idx; i++) {
 		if (!stages[i])
 			any_anc_missing = 1;
+		else
+			no_anc_exists = 0;
 	}
 
 	index = stages[0];
@@ -489,6 +493,29 @@ static int threeway_merge(struct cache_e
 	if (!head && !remote && any_anc_missing)
 		return 0;
 
+	/* Under the new "aggressive" rule, we resolve mostly trivial
+	 * cases that we historically had git-merge-one-file resolve.
+	 */
+	if (aggressive) {
+		int head_deleted = !head && !df_conflict_head;
+		int remote_deleted = !remote && !df_conflict_remote;
+		/*
+		 * Deleted in both.
+		 * Deleted in one and unchanged in the other.
+		 */
+		if ((head_deleted && remote_deleted) ||
+		    (head_deleted && remote && remote_match) ||
+		    (remote_deleted && head && head_match))
+			return 0;
+
+		/*
+		 * Added in both, identically.
+		 */
+		if (no_anc_exists && head && remote && same(head, remote))
+			return merged_entry(head, index);
+
+	}
+
 	/* Below are "no merge" cases, which require that the index be
 	 * up-to-date to avoid the files getting overwritten with
 	 * conflict resolution files. 
@@ -677,6 +704,11 @@ int main(int argc, char **argv)
 			continue;
 		}
 
+		if (!strcmp(arg, "--aggressive")) {
+			aggressive = 1;
+			continue;
+		}
+
 		/* "-m" stands for "merge", meaning we start in stage 1 */
 		if (!strcmp(arg, "-m")) {
 			if (stage || merge)

-- 
1.1.6.ge2129