[PATCH] Do not send "want" lines for complete objects

[PATCH] Do not send "want" lines for complete objects

[Johannes Schindelin]

It was all good and well to check if all remote refs are complete (local 
refs or descendants thereof), but we can just as easily use the same 
information to avoid sending "want" lines just for the complete objects in 
the case that not all remote refs are complete (or their names differ).

Also, git-fetch-pack does not have to ask for descendants of remote refs 
which are complete (for now, git-rev-list is told to ignore only the first 
parent). That change also eliminates a code path where a popen()ed handle 
was not pclose()ed.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>

---

	With this patch, in a particular setup, git-fetch got 805 objects 
	instead of 8404, i.e. 10 times less! This setup involves 691 
	tags...

	NOTE: I'd rather have git-rev-list circumvented, so that 
	descendants of ack'ed objects are not sent via "have" lines.

	2nd NOTE: If this patch reminds you of my "has_ref()" patch: Yes,
	it is the next generation of that idea.

 fetch-pack.c |   33 +++++++++++++++++++++++++--------
 1 files changed, 25 insertions(+), 8 deletions(-)

applies-to: f76de7f266b0b7feb38c73c7ccb635d6da18a582
f22af070becd6546eeff44895769b8299a6ddb5e
diff --git a/fetch-pack.c b/fetch-pack.c
index 969e72a..9dfd072 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -12,31 +12,49 @@ static const char fetch_pack_usage[] =
 "git-fetch-pack [-q] [-v] [--exec=upload-pack] [host:]directory <refs>...";
 static const char *exec = "git-upload-pack";
 
+#define COMPLETE	(1U << 0)
+
 static int find_common(int fd[2], unsigned char *result_sha1,
 		       struct ref *refs)
 {
 	int fetching;
 	static char line[1000];
-	int count = 0, flushes = 0, retval;
+	static char rev_command[1024];
+	int count = 0, flushes = 0, retval, rev_command_len;
 	FILE *revs;
 
-	revs = popen("git-rev-list $(git-rev-parse --all)", "r");
-	if (!revs)
-		die("unable to run 'git-rev-list'");
-
+	strcpy(rev_command, "git-rev-list $(git-rev-parse --all)");
+	rev_command_len = strlen(rev_command);
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
 		unsigned char *remote = refs->old_sha1;
-		unsigned char *local = refs->new_sha1;
 
-		if (!memcmp(remote, local, 20))
+		/*
+		   If that object is complete (i.e. it is a descendant of a
+		   local ref), we don't want it, nor its descendants.
+		*/
+		if (has_sha1_file(remote)
+				&& parse_object(remote)->flags & COMPLETE) {
+			if (rev_command_len + 44 < sizeof(rev_command)) {
+				snprintf(rev_command + rev_command_len, 44,
+					" ^%s^", sha1_to_hex(remote));
+				rev_command_len += 43;
+			}
+
 			continue;
+		}
+
 		packet_write(fd[1], "want %s\n", sha1_to_hex(remote));
 		fetching++;
 	}
 	packet_flush(fd[1]);
 	if (!fetching)
 		return 1;
