[PATCH 0/8] fetch.c optimizations

Hello!

I have noticed that git-*-fetch now uses much more CPU than it was
before the modifications to fix recovery after interrupted fetch.
Here is a series of small patches which fix the problems which I have
found (some of the fixes give pretty impressive results, like a 14x
decrease of CPU time); as a positive side effect, fetch.c becomes
slightly smaller and hopefully simpler than before.

-- 
Sergey Vlasov

If the SEEN flag was not set, the TO_SCAN flag cannot be set,
therefore testing it is pointless.

---

 fetch.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

6f33848a2f4aecd061d9499dfc88824235572695

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -136,8 +136,6 @@ static int process(struct object *obj)
 	if (has_sha1_file(obj->sha1)) {
 		parse_object(obj->sha1);
 		/* We already have it, so we should scan it now. */
-		if (obj->flags & TO_SCAN)
-			return 0;
 		obj->flags |= TO_SCAN;
 	} else {
 		if (obj->flags & COMPLETE)

The TO_FETCH flag also became redundant after adding the SEEN flag -
it was set and checked in process() to prevent adding the same object
to process_queue multiple times, but now SEEN guards against this.

---

 fetch.c |    4 +---
 1 files changed, 1 insertions(+), 3 deletions(-)

92ef6ee593199b80e01ebe93a48c03508941a340

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -55,7 +55,6 @@ static int process_tree(struct tree *tre
 }
 
 #define COMPLETE	1U
-#define TO_FETCH	2U
 #define TO_SCAN		4U
 #define SEEN		16U
 

@@ -144,11 +143,10 @@ static int process(struct object *obj)
 		obj->flags |= TO_SCAN;
 		return 0;
 	}
-	if (obj->flags & (COMPLETE | TO_FETCH))
+	if (obj->flags & COMPLETE)
 		return 0;
 	object_list_insert(obj, process_queue_end);
 	process_queue_end = &(*process_queue_end)->next;
-	obj->flags |= TO_FETCH;
 
 	prefetch(obj->sha1);
 		

It does not matter if we call prefetch() or set the TO_SCAN flag before
or after adding the object to process_queue.  However, doing it before
object_list_insert() allows us to kill 3 lines of duplicated code.

---

 fetch.c |   13 +++++--------
 1 files changed, 5 insertions(+), 8 deletions(-)

dc255341f62596b0808c383ef8f3eff044be5515

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -138,18 +138,15 @@ static int process(struct object *obj)
 		/* We already have it, so we should scan it now. */
 		if (obj->flags & TO_SCAN)
 			return 0;
-		object_list_insert(obj, process_queue_end);
-		process_queue_end = &(*process_queue_end)->next;
 		obj->flags |= TO_SCAN;
-		return 0;
+	} else {
+		if (obj->flags & COMPLETE)
+			return 0;
+		prefetch(obj->sha1);
 	}
-	if (obj->flags & COMPLETE)
-		return 0;
+		
 	object_list_insert(obj, process_queue_end);
 	process_queue_end = &(*process_queue_end)->next;
-
-	prefetch(obj->sha1);
-		
 	return 0;
 }
 

In all places where process() is called except the one in pull() (which
is executed only once) the pointer to the object is already available,
so pass it as the argument to process() instead of sha1 and avoid an
unneeded call to lookup_object_type().

---

 fetch.c |   23 ++++++++++-------------
 1 files changed, 10 insertions(+), 13 deletions(-)

3a0ec5d22a2f9828bebae9b13e5848291685e4c5

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -33,7 +33,7 @@ static void report_missing(const char *w
 		what, missing_hex, sha1_to_hex(current_commit_sha1));
 }
 
