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

Subsystems: the rest

DORMANTno replies

4 messages, 1 author, 2016-06-15 · open the first message on its own page

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

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:43:28

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

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:43:28

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

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:43:28

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 [off-list ref]
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 [off-list ref]
---
 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

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: 2016-06-15 22:43:28

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. */

`h`	back out one level
`j`	next message in thread
`k`	previous message in thread
`l`	drill in
`Esc`	close help / fold thread tree
`?`	toggle this help