+
+	revs = popen(rev_command, "r");
+	if (!revs)
+		die("unable to run 'git-rev-list'");
+
 	flushes = 1;
 	retval = -1;
 	while (fgets(line, sizeof(line), revs) != NULL) {
@@ -81,7 +99,6 @@ static int find_common(int fd[2], unsign
 	return retval;
 }
 
-#define COMPLETE	(1U << 0)
 static struct commit_list *complete = NULL;
 
 static int mark_complete(const char *path, const unsigned char *sha1)
---
0.99.8.GIT

Re: [PATCH] Do not send "want" lines for complete objects

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Also, git-fetch-pack does not have to ask for descendants of remote refs 
> which are complete (for now, git-rev-list is told to ignore only the first 
> parent).

I should interpret what you said with s/descendant/ancestor/
applied, I think.  I would like to make sure I understand what
you are doing here.

> +		if (has_sha1_file(remote)
> +				&& parse_object(remote)->flags & COMPLETE) {
> +			if (rev_command_len + 44 < sizeof(rev_command)) {
> +				snprintf(rev_command + rev_command_len, 44,
> +					" ^%s^", sha1_to_hex(remote));
> +				rev_command_len += 43;
> +			}

This rev-list command is to generate the list of "have", and we
learned that the other side says she has remote -- we choose not
to tell her that we have ancestors of it, but we do tell her
about the remote head itself.

Let's draw a single strand of pearl case to illustrate.  You
have a commit chain A->B->C->D, and the other end says she has
C.  At this point, telling her that you have C is enough, and by
not telling her about A and B, you would save her from depreting
MAX_HAVE slots.  Of course, if the other end has D as another
head, then the above logic would give "^D^" to rev-list as well,
telling it not to tell her about C, but that is what we want --
because she already knows you have C too when you tell her that
you have D.  I think I like this optimization.

One thing that might help, when we are telling the other end
about what we have, is an output ordering option to get-rev-list
that shows not in chronological order, but in the order of
distance from the tip.  That may give the other end a better
chance to find the latest (in commit order) common commit in
each branch without running out is MAX_HAS buffer.

> 	NOTE: I'd rather have git-rev-list circumvented, so that 
> 	descendants of ack'ed objects are not sent via "have" lines.

I think since we do the traversal ourselves this may start to
make more sense.

Re: [PATCH] Do not send "want" lines for complete objects

[Junio C Hamano]

Junio C Hamano <junkio@cox.net> writes:

> Let's draw a single strand of pearl case to illustrate.  You
> have a commit chain A->B->C->D, and the other end says she has
> C.  At this point, telling her that you have C is enough, and by
> not telling her about A and B, you would save her from depreting
> MAX_HAVE slots.  Of course, if the other end has D as another
> head, then the above logic would give "^D^" to rev-list as well,
> telling it not to tell her about C, but that is what we want --
> because she already knows you have C too when you tell her that
> you have D.  I think I like this optimization.

This was subtly wrong.  ^D^ would barf if D is a tag that points
at a non commit (refs/tags/v2.6.11-tree).  Also it would do a
suboptimal thing for a merge commit, since it will not cull the
second and later parents.

Maybe something like this on top of your patch?  This is turning
out to be quite ugly.

---

diff --git a/fetch-pack.c b/fetch-pack.c
index 9dfd072..5cc3766 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -28,20 +28,29 @@ static int find_common(int fd[2], unsign
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
 		unsigned char *remote = refs->old_sha1;
-
+		struct object *o;
+		struct commit *commit;
 		/*
-		   If that object is complete (i.e. it is a descendant of a
-		   local ref), we don't want it, nor its descendants.
-		*/
-		if (has_sha1_file(remote)
-				&& parse_object(remote)->flags & COMPLETE) {
-			if (rev_command_len + 44 < sizeof(rev_command)) {
+		 * If that object is complete (i.e. it is an ancestor of a
+		 * local ref), we tell them we have it but do not have to
+		 * tell them about its ancestors, which they already know
+		 * about.
+		 */
+		if (has_sha1_file(remote) &&
+		    ((o = parse_object(remote)) != NULL) &&
+		    (o->flags & COMPLETE) &&
+		    ((commit = (struct commit *) deref_tag(o)) != NULL) &&
+		    (commit->object.type = commit_type)) {
+			struct commit_list *p = commit->parents;
+			while (p && rev_command_len + 44 < sizeof(rev_command)) {
 				snprintf(rev_command + rev_command_len, 44,
-					" ^%s^", sha1_to_hex(remote));
+					 " ^%s",
+					 sha1_to_hex(p->item->object.sha1));
 				rev_command_len += 43;
+				p = p->next;
 			}
-
-			continue;
+			if (!p)
+				continue;
 		}
 
 		packet_write(fd[1], "want %s\n", sha1_to_hex(remote));

Re: [PATCH] Do not send "want" lines for complete objects

[Johannes Schindelin]

Hi,

On Wed, 19 Oct 2005, Junio C Hamano wrote:

> Junio C Hamano <junkio@cox.net> writes:
> 
> > Let's draw a single strand of pearl case to illustrate.  You
> > have a commit chain A->B->C->D, and the other end says she has
> > C.  At this point, telling her that you have C is enough, and by
> > not telling her about A and B, you would save her from depreting
> > MAX_HAVE slots.  Of course, if the other end has D as another
> > head, then the above logic would give "^D^" to rev-list as well,
> > telling it not to tell her about C, but that is what we want --
> > because she already knows you have C too when you tell her that
> > you have D.  I think I like this optimization.
> 
> This was subtly wrong.  ^D^ would barf if D is a tag that points
> at a non commit (refs/tags/v2.6.11-tree).  Also it would do a
> suboptimal thing for a merge commit, since it will not cull the
> second and later parents.

Right, I keep forgetting about tags. And again right, like I said, it is 
suboptimal but helps the common case.

> +		if (has_sha1_file(remote) &&
> +		    ((o = parse_object(remote)) != NULL) &&
> +		    (o->flags & COMPLETE) &&

Why not split it here, and do a separate block here:

> +		    ((commit = (struct commit *) deref_tag(o)) != NULL) &&
> +		    (commit->object.type = commit_type)) {
> +			struct commit_list *p = commit->parents;
> +			while (p && rev_command_len + 44 < sizeof(rev_command)) {
>  				snprintf(rev_command + rev_command_len, 44,
> -					" ^%s^", sha1_to_hex(remote));
> +					 " ^%s",
> +					 sha1_to_hex(p->item->object.sha1));
>  				rev_command_len += 43;
> +				p = p->next;
>  			}

And here I am at a loss: why only continue if p is empty? I mean, remote 
could be a tag, and still be complete, no?

> -
> -			continue;
> +			if (!p)
> +				continue;
>  		}
>  
>  		packet_write(fd[1], "want %s\n", sha1_to_hex(remote));
> 

If the git-rev-list call goes, this probably gets prettier. I'll try to 
come up with a patch.

Ciao,
Dscho

Re: [PATCH] Do not send "want" lines for complete objects

[Johannes Schindelin]

Hi,

> > +		    ((o = parse_object(remote)) != NULL) &&
> > +		    (o->flags & COMPLETE) &&

I just realized that parse_object() always reads the file, then does a 
lookup (which makes the above code work), and then parses the file. It 
always does all of these steps, even if the object was already parsed. Any 
reason for this?

Ciao,
Dscho

Re: [PATCH] Do not send "want" lines for complete objects

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Hi,
>
>> > +		    ((o = parse_object(remote)) != NULL) &&
>> > +		    (o->flags & COMPLETE) &&
>
> I just realized that parse_object() always reads the file, then does a 
> lookup (which makes the above code work), and then parses the file. It 
> always does all of these steps, even if the object was already parsed. Any 
> reason for this?

You are right.  We should be using lookup_object() for this part
of the code.

Re: [PATCH] Do not send "want" lines for complete objects

[Daniel Barkalow]

On Thu, 20 Oct 2005, Johannes Schindelin wrote:

> Hi,
> 
> > > +		    ((o = parse_object(remote)) != NULL) &&
> > > +		    (o->flags & COMPLETE) &&
> 
> I just realized that parse_object() always reads the file, then does a 
> lookup (which makes the above code work), and then parses the file. It 
> always does all of these steps, even if the object was already parsed. Any 
> reason for this?

I'm lazy and haven't sent in a patch to clean that up. There's no reason 
it couldn't check whether the value it gets is already parsed.

	-Daniel
*This .sig left intentionally blank*

Re: [PATCH] Do not send "want" lines for complete objects

[Johannes Schindelin]

Hi,

On Thu, 20 Oct 2005, Daniel Barkalow wrote:

> On Thu, 20 Oct 2005, Johannes Schindelin wrote:
> 
> > Hi,
> > 
> > > > +		    ((o = parse_object(remote)) != NULL) &&
> > > > +		    (o->flags & COMPLETE) &&
> > 
> > I just realized that parse_object() always reads the file, then does a 
> > lookup (which makes the above code work), and then parses the file. It 
> > always does all of these steps, even if the object was already parsed. Any 
> > reason for this?
> 
> I'm lazy and haven't sent in a patch to clean that up. There's no reason 
> it couldn't check whether the value it gets is already parsed.

Actually, you don't have to... Junio already replaced parse_object() by 
lookup_object() in this case. I did not use it originally, because lines 
24-25 of commit.h say

	/** Internal only **/
	struct object *lookup_object(const unsigned char *sha1);

Is this obsolete?

Ciao,
Dscho

Re: [PATCH] Do not send "want" lines for complete objects

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin <at> gmx.de> writes:

> ... I did not use it originally, because lines 
> 24-25 of commit.h say
> 
> 	/** Internal only **/
> 	struct object *lookup_object(const unsigned char *sha1);
> 
> Is this obsolete?

For this particular application, it should be OK, because:

 - it checks if we already have that object, and returns a pointer to it;
 - if we haven't seen that object, we get a NULL back;

and

 - what we care about is to see if we have checked and verified if it is
   reachable from our refs.  We do not want the check to actively go read
   and parse that object.

-jc

Re: [PATCH] Do not send "want" lines for complete objects

[Daniel Barkalow]

On Fri, 21 Oct 2005, Johannes Schindelin wrote:

> Hi,
> 
> On Thu, 20 Oct 2005, Daniel Barkalow wrote:
> 
> > On Thu, 20 Oct 2005, Johannes Schindelin wrote:
> > 
> > > Hi,
> > > 
> > > > > +		    ((o = parse_object(remote)) != NULL) &&
> > > > > +		    (o->flags & COMPLETE) &&
> > > 
> > > I just realized that parse_object() always reads the file, then does a 
> > > lookup (which makes the above code work), and then parses the file. It 
> > > always does all of these steps, even if the object was already parsed. Any 
> > > reason for this?
> > 
> > I'm lazy and haven't sent in a patch to clean that up. There's no reason 
> > it couldn't check whether the value it gets is already parsed.
> 
> Actually, you don't have to... Junio already replaced parse_object() by 
> lookup_object() in this case.

It often gets used in cases where it isn't completely obvious that the 
object has already been parsed; this is the second place that it's been 
replaced.

> I did not use it originally, because lines 24-25 of commit.h say
> 
> 	/** Internal only **/
> 	struct object *lookup_object(const unsigned char *sha1);
> 
> Is this obsolete?

I'd intended it to be internal, for use by things like lookup_tree(), but 
I suppose that it could be used more generally, if it got a comment that 
says that, unlike lookup_tree() and such, it returns NULL if the object 
has not already been read (because it doesn't know how to create it).

	-Daniel
*This .sig left intentionally blank*

Re: [PATCH] Do not send "want" lines for complete objects

[Johannes Schindelin]

Hi,

On Wed, 19 Oct 2005, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > Also, git-fetch-pack does not have to ask for descendants of remote refs 
> > which are complete (for now, git-rev-list is told to ignore only the first 
> > parent).
> 
> I should interpret what you said with s/descendant/ancestor/
> applied, I think.  I would like to make sure I understand what
> you are doing here.

Sure. You are thinking along chronological lines. Okay.

> > +		if (has_sha1_file(remote)
> > +				&& parse_object(remote)->flags & COMPLETE) {
> > +			if (rev_command_len + 44 < sizeof(rev_command)) {
> > +				snprintf(rev_command + rev_command_len, 44,
> > +					" ^%s^", sha1_to_hex(remote));
> > +				rev_command_len += 43;
> > +			}
> 
> This rev-list command is to generate the list of "have", and we
> learned that the other side says she has remote -- we choose not
> to tell her that we have ancestors of it, but we do tell her
> about the remote head itself.
> 
> Let's draw a single strand of pearl case to illustrate.  You
> have a commit chain A->B->C->D, and the other end says she has
> C.  At this point, telling her that you have C is enough, and by
> not telling her about A and B, you would save her from depreting
> MAX_HAVE slots.  Of course, if the other end has D as another
> head, then the above logic would give "^D^" to rev-list as well,
> telling it not to tell her about C, but that is what we want --
> because she already knows you have C too when you tell her that
> you have D.  I think I like this optimization.
> 
> One thing that might help, when we are telling the other end
> about what we have, is an output ordering option to get-rev-list
> that shows not in chronological order, but in the order of
> distance from the tip.  That may give the other end a better
> chance to find the latest (in commit order) common commit in
> each branch without running out is MAX_HAS buffer.

That was my idea.

Ciao,
Dscho