[PATCH 0/8] fetch.c optimizations

[PATCH 0/8] fetch.c optimizations

[Sergey Vlasov]

[-- Attachment #1: Type: text/plain, Size: 427 bytes --]

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

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[PATCH 1/8] fetch.c: Remove useless lookup_object_type() call in process()

[Sergey Vlasov]

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;

[PATCH 2/8] fetch.c: Make process() look at each object only once

[Sergey Vlasov]

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

[PATCH 3/8] fetch.c: Remove redundant SCANNED flag

[Sergey Vlasov]

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;

[PATCH 4/8] fetch.c: Remove redundant TO_FETCH flag

[Sergey Vlasov]

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);
 		

[PATCH 5/8] fetch.c: Remove some duplicated code in process()

[Sergey Vlasov]

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;
 }
 

[PATCH 6/8] fetch.c: Remove redundant test of TO_SCAN in process()

[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)

[PATCH 7/8] fetch.c: Clean up object flag definitions

[Sergey Vlasov]

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;
 

[PATCH 8/8] fetch.c: Remove call to parse_object() from process()

[Sergey Vlasov]

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 {

Re: [PATCH 1/8] fetch.c: Remove useless lookup_object_type() call in process()

[Junio C Hamano]

Sergey Vlasov <vsu@altlinux.ru> 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.

Re: [PATCH 0/8] fetch.c optimizations

[Daniel Barkalow]

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*

Re: [PATCH 1/8] fetch.c: Remove useless lookup_object_type() call in process()

[Sergey Vlasov]

[-- Attachment #1: Type: text/plain, Size: 1080 bytes --]

On Wed, Sep 21, 2005 at 12:45:13PM -0700, Junio C Hamano wrote:
> Sergey Vlasov <vsu@altlinux.ru> 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?

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).

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]