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

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Aug 10, 2007, 19:21 UTC
Message-ID: <alpine.LFD.0.999.0708101216000.30176@woody.linux-foundation.org>
In-Reply-To: <alpine.LFD.0.999.0708101213560.30176@woody.linux-foundation.org>

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;