[PATCH 1/2] Move old index entry removal from "unpack_trees()" into the individual functions

[PATCH 1/2] Move old index entry removal from "unpack_trees()" into the individual functions

[Linus Torvalds]

This makes no changes to current code, but it allows the individual merge 
functions to decide what to do about the old entry.  They might decide to 
update it in place, rather than force them to always delete and re-add it.
    
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This commit on purpose does *not* change any behaviour, it just lays the 
groundwork for the next patch, which optimizes the hell out of the two 
common cases.

 unpack-trees.c |   29 +++++++++++++++++++++++------
 unpack-trees.h |   11 ++++++-----
 2 files changed, 29 insertions(+), 11 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index 5d1ffd1..7fed5d2 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -58,10 +58,17 @@ static int entcmp(const char *name1, int dir1, const char *name2, int dir2)
 	return ret;
 }
 
+static inline void remove_entry(int remove)
+{
+	if (remove >= 0)
+		remove_cache_entry_at(remove);
+}
+
 static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 			    const char *base, struct unpack_trees_options *o,
 			    struct tree_entry_list *df_conflict_list)
 {
+	int remove;
 	int baselen = strlen(base);
 	int src_size = len + 1;
 	int i_stk = i_stk;
@@ -145,10 +152,11 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 
 		subposns = xcalloc(len, sizeof(struct tree_list_entry *));
 
+		remove = -1;
 		if (cache_name && !strcmp(cache_name, first)) {
 			any_files = 1;
 			src[0] = active_cache[o->pos];
-			remove_cache_entry_at(o->pos);
+			remove = o->pos;
 		}
 
 		for (i = 0; i < len; i++) {
@@ -214,13 +222,14 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 						printf("\n");
 				}
 #endif
-				ret = o->fn(src, o);
+				ret = o->fn(src, o, remove);
 
 #if DBRT_DEBUG > 1
 				printf("Added %d entries\n", ret);
 #endif
 				o->pos += ret;
 			} else {
+				remove_entry(remove);
 				for (i = 0; i < src_size; i++) {
 					if (src[i]) {
 						add_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);
@@ -641,7 +650,8 @@ static void show_stage_entry(FILE *o,
 #endif
 
 int threeway_merge(struct cache_entry **stages,
-		struct unpack_trees_options *o)
+		struct unpack_trees_options *o,
+		int remove)
 {
 	struct cache_entry *index;
 	struct cache_entry *head;
@@ -657,6 +667,7 @@ int threeway_merge(struct cache_entry **stages,
 	int no_anc_exists = 1;
 	int i;
 
+	remove_entry(remove);		
 	for (i = 1; i < o->head_idx; i++) {
 		if (!stages[i] || stages[i] == o->df_conflict_entry)
 			any_anc_missing = 1;
@@ -809,12 +820,14 @@ int threeway_merge(struct cache_entry **stages,
  *
  */
 int twoway_merge(struct cache_entry **src,
-		struct unpack_trees_options *o)
+		struct unpack_trees_options *o,
+		int remove)
 {
 	struct cache_entry *current = src[0];
 	struct cache_entry *oldtree = src[1];
 	struct cache_entry *newtree = src[2];
 
+	remove_entry(remove);
 	if (o->merge_size != 2)
 		return error("Cannot do a twoway merge of %d trees",
 			     o->merge_size);
@@ -868,11 +881,13 @@ int twoway_merge(struct cache_entry **src,
  * stage0 does not have anything there.
  */
 int bind_merge(struct cache_entry **src,
-		struct unpack_trees_options *o)
+		struct unpack_trees_options *o,
+		int remove)
 {
 	struct cache_entry *old = src[0];
 	struct cache_entry *a = src[1];
 
+	remove_entry(remove);
 	if (o->merge_size != 1)
 		return error("Cannot do a bind merge of %d trees\n",
 			     o->merge_size);
@@ -891,11 +906,13 @@ int bind_merge(struct cache_entry **src,
  * - take the stat information from stage0, take the data from stage1
  */
 int oneway_merge(struct cache_entry **src,
-		struct unpack_trees_options *o)
+		struct unpack_trees_options *o,
+		int remove)
 {
 	struct cache_entry *old = src[0];
 	struct cache_entry *a = src[1];
 
+	remove_entry(remove);
 	if (o->merge_size != 1)
 		return error("Cannot do a oneway merge of %d trees",
 			     o->merge_size);
diff --git a/unpack-trees.h b/unpack-trees.h
index 9cd39a2..5517faa 100644
--- a/unpack-trees.h
+++ b/unpack-trees.h
@@ -4,7 +4,8 @@
 struct unpack_trees_options;
 
 typedef int (*merge_fn_t)(struct cache_entry **src,
-		struct unpack_trees_options *options);
+		struct unpack_trees_options *options,
+		int remove);
 
 struct unpack_trees_options {
 	int reset;
@@ -29,9 +30,9 @@ struct unpack_trees_options {
 extern int unpack_trees(unsigned n, struct tree_desc *t,
 		struct unpack_trees_options *options);
 
-int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o);
-int twoway_merge(struct cache_entry **src, struct unpack_trees_options *o);
-int bind_merge(struct cache_entry **src, struct unpack_trees_options *o);
-int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o);
+int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o, int);
+int twoway_merge(struct cache_entry **src, struct unpack_trees_options *o, int);
+int bind_merge(struct cache_entry **src, struct unpack_trees_options *o, int);
+int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o, int);
 
 #endif

[PATCH 2/2] Optimize the common cases of git-read-tree

[Linus Torvalds]

This optimizes bind_merge() and oneway_merge() to not unnecessarily
remove and re-add the old index entries when they can just get replaced
by updated ones.

This makes these operations much faster for large trees (where "large"
is in the 50,000+ file range), because we don't unnecessarily move index
entries around in the index array all the time.

Using the "bummer" tree (a test-tree with 100,000 files) we get:

Before:
	[torvalds@woody bummer]$ time git commit -m"Change one file" 50/500
	real    0m9.470s
	user    0m8.729s
	sys     0m0.476s

After:
	[torvalds@woody bummer]$ time git commit -m"Change one file" 50/500
	real    0m1.173s
	user    0m0.720s
	sys     0m0.452s

so for large trees this is easily very noticeable indeed.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Btw, these patches are based on top of my "speedup" branch, which includes 
the previous changes (including the change to use "struct tree_desc" in 
unpacking). However, apart from some context lines, they really should 
work fine on top of current master too, so if you don't want to take the 
"struct tree_desc" one, these patches should work fine even without it.

Also: this same "don't remove unnecessarily" case could (and should) be 
done for the two-way and three-way cases too, and it should be trivial to 
do. However, I didn't bother, since it wasn't the particular timings I was 
worried about. 

But doing that should help branch switching a lot, so I may send a "patch 
3/2" soon.

 unpack-trees.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index 7fed5d2..b4e2618 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -887,7 +887,6 @@ int bind_merge(struct cache_entry **src,
 	struct cache_entry *old = src[0];
 	struct cache_entry *a = src[1];
 
-	remove_entry(remove);
 	if (o->merge_size != 1)
 		return error("Cannot do a bind merge of %d trees\n",
 			     o->merge_size);
@@ -912,13 +911,14 @@ int oneway_merge(struct cache_entry **src,
 	struct cache_entry *old = src[0];
 	struct cache_entry *a = src[1];
 
-	remove_entry(remove);
 	if (o->merge_size != 1)
 		return error("Cannot do a oneway merge of %d trees",
 			     o->merge_size);
 
-	if (!a)
+	if (!a) {
+		remove_entry(remove);
 		return deleted_entry(old, old, o);
+	}
 	if (old && same(old, a)) {
 		if (o->reset) {
 			struct stat st;

[PATCH 3/2] Optimize the two-way merge of git-read-tree too

[Linus Torvalds]

This trivially optimizes the two-way merge case of git-read-tree too, 
which affects switching branches.

When you have tons and tons of files in your repository, but there are 
only small differences in the branches (maybe just a couple of files 
changed), the biggest cost of the branch switching was actually just the 
index calculations.

This fixes it (timings for switching between the "testing" and "master" 
branches in the 100,000 file testing-repo-from-hell, where the branches 
only differ in one small file).

Before:
	[torvalds@woody bummer]$ time git checkout master
	real    0m9.919s
	user    0m8.461s
	sys     0m0.264s

After:
	[torvalds@woody bummer]$ time git checkout testing
	real    0m0.576s
	user    0m0.348s
	sys     0m0.228s

so it's easily an order of magnitude different.

This concludes the series. I think we could/should do the three-way merge 
too (to speed up merges), but I'm lazy. Somebody else can do it.

The rule is very simple: you need to remove the old entry if:
 - you want to remove the file entirely
 - you replace it with a "merge conflict" entry (ie a non-stage-0 entry)

and you can avoid removing it if you either

 - keep the old one
 - or resolve it to a new one.

and these rules should all be valid for the three-way case too.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
commit b8d8d6aa12a3ae7e2f7a8cb008413b780e1152ce
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Fri Aug 10 12:13:41 2007 -0700

    Optimize the common cases of git-read-tree
    
    This optimizes bind_merge() and oneway_merge() to not unnecessarily
    remove and re-add the old index entries when they can just get replaced
    by updated ones.
    
    This makes these operations much faster for large trees (where "large"
    is in the 50,000+ file range), because we don't unnecessarily move index
    entries around in the index array all the time.
    
    Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 unpack-trees.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index b4e2618..810816e 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -827,7 +827,6 @@ int twoway_merge(struct cache_entry **src,
 	struct cache_entry *oldtree = src[1];
 	struct cache_entry *newtree = src[2];
 
-	remove_entry(remove);
 	if (o->merge_size != 2)
 		return error("Cannot do a twoway merge of %d trees",
 			     o->merge_size);
@@ -850,6 +849,7 @@ int twoway_merge(struct cache_entry **src,
 		}
 		else if (oldtree && !newtree && same(current, oldtree)) {
 			/* 10 or 11 */
+			remove_entry(remove);
 			return deleted_entry(oldtree, current, o);
 		}
 		else if (oldtree && newtree &&
@@ -859,6 +859,7 @@ int twoway_merge(struct cache_entry **src,
 		}
 		else {
 			/* all other failures */
+			remove_entry(remove);
 			if (oldtree)
 				reject_merge(oldtree);
 			if (current)
@@ -870,8 +871,8 @@ int twoway_merge(struct cache_entry **src,
 	}
 	else if (newtree)
 		return merged_entry(newtree, current, o);
-	else
-		return deleted_entry(oldtree, current, o);
+	remove_entry(remove);
+	return deleted_entry(oldtree, current, o);
 }
 
 /*

Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too

[Linus Torvalds]

On Fri, 10 Aug 2007, Linus Torvalds wrote:
> 
> This trivially optimizes the two-way merge case of git-read-tree too, 
> which affects switching branches.

Side note, if this wasn't obvious: this series of three patches (four, if 
you count the one in this email) obviates the need for Junio's hacky fix 
from yesterday that removed the "-i -m" flags from "git read-tree" in 
git-commit.sh, and made builtin-read-tree sometimes use the "read_tree()" 
function.

Now "unpack_trees()" is just fast enough that we don't need to avoid it 
(although it's probably still a good idea to eventually convert it to use 
the traverse_trees() infrastructure some day - just to avoid having 
extraneous tree traversal functions).

And as mentioned, the three-way case *should* be as trivial as the 
following. It passes all the tests, and I verified that a conflicting 
merge in the 100,000 file horror-case merged correctly (with the conflict 
markers) in 0.687 seconds with this, so it works, but I'm lazy and 
somebody else should double-check it.

(Again - *without* this patch, the merge took 8.355 seconds, so this patch 
really does make a huge difference for merge performance with lots and 
lots of files, and we're not talking percentages, we're talking 
orders-of-magnitude differences!)

		Linus

---
 unpack-trees.c |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index 810816e..ccfeb6e 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -667,7 +667,6 @@ int threeway_merge(struct cache_entry **stages,
 	int no_anc_exists = 1;
 	int i;
 
-	remove_entry(remove);		
 	for (i = 1; i < o->head_idx; i++) {
 		if (!stages[i] || stages[i] == o->df_conflict_entry)
 			any_anc_missing = 1;
@@ -730,8 +729,10 @@ int threeway_merge(struct cache_entry **stages,
 	}
 
 	/* #1 */
-	if (!head && !remote && any_anc_missing)
+	if (!head && !remote && any_anc_missing) {
+		remove_entry(remove);
 		return 0;
+	}
 
 	/* Under the new "aggressive" rule, we resolve mostly trivial
 	 * cases that we historically had git-merge-one-file resolve.
@@ -763,6 +764,7 @@ int threeway_merge(struct cache_entry **stages,
 		if ((head_deleted && remote_deleted) ||
 		    (head_deleted && remote && remote_match) ||
 		    (remote_deleted && head && head_match)) {
+			remove_entry(remove);
 			if (index)
 				return deleted_entry(index, index, o);
 			else if (ce && !head_deleted)
@@ -785,6 +787,7 @@ int threeway_merge(struct cache_entry **stages,
 		verify_uptodate(index, o);
 	}
 
+	remove_entry(remove);
 	o->nontrivial_merge = 1;
 
 	/* #2, #3, #4, #6, #7, #9, #10, #11. */

Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too

[Junio C Hamano]

Looks obvious, mostly thanks to the clean rule that you outlined
in [PATCH 2/2] description.

Thanks.

Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> And as mentioned, the three-way case *should* be as trivial as the 
> following. It passes all the tests, and I verified that a conflicting 
> merge in the 100,000 file horror-case merged correctly (with the conflict 
> markers) in 0.687 seconds with this, so it works, but I'm lazy and 
> somebody else should double-check it.
>
> (Again - *without* this patch, the merge took 8.355 seconds, so this patch 
> really does make a huge difference for merge performance with lots and 
> lots of files, and we're not talking percentages, we're talking 
> orders-of-magnitude differences!)

Hmph, this might make what I was hoping to find time to do more
or less unnecessary.

But here it is anyway.

I wanted to speed up the three-way merges.  The assumption is
that when you do a merge, you are not in the middle of your own
messy work.  It is either while you are in a merge binge,
pulling from one subsystem lieutenant after another, or perhaps
applying patchbombs from people.  In either case, you would
start your merge with a clean index that >99% matches the HEAD,
after writing your index out as a tree.

Then, the new 3-way read-tree (or unpack_trees) would go like
this.

First, we scan the index and find locally modified paths;
invalidate cache-tree by calling cache_tree_invalidate_path()
for such paths.  The expectation is that you will still have
largely usable cache-tree after this step.

The main part of the merge will be done by using tree_desc based
traversal that walks over three (ancestor, mine and theirs)
trees, instead of the current unpack_trees() that iterates
mainly over the index entries.

(A) The three trees all may have a subtree at the same path, or
    the one that does not have a tree where others have does not
    have a blob at the path either (i.e. the subtree is missing
    from the tree without a D/F conflict).  If the usual 3-way
    tree level merge rule (one side changes while the other side
    does not do anything, or both sides change to the same) can
    be applied, and if the cache tree entry for that subtree is
    valid and matches our tree, then...

    - we know the working tree for that entire subdirectory is
      also clean because of the earlier invalidation;

    - we can simply follow the tree level merge without ever
      looking at individual paths contained in the subtree.

(B) If the precondition of (A) does not hold, we recurse into
    the subtree, and perform per-path 3-way merge, like the
    current unpack_trees() does.

If your merge does not involve anything in large subdirectories,
e.g., include/, arch/, or drivers/, this would allow you to skip
quite a lot of per-path merge computation by doing comparison of
four (tree entries and cache-tree) tree object names (the three
subdirectories have about 6k paths each, so this could be a huge
win).

Another optimization I was hoping to do was "git diff --cached",
which is unrelated to the recent change to use read_tree().
Instead of reading the tree into the stage #1 of the same index,
we could walk the tree and skip the subtree whose cache-tree
matches the entry from the tree.  This would have the same scale
of performance improvement opportunity.

Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too

[Linus Torvalds]

On Sat, 11 Aug 2007, Junio C Hamano wrote:
> 
> Then, the new 3-way read-tree (or unpack_trees) would go like
> this.
> 
> First, we scan the index and find locally modified paths;
> invalidate cache-tree by calling cache_tree_invalidate_path()
> for such paths.  The expectation is that you will still have
> largely usable cache-tree after this step.
> 
> The main part of the merge will be done by using tree_desc based
> traversal that walks over three (ancestor, mine and theirs)
> trees, instead of the current unpack_trees() that iterates
> mainly over the index entries.
> 
> (A) The three trees all may have a subtree at the same path, or
>     the one that does not have a tree where others have does not
>     have a blob at the path either (i.e. the subtree is missing
>     from the tree without a D/F conflict).  If the usual 3-way
>     tree level merge rule (one side changes while the other side
>     does not do anything, or both sides change to the same) can
>     be applied, and if the cache tree entry for that subtree is
>     valid and matches our tree, then...
> 
>     - we know the working tree for that entire subdirectory is
>       also clean because of the earlier invalidation;
> 
>     - we can simply follow the tree level merge without ever
>       looking at individual paths contained in the subtree.
> 
> (B) If the precondition of (A) does not hold, we recurse into
>     the subtree, and perform per-path 3-way merge, like the
>     current unpack_trees() does.

I'd love to see this, because it would likely speed up merging of really 
big trees by a huge amount, and because I think it's fundamentally the 
"right thing(tm)" to do.

That said, right now we do so well that it's almost not interesting. The 
kernel tree is so small as to merge in basically zero time even when you 
do per-file merges, and generatign the diffstat is almost always the 
biggest component of the merge by far.

But yes, for bigger trees, and just because it's the right thing to do 
considering the data structures we have, we really should plan on doing 
that some day. I think that with the current optimizations (and at least 
with current hardware - old hw might change the equation), based on my 
timings on the "bummer" tree, are fine at _least_ to 100,000 files. But if 
we're talking about slower hardware, or many more files than that, we 
should _definitely_ eventually do the tree-based optimizations.

> Another optimization I was hoping to do was "git diff --cached",
> which is unrelated to the recent change to use read_tree().

Yeah. "git diff" is just about the most performance-critical one. That 
said, the "--cached" case is likely the least used one, and any time you 
don't use that, you end up having to lstat() the files anyway, so you 
cannot do the tree-based optimizations ;^p

But it would help "git status", I think (which needs to do both --cached 
and the normal one).

		Linus