-static int process(unsigned char *sha1, const char *type);
+static int process(struct object *obj);
 
 static int process_tree(struct tree *tree)
 {

@@ -46,8 +46,7 @@ static int process_tree(struct tree *tre
 	tree->entries = NULL;
 	while (entry) {
 		struct tree_entry_list *next = entry->next;
-		if (process(entry->item.any->sha1,
-			    entry->directory ? tree_type : blob_type))
+		if (process(entry->item.any))
 			return -1;
 		free(entry);
 		entry = next;

@@ -79,7 +78,7 @@ static int process_commit(struct commit 
 	pull_say("walk %s\n", sha1_to_hex(commit->object.sha1));
 
 	if (get_tree) {
-		if (process(commit->tree->object.sha1, tree_type))
+		if (process(&commit->tree->object))
 			return -1;
 		if (!get_all)
 			get_tree = 0;

@@ -87,7 +86,7 @@ static int process_commit(struct commit 
 	if (get_history) {
 		struct commit_list *parents = commit->parents;
 		for (; parents; parents = parents->next) {
-			if (process(parents->item->object.sha1, commit_type))
+			if (process(&parents->item->object))
 				return -1;
 		}
 	}

@@ -98,7 +97,7 @@ static int process_tag(struct tag *tag)
 {
 	if (parse_tag(tag))
 		return -1;
-	return process(tag->tagged->sha1, NULL);
+	return process(tag->tagged);
 }
 
 static struct object_list *process_queue = NULL;

@@ -133,12 +132,10 @@ static int process_object(struct object 
 		     obj->type, sha1_to_hex(obj->sha1));
 }
 
-static int process(unsigned char *sha1, const char *type)
+static int process(struct object *obj)
 {
-	struct object *obj = lookup_object_type(sha1, type);
-
-	if (has_sha1_file(sha1)) {
-		parse_object(sha1);
+	if (has_sha1_file(obj->sha1)) {
+		parse_object(obj->sha1);
 		/* We already have it, so we should scan it now. */
 		if (obj->flags & (SCANNED | TO_SCAN))
 			return 0;

@@ -153,7 +150,7 @@ static int process(unsigned char *sha1, 
 	process_queue_end = &(*process_queue_end)->next;
 	obj->flags |= TO_FETCH;
 
-	prefetch(sha1);
+	prefetch(obj->sha1);
 		
 	return 0;
 }

@@ -228,7 +225,7 @@ int pull(char *target)
 	if (interpret_target(target, sha1))
 		return error("Could not interpret %s as something to pull",
 			     target);
-	if (process(sha1, NULL))
+	if (process(lookup_unknown_object(sha1)))
 		return -1;
 	if (loop())
 		return -1;

After adding the SEEN flag, the SCANNED flag became obviously
redundant - each object can get into process_queue through process()
only once, and therefore multiple calls to process_object() for the
same object are not possible.

---

 fetch.c |    7 +------
 1 files changed, 1 insertions(+), 6 deletions(-)

320120295a258c4b66c43ee3b4ff6af962333950

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -57,7 +57,6 @@ static int process_tree(struct tree *tre
 #define COMPLETE	1U
 #define TO_FETCH	2U
 #define TO_SCAN		4U
-#define SCANNED		8U
 #define SEEN		16U
 
 static struct commit_list *complete = NULL;

@@ -106,10 +105,6 @@ static struct object_list **process_queu
 
 static int process_object(struct object *obj)
 {
-	if (obj->flags & SCANNED)
-		return 0;
-	obj->flags |= SCANNED;
-
 	if (obj->type == commit_type) {
 		if (process_commit((struct commit *)obj))
 			return -1;

@@ -142,7 +137,7 @@ static int process(struct object *obj)
 	if (has_sha1_file(obj->sha1)) {
 		parse_object(obj->sha1);
 		/* We already have it, so we should scan it now. */
-		if (obj->flags & (SCANNED | TO_SCAN))
+		if (obj->flags & TO_SCAN)
 			return 0;
 		object_list_insert(obj, process_queue_end);
 		process_queue_end = &(*process_queue_end)->next;

The process() function is very often called multiple times for the
same object (because lots of trees refer to the same blobs), but did
not have a fast check for this, therefore a lot of useless calls to
has_sha1_file() and parse_object() were made before discovering that
nothing needs to be done.

This patch adds the SEEN flag which is used in process() to make it
look at each object only once.  When testing git-local-fetch on the
repository of GIT, this gives a 14x improvement in CPU usage (mainly
because the redundant calls to parse_object() are now avoided -
parse_object() always unpacks and parses the object data, even if it
was already parsed before).

---

 fetch.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)

03abc6806a4433807bc21cf3f1aac2528c655c8f

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -58,6 +58,7 @@ static int process_tree(struct tree *tre
 #define TO_FETCH	2U
 #define TO_SCAN		4U
 #define SCANNED		8U
+#define SEEN		16U
 
 static struct commit_list *complete = NULL;
 

@@ -134,6 +135,10 @@ static int process_object(struct object 
 
 static int process(struct object *obj)
 {
+	if (obj->flags & SEEN)
+		return 0;
+	obj->flags |= SEEN;
+
 	if (has_sha1_file(obj->sha1)) {
 		parse_object(obj->sha1);
 		/* We already have it, so we should scan it now. */

Remove holes left after deleting flags, and use shifts to emphasize
that flags are single bits.

---

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

42e3d6ef7c0a4eda60032815a36039240dc5cd0b

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -54,9 +54,9 @@ static int process_tree(struct tree *tre
 	return 0;
 }
 
-#define COMPLETE	1U
-#define TO_SCAN		4U
-#define SEEN		16U
+#define COMPLETE	(1U << 0)
+#define SEEN		(1U << 1)
+#define TO_SCAN		(1U << 2)
 
 static struct commit_list *complete = NULL;
 

The call to parse_object() in process() is not actually needed - if
the object type is unknown, parse_object() will be called by loop();
if the type is known, the object will be parsed by the appropriate
process_*() function.

After this change blobs which exist locally are no longer parsed,
which gives about 2x CPU usage improvement; the downside is that there
will be no warnings for existing corrupted blobs, but detecting such
corruption is the job of git-fsck-objects, not the fetch programs.
Newly fetched objects are still checked for corruption in http-fetch.c
and ssh-fetch.c (local-fetch.c does not seem to do it, but the removed
parse_object() call would not be reached for new objects anyway).

---

 fetch.c |    1 -
 1 files changed, 0 insertions(+), 1 deletions(-)

b8a4d51743787be17f9572dce2eb2f4040ac241b

diff --git a/fetch.c b/fetch.c
--- a/fetch.c
+++ b/fetch.c

@@ -134,7 +134,6 @@ static int process(struct object *obj)
 	obj->flags |= SEEN;
 
 	if (has_sha1_file(obj->sha1)) {
-		parse_object(obj->sha1);
 		/* We already have it, so we should scan it now. */
 		obj->flags |= TO_SCAN;
 	} else {

Sergey Vlasov [off-list ref] writes:

In all places where process() is called except the one in pull() (which
is executed only once) the pointer to the object is already available,
so pass it as the argument to process() instead of sha1 and avoid an
unneeded call to lookup_object_type().

Agreed, except we probably would want to pass the expected type
to process() so that we can make sure the object is of that type,
perhaps?

Having said that, I am really happy that you seem to have fixed
it a lot better than my previous attempt, after which I was
really dissapointed that 'git clone' was still unusablly slow,
just walking commits in huge packs.

Thanks.

On Wed, 21 Sep 2005, Sergey Vlasov wrote:

Hello!

I have noticed that git-*-fetch now uses much more CPU than it was
before the modifications to fix recovery after interrupted fetch.
Here is a series of small patches which fix the problems which I have
found (some of the fixes give pretty impressive results, like a 14x
decrease of CPU time); as a positive side effect, fetch.c becomes
slightly smaller and hopefully simpler than before.

These all look like good changes. It would also be worth doing some 
optimization in the library, like making parse_object just return the 
object if we already have it.

	-Daniel
*This .sig left intentionally blank*

On Wed, Sep 21, 2005 at 12:45:13PM -0700, Junio C Hamano wrote:

Sergey Vlasov [off-list ref] writes:

quoted

In all places where process() is called except the one in pull() (which
is executed only once) the pointer to the object is already available,
so pass it as the argument to process() instead of sha1 and avoid an
unneeded call to lookup_object_type().

Agreed, except we probably would want to pass the expected type
to process() so that we can make sure the object is of that type,
perhaps?

This is not needed - all parse_*_buffer() functions, which fill in
pointers to referenced objects, specify required types themselves by
using lookup_commit(), lookup_tree(), etc.; even parse_tag_buffer()
uses lookup_object_type().

The only way to get a "struct object" with an unspecified type is by
calling lookup_unknown_object() (or lookup_object_type() with NULL
type) - grep shows than nothing in GIT does this, except the pull()
function in fetch.c (which obviously does not know type of the object
to be fetched in advance).